在没有递归的情况下遍历非二叉树的算法是什么（使用堆栈） [英] What is the algorithm to traverse a non-binary tree without recursion (using stack)

问题描述

直觉上，我了解到我会像（节点，迭代器）这样使用堆栈对，但是仍然无法找到有效的解决方案。

Intuitively I understand that I keep on stack pairs like (node, iterator), but still I can not get to a working solution.

推荐答案

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

You can always translate a recursive algorithm to one with an explicit stack. Start with recursive code:

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;
}

有了它：一个显式堆栈实现必须在递归版本做到了。

There you have it: an explicit stack implementation that has to work as long as the recursive version did. It's the same thing.

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

Now if you like, we an do some algebra to eliminate the gotos. First we can rewrite the for as a while and refactor the rtn label

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;
}

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

Note the ++i inside the while was dead code, so was safe to drop.

现在请注意， while 的主体永远不会执行多次。可以用 if 代替。我们还可以将 goto rtn_2 替换为其执行的代码。

Now note that the body of the while never executes more than once. It can be replaced with an if. We can also replace goto rtn_2 with the code that it causes to execute.

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 标签：

Finally, we can get rid of the start label by using a loop instead:

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 和 continue 实际上正在实现一个嵌套循环，我们可以使之明确。还有一个多余的 stk [sp] .p = p; 可以删除。只是将一个值复制到已经存在的堆栈中：

Another cleanup is to note that i is always 0 in the first if, and the continue is actually implementing a nested loop, which we can make explicit. There's also a redundant stk[sp].p = p; that can be deleted. It's just copying a value onto the stack that's already there:

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;
      }
    }
  }
}

可以使代码更漂亮，但我将留给您。需要注意的是，没有直觉或想像一下指针在做什么。我们只是对代码进行了代数运算，因此实现了一个相当不错的实现。我还没有运行它，但是除非我犯了一个代数错误（这是可能的），否则这应该行之有效。

It's possible to make the code a bit prettier, but I'll leave that to you. The thing to note is that there was no intuition or trying to imagine what pointers are doing. We just did algebra on the code, and a reasonably nice implementation resulted. I haven't run it, but unless I made an algebra mistake (which is possible), this ought to "just work."

请注意，这与您在教科书中看到的典型的基于堆栈的DFS有点不同。它们将堆栈中新找到的节点的所有子节点推入堆栈，必须首先在最右边的子节点上执行此操作才能获得正常的DFS顺序。

Note this is a bit different from the typical stack-based DFS you'll see in textbooks. Those push all the children of a newly found node on the stack, which must be done rightmost child first to get a normal DFS order.

相反，我们在此处推父代，并带有一个整数，该整数表示接下来应搜索哪个子代。这是您提到的节点+迭代器。它有点复杂，但堆栈大小也更有效。我们的堆栈的最大大小为O（D），其中D是树的最大深度。教科书算法中堆栈的大小为O（KD），其中K是节点可以拥有的最大子代数。

Instead here we are pushing the parent along with an integer saying which child should be searched next. This is the node + iterator you mentioned. It's a bit more complex but also more efficient in stack size. The max size of our stack is O(D) where D is the max depth of the tree. The size of the stack in the textbook algorithm is O(KD) where K is the max number of children a node can have.

这篇关于在没有递归的情况下遍历非二叉树的算法是什么（使用堆栈）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！