树遍历的迭代方法

Question

有人可以帮助我使用算法迭代地遍历二叉树而不使用任何其他数据结构,如堆栈

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

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

Answer 1

一种选择是线程化二叉树.

每当某个节点指向NULL(向左或向右)时,使该节点指向其遍历中的下一个节点(预订,后序等).通过这种方式,您可以在一次迭代中遍历整个树.

示例线程二叉树:

请注意,每个节点的左节点指向小于它的最大值.并且每个节点的右节点指向大于它的最小值.所以这给出了有序遍历.