Morris中序遍历二叉树

Posted on
一般遍历的二叉树的方法，要么使用递归『空间复杂度为O(n)』，要么使用栈『空间复杂度为O(h)』。Morris遍历通过调整树的结构，使空间复杂度降为O(1)。本文结合示意图和代码对Morris中序遍历二叉树做简单的介绍。

一般方法遍历二叉树

一般方法遍历二叉树都是通过递归合着栈，递归本身存在函数调用栈，其空间复杂度必然是O(n)；使用栈的情况下，由于遍历时需要将从当前节点到叶子节点之间的经过的所有节点压入栈中，所以最大需要O(h)的空间复杂度，h为树的高度。

图示Morris遍历

Morris遍历通过调整树的结构，可以只用O(1)的空间复杂度实现对二叉树的遍历。下图是Morris算法对二叉树遍历的完整的过程。

Morris中序遍历的流程

从图中的说明可以看出，Morris的最核心的思想就是：找到当前节点中序遍历的前驱结点，并将前驱节点的右节点指向当前节点，知道当前节点的左子树处理完成后，再将树结构调整回原状。

总结Morris中序遍历算法过程如下：

  1. 初始化当前节点指向根节点
  2. 如果当前节点不为空
    • 如果当前节点没有左节点
      • 输出当前节点的数据
      • 设置当前节点指向当前节点的右节点
    • 如果当前节点存在左节点
      • 寻找当前节点的左子树的最右节点的右节点，设置其为前驱结点
        • 如果前驱结点的右节点为空，则将其右节点指向当前节点（还未遍历过，需要修改树结构）
        • 如果前驱节点的右节点已经指向当前节点，则将其右节点置空（已经遍历过，将树结构修改回原样）
      • 设置当前节点指向当前节点的左节点

Morris中序遍历的Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Java program to print inorder traversal without recursion and stack
 
// A binary tree node
class Node {
    int data;
    Node left, right;
     
    Node(int item) {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    static Node root;
    /* Function to traverse binary tree without recursion and 
     without stack */
    void MorrisTraversal(Node node) {
        Node current, pre;
         
        if (node == null) {
            return;
        }
         
        current = node;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.data + " ");
                current = current.right;
            } else {
 
                /* Find the inorder predecessor of current */
                pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }
 
                /* Make current as right child of its inorder predecessor */
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } 
 
                /* Revert the changes made in if part to restore the original 
                tree i.e., fix the right child of predecssor */ else {
                    pre.right = null;
                    System.out.print(current.data + " ");
                    current = current.right;
                } /* End of if condition pre->right == NULL */
                 
            } /* End of if condition current->left == NULL*/
             
        } /* End of while */
         
    }
     
    public static void main(String args[]) {
        int sum = 14;
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
         
        tree.MorrisTraversal(root);
    }
}
 
// This code has been contributed by Mayank Jaiswal

参考

  1. Inorder Tree Traversal without recursion and without stack!
  2. Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）