二叉树的遍历（递归，非递归，Morris）

迈不过友情╰ 2023-06-23 02:52 70阅读 0赞

# 二叉树的遍历 #

--------------------

## 目录 ##

1.  递归遍历
2.  非递归遍历
3.  Morris遍历

--------------------

### 1. 递归遍历 ###

递归版遍历只要当前节点不为null，就可以三次回到当前节点。

public static void preOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            System.out.print(head.value + " ");
            preOrderRecur(head.left);
            preOrderRecur(head.right);
        }
    
        public static void inOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            inOrderRecur(head.left);
            System.out.print(head.value + " ");
            inOrderRecur(head.right);
        }
    
        public static void posOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            posOrderRecur(head.left);
            posOrderRecur(head.right);
            System.out.print(head.value + " ");
        }

--------------------

### 2. 非递归遍历 ###

其中后序遍历打印顺序为**左右中**，由先序遍历打印顺序为**中左右**，所以可以对先序遍历改进为**中右左**（改变添加顺序），添加到另外一个栈中，最后遍历打印就是**左右中**顺序了。

public static void preOrderUnRecur(Node head) {
        
            System.out.println("pre-order: ");
            while (head != null) {
        
                Stack<Node> stack = new Stack<>();
                stack.push(head);
                while (!stack.isEmpty()) {
        
                    Node node = stack.pop();
                    System.out.println(node.value + " ");
                    if (node.right != null) {
        
                        stack.push(node.right);
                    }
                    if (node.left != null) {
        
                        stack.push(node.left);
                    }
                }
            }
        }
    
        public static void inOrderUnRecur(Node head) {
        
            System.out.print("in-order: ");
            if (head != null) {
        
                Stack<Node> stack = new Stack<>();
                while (!stack.isEmpty() || head != null) {
        
                    if (head != null) {
        
                        stack.push(head.left);
                        head = head.left;
                    } else {
        
                        head = stack.pop();
                        System.out.println(head.value + " ");
                        head = head.right;
                    }
                }
            }
            System.out.println();
        }
    
        public static void posOrderUnRecur1(Node head) {
        
            System.out.print("pos-order: ");
            if (head != null) {
        
                Stack<Node> s1 = new Stack<>();
                Stack<Node> s2 = new Stack<>();
                s1.push(head);
                while (!s1.isEmpty()) {
        
                    head = s1.pop();
                    s2.push(head);
                    if (head.left != null) {
        
                        s1.push(head.left);
                    }
                    if (head.right != null) {
        
                        s1.push(head.right);
                    }
                    while (!s2.isEmpty()) {
        
                        System.out.print(s2.pop().value + " ");
                    }
                }
            }
            System.out.println();
        }

--------------------

### 3. Morris遍历 ###

Morris遍历法，能以时间复杂度O(N)，空间复杂度O(1)实现二叉树的遍历。

程序流程：  
假设指针cur指向当前节点，cur从头结点开始。

1.  如果cur无左孩子，则cur = cur.right；
2.  如果cur有左孩子，则找到cur左子树上最右的节点，记为mostRight，分为以下两种情况：
    
    1.  若mostRight的right指针为null，则让其指向cur，且cur = cur.left;
    2.  若mostRight的right指针指向cur，则让其指回null，且cur = cur.right。

--------------------

假设二叉树如下：

1
          2        3
       4    5   6    7

则Morris遍历顺序为：1,2,4,2,5,1,3,6,3,7

Morris 遍历代码实现：

**特点：**

1.  当某个节点有左子树，则会到达该节点两次，如果没有左子树，只会到达一次。
2.  当第二次回到某个节点时，它的左子树已遍历完。

**实质：**  
Morris遍历是利用左子树最右节点的指针指向null或指向自己来标记是第一次来到该节点还是第二次来到该节点。

--------------------

**Morris遍历改先序遍历**

在以下两种情况下打印节点:

1.  当节点没有左子树时，打印当前节点；
2.  当节点有左子树时并且第一次访问时打印该节点，就是当mosrRight的右指针为null时。

public static void morrisPre(Node head) {
        
            if (head == null) {
        
                return;
            }
            Node cur = head;
            Node mostRight = null;
            while (cur != null) {
        
                mostRight = cur.left;
                if (mostRight != null) {
        
                    while (mostRight.right != null && mostRight.right != cur) {
        
                        mostRight = mostRight.right;
                    }
                    if (mostRight.right == null) {
        
                        mostRight.right = cur;
                        System.out.print(cur.value + " ");
                        cur = cur.left;
                        continue;
                    } else {
        
                        mostRight.right = null;
                    }
                } else {
        
                    System.out.print(cur.value + " ");
                }
                cur = cur.right;
            }
            System.out.println();
        }

**Morris遍历改中序遍历**

在以下两种情况下打印节点:

1.  当节点没有左子树时，说明第一次和第二次是重合在一起的，打印当前节点即可。
2.  当节点有左子树时，那么需要处理完左子树再打印，即当前节点准备右移时打印。

public static void morrisIn(Node head) {
        
            if (head == null) {
        
                return;
            }
            Node cur = head;
            Node mostRight = null;
            while (cur != null) {
        
                mostRight = cur.left;
                if (mostRight != null) {
        
                    while (mostRight.right != null && mostRight.right != cur) {
        
                        mostRight = mostRight.right;
                    }
                    if (mostRight.right == null) {
        
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
        
                        mostRight.right = null;
                    }
                }
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
            System.out.println();
        }

**Morris遍历改后序遍历**

在以下两种情况下打印节点:

1.  只有当到达某个节点两次时逆序打印该节点左子树的右边界;
2.  在代码的最后逆序打印整棵树的右边界，而逆序的过程就和单向链表的反转过程类似。

public static void morrisPos(Node head) {
        
            if (head == null) {
        
                return;
            }
            Node cur1 = head;
            Node cur2 = null;
            while (cur1 != null) {
        
                cur2 = cur1.left;
                if (cur2 != null) {
        
                    while (cur2.right != null && cur2.right != cur1) {
        
                        cur2 = cur2.right;
                    }
                    if (cur2.right == null) {
        
                        cur2.right = cur1;
                        cur1 = cur1.left;
                        continue;
                    } else {
        
                        cur2.right = null;
                        printEdge(cur1.left);
                    }
                }
                cur1 = cur1.right;
            }
            printEdge(head);
            System.out.println();
        }
    
        public static void printEdge(Node head) {
        
            Node tail = reverseEdge(head);
            Node cur = tail;
            while (cur != null) {
        
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
            reverseEdge(tail);
        }
    
        public static Node reverseEdge(Node from) {
        
            Node pre = null;
            Node next = null;
            while (from != null) {
        
                next = from.right;
                from.right = pre;
                pre = from;
                from = next;
            }
            return pre;
        }