无递归的二叉树遍历的直观解释

我见过很多文章和书籍（和堆栈溢出的答案），它们展示了如何使用显式堆栈而不是递归迭代地执行深度优先树遍历的前序，后序和后序。例如：https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2 无递归的二叉树遍历的直观解释

预订遍历很简单，但我认为其他人很复杂，远不明显。

是否有任何源代码（最好是文章或书籍）直观地解释这些算法，所以你可以看到有人会如何想出他们呢？

2016-08-02 gesgsklw

从技术上讲，使用堆栈是递归，只是不明确。这是隐式递归，因为类似于一遍又一遍地调用一个方法，使用了一个堆栈。这只是一种方式使用调用堆栈而另一种使用节点堆栈。没有某种递归，你无法真正穿过一棵树。 –

@DaneBrick，*技术*，这是不正确的。它是一个函数根据自身定义的递归。 –

@MattTimmermans我明白了，但是如果OP在理解堆栈的树遍历时有困难，但是可以理解递归的遍历，那么我想指出两种遍历方法其实都非常相似。因为堆栈用于递归。 –

在所有情况下，堆栈用于存储您不能马上完成的工作。预购案例最简单，因为只有一种工作需要推迟 - 处理一个子节点。

预订：堆栈保存要处理的节点。要处理节点，请访问它，将正确的子节点推入堆栈，然后处理下一个左侧子节点。如果没有剩下的孩子，那么从堆栈中抓一个。

Inorder也很容易。堆栈具有存储节点访问和节点的过程，但过程中的节点总是刚去过，所以一个节点的右子：

中序：堆栈持有节点访问。当我们从堆栈中取出一个节点时，我们访问它，然后处理它的正确的孩子。当我们处理一个节点时，我们把它放在堆栈上，然后处理它的左边的孩子。

后序是棘手的，因为堆栈具有存储节点访问和节点的过程，他们并不总是简单的相关就像他们在中序情况。堆栈必须以某种方式指示哪个是哪个。

你可以这样说：

后序：堆栈持有节点访问或处理，与已处理孩子的号码。要处理来自堆栈的条目(n,x)，请访问节点n，如果它有< = x个子项。否则将(n,x+1)放在堆栈上并处理节点的第一个未处理的子节点。

2016-08-02 20:23:33

回答