ges*_*klw 6 language-agnostic algorithm tree recursion
我看过很多文章和书籍（以及 Stack Overflow 的答案），它们展示了如何使用显式堆栈而不是递归来迭代地进行前序、中序和后序深度优先树遍历。例如：https : //en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2
前序遍历很简单，但我认为其他的很复杂，而且远非显而易见。
是否有任何来源（最好是文章或书籍）可以直观地解释这些算法，以便您首先了解有人是如何提出这些算法的？
如何提出没有堆栈的迭代解决方案
实现迭代树遍历不需要堆栈！您可以通过在树节点数据结构中保留父指针来摆脱任何堆栈。这就是你想出它的方式：
什么是迭代解决方案？迭代解决方案是一种解决方案，其中代码的固定部分在循环中重复执行（几乎是迭代的最终结果）。循环的输入是系统的状态 s1，输出是状态 s2，循环将系统从状态 s1 带到状态 s2。您从初始状态 s 开始，并在达到最终所需状态 s 时结束。
所以我们的问题简化为发现：
（这有效地将树变成了状态机。）
在树遍历中，每一步都会访问一个节点。树的每个节点最多被访问三次——一次来自父节点，一次来自左子节点，一次来自右子节点。我们在特定步骤对节点做什么取决于它是三种情况中的哪一种。
因此，如果我们捕获所有这些信息：我们正在访问哪个节点，以及它是哪种情况，我们就有了系统的特征。
捕获此信息的一种方法是存储对先前节点/状态的引用：
Node current;
Node previous;
如果previous = current.parent，那么我们是从父访问。如果previous = current.leftChild，我们从左边访问，如果previous = current.rightChiild，我们从右边访问。
我们可以捕获此信息的另一种方法：
Node current;
boolean visitedLeft;
boolean visitedRight;
如果visitedLeft 和visitedRight 都为false，那么我们是从父访问，如果visitedLeft 为真但visitedRight 为false，我们从左边访问，如果visitedLeft 和visitedRight 都为真，我们从右边访问（第四个状态：visitedLeft false 但visitedRight false，在 preOrder 中从未达到）。
最初，我们从 viisitedLeft = false、visitedRight = false 和 current = root 开始。当遍历完成时，我们期望visitedLeft = true，visitedRight = true，current = null。
在作为循环的一部分重复运行的指令中，系统必须从一种状态移动到另一种状态。所以在指令中，我们只是告诉系统在遇到任何状态时要做什么，以及何时结束执行。
您可以将所有三个遍历组合在一个函数中：
void traversal(String typeOfTraversal){
boolean visitedLeft = false;
boolean visitedRight = false;
TreeNode currentNode = this.root;
while(true){
if (visitedLeft == false && currentNode.leftChild != null){
if(typeOfTraversal == "preOrder"){
System.out.println(currentNode.key);
}
currentNode = currentNode.leftChild;
continue;
}
if (visitedLeft == false && currentNode.leftChild == null){
if(typeOfTraversal == "preOrder"){
System.out.println(currentNode.key);
}
visitedLeft = true;
continue;
}
if (visitedLeft == true && visitedRight == false && currentNode.rightChild != null){
if(typeOfTraversal == "inOrder"){
System.out.println(currentNode.key);
}
currentNode = currentNode.rightChild;
visitedLeft = false;
continue;
}
if (visitedLeft == true && visitedRight == false && currentNode.rightChild == null){
if(typeOfTraversal == "inOrder"){
System.out.println(currentNode.key);
}
visitedRight = true;
continue;
}
if (visitedLeft == true && visitedRight == true && currentNode.parent != null){
if(typeOfTraversal == "postOrder"){
System.out.println(currentNode.key);
}
if (currentNode == currentNode.parent.leftChild){
visitedRight = false;
}
currentNode = currentNode.parent;
}
if (visitedLeft == true && visitedRight == true && currentNode.parent == null){
if(typeOfTraversal == "postOrder"){
System.out.println(currentNode.key);
}
break; //Traversal is complete.
}
如果您获得节点级锁，则该算法允许树的并发遍历和更新。除了分离非叶节点之外的任何原子操作都是安全的。
如何提出基于堆栈的解决方案
当考虑将递归解决方案转换为迭代解决方案，或者为递归定义的问题提出迭代解决方案时，堆栈是有用的数据结构。调用堆栈是一种堆栈数据结构，用于存储有关计算机程序的活动子例程的信息，是大多数高级编程语言在底层实现递归的方式。因此，在迭代解决方案中显式使用堆栈，我们只是在编写递归代码时模仿处理器所做的事情。Matt Timmermans 的回答对使用堆栈的原因以及如何提出基于堆栈的显式解决方案给出了很好的直觉。
我在这里写过关于如何提出带有两个堆栈的 postOrder 解决方案的文章：Understanding the logic in iterative Postorder traversal implementation on a Binary tree。
基于父指针的方法比基于堆栈的方法消耗更多的内存。在堆栈上，指向仍要处理的节点的指针是暂时的，只需要 O(log n) 堆栈空间的数量级，因为您只需要为树下的单个路径保留足够的它们（实际上，这可能会更少）。相反，用节点存储父指针需要固定的 O(n) 空间。
预序：通过访问节点来处理节点，然后处理每个子节点。
中序：通过处理左子节点、访问该节点、然后处理右子节点来处理节点。
PostOrder (DFS)：通过处理每个子节点，然后访问该节点来处理节点。
在所有情况下，堆栈都用于存储您无法立即完成的工作。预购情况是最简单的，因为只有一种工作需要推迟——处理子节点。
预序：堆栈保存要处理的节点。要处理节点，请访问它，将右子节点压入堆栈，然后处理左子节点。如果没有左孩子，则从堆栈中抓取一个。
Inorder也很容易。堆栈必须存储要访问的节点和要处理的节点，但要处理的节点始终是刚刚访问的节点的右子节点，因此：
Inorder：堆栈保存要访问的节点。当我们从堆栈中取出一个节点时，我们访问它，然后处理它的右子节点。当我们处理一个节点时，我们将它放入堆栈中，然后处理它的左子节点。
后序比较棘手，因为堆栈必须存储要访问的节点和要处理的节点，并且它们并不总是像 Inorder 情况那样简单相关。堆栈必须以某种方式指示哪个是哪个。
你可以这样做：
后序：堆栈保存要访问或处理的节点，以及已处理的子节点的数量。
(n,x)要处理堆栈中的条目，请访问节点n（如果它有 <= x 个子节点）。否则放入(n,x+1)堆栈并处理节点的第一个未处理的子节点。