algorithm - 树遍历的迭代方法

Question

谁能帮我想出一种迭代遍历二叉树的算法而不使用任何其他数据结构(如堆栈)

我在某处读到我们可以为每个节点设置一个名为 visited 的标志，如果节点被访问则打开，但我的 BinaryTreeNode 类没有定义 visited 变量。所以我不能做类似 node.left.visited = false 的事情

有没有其他方法可以迭代遍历？

Answer 1

一个选择是 thread二叉树。

每当某个节点指向NULL(无论是左还是右)时，使该节点指向其遍历中的下一个节点(前序、后序等)。这样，一次迭代就可以遍历整棵树。

示例线程二叉树:

注意每个节点的左节点指向比它小的最大值。而每个节点的右节点指向比它大的最小值。所以这给出了一个中序遍历。