不使用递归或堆栈的树的PostOrder遍历

Question

可能重复： 无递归二叉树的后序遍历

我正在研究莫里斯在二叉树中的无序遍历算法。请有人建议是否有一种不使用递归和堆栈来遍历postorder的方法？

Answer 1

您可以使用螺纹树来完成这一任务。下面是该方法的概要(摘自这里-see幻灯片31)：

• Postorder:创建的一个虚拟节点，其根作为左后代。
• 变量可用于检查当前操作的类型。
• 如果操作是左遍历的，而当前节点有左子代，则遍历子代。否则，操作更改为右遍历。
• 如果操作是右遍历，且当前节点具有左后代，则操作更改为左遍历。否则，操作更改为访问节点。
• 如果操作是访问节点:访问当前节点之后，必须找到它的后继节点。
• 如果通过线程访问当前节点的父节点(即当前节点是父节点的左子节点)，则遍历设置为继续使用父节点的右后代。
• 如果当前节点没有正确的后代，则这是右扩展节点链的结束。
• 首先:通过当前节点的线程到达链的开始。
• 第二，反转链中节点的正确引用。
• 最后:向后扫描链，访问每个节点，然后将正确的引用还原到以前的设置。

正如上面的引用所显示的那样，如果对树结构使用临时修改，也可以不进行线程处理。