algorithm - 不用递归遍历非二叉树的算法是什么(使用栈)

Question

<分区>

Answer 1

您始终可以将递归算法转换为具有显式堆栈的算法。从递归代码开始:

void traverse(NODE *p) {
  if (p) {
    for (int i = 0; i < p->n_children; ++i) {
      traverse(p->child[i]);
    }
  }
}

替换递归调用:

struct {
  NODE *p;
  int i;
} stk[MAX_RECURSION_DEPTH];
int sp = 0;

void traverse(NODE *p) {
 start:
  if (p) {
    for (int i = 0; i < p->n_children; ++i) {
      // Save local values on stack.
      stk[sp].p = p;
      stk[sp++].i = i;
      // Simulate recursive call.  
      p = p->child[i];        
      goto start;
      // Goto this label for return.
     rtn:
    }
  }
  // Simulate recursive return, restoring from stack if not empty.
  if (sp == 0) return;
  p = stk[--sp].p;
  i = stk[sp].i;
  goto rtn;
}

你有它:一个显式堆栈实现，只要递归版本就可以工作。这是同一回事。

现在，如果您愿意，我们可以做一些代数运算来消除 goto。首先我们可以将for重写为while并重构rtn标签

void traverse(NODE *p) {
  int i;
 start:
  if (p) {
    i = 0;
   rtn_2:
    while (i < p->n_children) {
      stk[sp].p = p;
      stk[sp++].i = i;
      p = p->child[i];        
      goto start;
    }
  }
  if (sp == 0) return;
  p = stk[--sp].p;
  i = stk[sp].i;
  ++i;
  goto rtn_2;
}

请注意 while 中的 ++i 是死代码，因此可以安全删除。

现在请注意，while 的主体绝不会执行多次。它可以用 if 替换。我们还可以用它导致执行的代码替换 goto rtn_2。

void traverse(NODE *p) {
  int i;
 start:
  if (p) {
    i = 0;
    if (i < p->n_children) {
      stk[sp].p = p;
      stk[sp++].i = i;
      p = p->child[i];        
      goto start;
    }
  }
  for (;;) {
    if (sp == 0) return;
    p = stk[--sp].p;
    i = stk[sp].i;
    ++i;
    if (i < p->n_children) {
      stk[sp].p = p;
      stk[sp++].i = i;
      p = p->child[i];        
      goto start;
    }
  }
}

最后，我们可以使用循环代替 start 标签:

void traverse(NODE *p) {
  int i;
  for (;;) {
    if (p) {
      i = 0;
      if (i < p->n_children) {
        stk[sp].p = p;
        stk[sp++].i = i;
        p = p->child[i];        
        continue;
      }
    }
    for (;;) {
      if (sp == 0) return;
      p = stk[--sp].p;
      i = stk[sp].i;
      ++i;
      if (i < p->n_children) {
        stk[sp].p = p;
        stk[sp++].i = i;
        p = p->child[i];        
        break;
      }
    }
  }
}

另一个清理是要注意 i 在第一个 if 中始终为 0，而 continue 实际上是在实现一个嵌套循环，它我们可以明确。还有一个多余的 stk[sp].p = p; 可以删除。它只是将一个值复制到已经存在的堆栈上:

void traverse(NODE *p) {
  for (;;) {
    while (p && p->n_children > 0) {
      stk[sp].p = p;
      stk[sp++].i = 0;
      p = p->child[0];        
    }
    for (;;) {
      if (sp == 0) return;
      p = stk[--sp].p;
      int i = stk[sp].i + 1;
      if (i < p->n_children) {
        stk[sp++].i = i; // stk[sp].p = p; was redundant, so deleted
        p = p->child[i];        
        break;
      }
    }
  }
}

可以让代码更漂亮一些，但我会把它留给你。需要注意的是，没有直觉或试图想象指针在做什么。我们只是对代码进行了代数计算，结果是一个相当不错的实现。我没有运行它，但除非我犯了代数错误(这是可能的)，否则这应该“有效”。

请注意，这与您在教科书中看到的典型的基于堆栈的 DFS 略有不同。那些将新找到的节点的所有子节点推送到堆栈上，必须首先完成最右边的子节点才能获得正常的 DFS 顺序。

相反，在这里我们将父级与一个整数一起推送，说明接下来应该搜索哪个子级。这就是你说的节点+迭代器。它有点复杂，但在堆栈大小方面也更有效。我们堆栈的最大大小是 O(D)，其中 D 是树的最大深度。教科书算法中堆栈的大小是 O(KD)，其中 K 是一个节点可以拥有的最大子节点数。