c - 不使用递归或堆栈的树的后序遍历

Question

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

我正在研究莫里斯的二叉树中的中序遍历算法。有人可以建议是否有一种方法可以在postorder不使用递归和堆栈的情况下进行遍历？

Answer 1

您可以使用线程树来执行此操作。以下是该方法的概述（取自此处— 参见幻灯片 31）：

• 后序：创建的虚拟节点，其根为左后代。
• 变量可用于检查当前操作的类型。
• 如果动作是左遍历并且当前节点有左后代，则遍历后代。否则动作改为右遍历。
• 如果 action 是右遍历且当前节点有左后代，则 action 更改为左遍历。否则操作更改为访问节点。
• 如果动作是访问节点：访问当前节点，之后必须找到它的后序后继节点。
• 如果当前节点的父节点可通过线程访问（即当前节点是父节点的左子节点），则遍历设置为继续父节点的右后代。
• 如果当前节点没有右后代，则这是右扩展节点链的末端。
• 第一：通过当前节点的线程到达链的开头。
• 第二：链中节点的正确引用被颠倒。
• 最后：向后扫描链，访问每个节点，然后将右引用恢复为之前的设置。

正如上面的参考资料继续显示的那样，如果您对树结构使用临时修改，也可以在不使用线程的情况下完成。