二叉树的遍历

发表于 | 分类于

看了左程云老师的算法课，记录学习过程，整理思路和形成系统认识。
主要介绍二叉树定义，和二叉树的前中后三种遍历方式的递归和非递归的实现。

一. 简介

二叉树定义

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。

二叉树实现

1
2
3
4
5
6
7
8
9
public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

二叉树性质

1、非空二叉树的第n层上至多有2(n-1)个元素
2、深度为h的二叉树至多有2h-1个结点
3、对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1

特殊的二叉树

满二叉树

  • 定义
    所有终端都在同一层次，且非终端结点的度数为2。

  • 性质
    在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。

完全二叉树

  • 定义
    除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。

  • 性质
    对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。(理解这个对堆的理解很重要)

二. 遍历

  • 定义
    （按规则）访问二叉树的所有结点且仅访问一次。
  • 分类
    按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
  1. 前序遍历preOrder：
    根节点->左子树->右子树（根节点在前面）
  2. 中序遍历inOrder：
    左子树->根节点->右子树（根节点在中间）
  3. 后序遍历posOrder：
    左子树->右子树->根节点（根节点在后边）

三. 代码实现

递归

  • 递归的前中后序遍历，逻辑是一样的，区别在于打印节点的时机。

递归过节点

  • 递归结束的关键是，理解叶子节点的后继节点是null节点，代码if (head == null) return;导致一个节点有可能被“经过三次”，这三次中：
  1. 第一次经过时打印节点，就是前序遍历
  2. 第二次经过时打印节点，就是中序遍历
  3. 第三次经过时打印节点，就是后序遍历

递归前序

1
2
3
4
5
6
7
8
public static void preOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    System.out.print(head.value + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

递归中序

1
2
3
4
5
6
7
8
public static void inOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

递归后序

1
2
3
4
5
6
7
8
public static void posOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.value + " ");
}

非递归

非递归，借助栈结构，实现类似递归的返回过程。

非递归前序

总体入栈顺序：根 -> 右 -> 左

  • 每次栈不空，就弹出栈顶，并且压入其右节点 (如果不空)，然后压入左节点(如果不空)

非递归前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void preOrderUnRecur(Node head) {
    System.out.print("pre-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();//借助栈结构
        stack.add(head);
        while (!stack.isEmpty()) { //栈不空
            Node cur = stack.pop();//每次while都弹出栈顶
            System.out.print(cur.value + " ");
            if (cur.right != null) {//当前节点有右就 先入右（所以右后出），注意是`if`
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }
    System.out.println();
}

非递归中序

  1. 当前节点的整个“左边界”全部入栈
  2. 否则(遇到空节点) 栈顶出栈，指针变成 弹出元素的右孩子

非递归中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void inOrderUnRecur(Node head) {
    System.out.print("in-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {  //当前节点不空，则把的整个“左边界”全部入栈
                stack.push(head);
                head = head.left;
            } else {   // 此时当前节点为null了，但是栈里不空；弹出/打印/右窜
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
    System.out.println();
}

非递归后序

  • 先根据先序遍历非递归 改变 左右压栈顺序，变成根 右 左
  • 然后该打印时不打印,而是放在辅助栈中,就成了左 右 根顺序,打印之!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void posOrderUnRecur(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();  //辅助栈；
        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();
}

总的测试

测试树：

1
2
3
4
5
              1
        /          \
    2              3
  /    \          /    \
4      5        6       7

遍历结果
前：1 - 2 - 4 - 5 - 3 - 6 - 7
中：4 - 2 - 5 - 1 - 6 - 3 - 7
后：4 - 5 - 2 - 6 - 7 - 3 - 1

代码：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class PreInPosTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    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 + " ");
    }

    public static void preOrderUnRecur(Node head) {
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
            	Node cur = stack.pop();
                System.out.print(cur.value + " ");
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
        System.out.println();
    }

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

    public static void posOrderUnRecur(Node head) {
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            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();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderRecur(head);
        System.out.println();

        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur(head);
    }
}

输出

无论递归非递归,本质都是使用了栈,由于二叉树整体是向下的,当遍历到某一结点时需要回去时,就是刚刚好逆序的栈。

> >