Java 中用于中序遍历的 Morris 遍历

在本节中，我们将学习 Java 中的 Morris 中序遍历。在 Morris 遍历中，我们可以在不借助递归或栈的情况下遍历树。Morris 遍历基于线索二叉树。在此遍历中，我们进行内部修改以创建指向中序后继的内部链接。最终，我们恢复修改，以使原始树恢复原状。

Morris 中序遍历算法

以下是 Morris 遍历（中序）涉及的步骤。

1. 将当前节点初始化为根节点
2. 当当前节点不为空时
   当当前节点没有左子节点时
   1. 显示当前节点的数据
   2. 访问当前节点的右节点，即 curr = curr -> right
      否则 / ELSE
      1. 在当前左子树中查找最右边的节点
         或
         该节点的右子节点是当前节点。
         如果右子节点 == 当前节点 (curr node)
         1. 恢复更改。这意味着右子节点应被设为 NULL，该节点是
            一个右子节点为当前节点的节点
         2. 显示当前节点的数据
         3. 访问右节点，即 curr = curr -> right
            否则 / ELSE
            1. 当前节点应成为我们找到的最右边节点的右子节点；并且
            2. 访问此左子节点，即 curr = curr -> left

实施

让我们使用上面描述的算法来看一下 Morris 中序遍历的实现。

文件名： BTree.java

输出

The inorder traversal of the binary tree is: 
1 8 4 6 9 7

时间复杂度：我们观察到树的每条边最多被遍历 3 次。相同的额外边数量，与输入树相同，被移除和创建。因此，上述程序的总时间复杂度为 O(n)。

注意：在很多地方，人们说递归方法进行中序遍历不消耗任何空间。然而，这是不正确的。在递归中，即使我们没有显式提供栈，也会使用栈。

Morris 遍历可以通过对二叉树进行的内部修改来工作。如果没有内部修改，Morris 遍历将无法工作。