二叉树遍历

二叉树 binary tree ： 每个节点最多有 2 个孩子节点

名词：

根的节点
根的子树
叶子节点 ： 没有“孩子” 的 leaf
父节点 parent
兄弟节点： sibling
孩子节点： child
树的高度
左孩子 left child
右孩子 right child

满二叉树 ： 一个二叉树的所有非叶子节点都存在左右孩子，并且所有的叶子节点都在同一个层级上。。。每一个分支都是满的
完全二叉树：对一个有 n 个节点的二叉树，按层级顺序编号，所有的编号从1 到 n ，，如果这个树的所有节点和同样深度的满二叉树的编号 从1到n 节点位置相同，则是完全二叉树
二叉查找树 binary search tree： 对于一个节点分布均衡的二叉查找树，如果节点总数是n，那么时间复杂度为O(logn),和树的深度一样
二叉查找树，又称 二叉排序树 binary sort tree
二叉堆： 一种特殊的完全二叉树，用数组存储，只要求父节点比它的左右孩子都大
二叉树自平衡： 红黑树，AVL树，数堆

二叉树遍历

在计算机程序中，遍历本身是一个线性操作，所以遍历同样具有线性结构的数组或链表，是件轻而易举的事
二叉树： 典型的非线性数据结构，遍历时需要将非线性关联节点转化成一个线性的序列

• 深度优先遍历 ： 纵深，一头扎到底
  • 前序
    根节点在最前面，从左到右
  • 中序
  • 后序
• 广度优先遍历
  • 层序遍历 ：二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点

绝大多数可以用递归解决的问题，其实都可以用栈 解决
因为：递归和栈都有回溯的特性

代码：
递归遍历：

public class BinaryTreeDemo {
    private static class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    // 创建binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }

    // 前序
    public static void preOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);

    }

    // 中序
    public static void inOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    // 后序
    public static void postOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println("前序遍历");
        preOrderTraveral(node);
        System.out.println("中序遍历");
        inOrderTraveral(node);
        System.out.println("后序遍历");
        postOrderTraveral(node);
    }
}

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

栈遍历：

public class BinaryTreeStack {
    private static class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    // 先序
    public static  void preOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){

            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }

            if (!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }

        }
    }

    // 中序
    public static void inOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
            if (treeNode != null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }else{
                 treeNode = stack.pop();
                System.out.println("----"+treeNode.data);
                treeNode = treeNode.rightChild;
            }
        }
    }

    /**
     *  后序遍历 ： 顺序  左--右--根
     *  先序遍历 ： 顺序  根--左--右
     *  这里我们可以想到，将先序遍历微调为： 根 -- 右 -- 左。。 然后将这些节点 出栈 ，，push到一个反向栈中，调换顺序
     *  这个微调很简单，只是在push节点到栈时，先push左节点，再push右节点，，此时栈顶是右节点，，，先弹出的是右节点，再push
     *  到反向栈stackReverse中，再push节点
     *  核心: 我们只需要增加一个栈来反向输出微调之后的先序遍历的每个节点，就可以得到后序遍历
     */
    public static void postOrderBinaryTreeWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        Stack<TreeNode> stackReverse = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            treeNode = stack.pop();
            stackReverse.push(treeNode);
            // stack中右边先取出来，，stackReverse中右边先放进去，后取出来
            if (treeNode.leftChild != null){
                stack.push(treeNode.leftChild);
            }
            if (treeNode.rightChild != null){
                stack.push(treeNode.rightChild);
            }
        }

        while (!stackReverse.isEmpty()){
            treeNode = stackReverse.pop();
            list.add(treeNode.data);
        }
        System.out.println(list);


    }

    // 创建binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }


    // 层序遍历
    public static void levelOrderTraversalWithQueue(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if (node.leftChild != null){
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null){
                queue.offer(node.rightChild);
            }
        }
    }

    // 一个层级 ：一个集合
   static ArrayList<List<Integer>> levels = new ArrayList<>();
    // 层序遍历-递归
    public static void levelOrderTraversal(TreeNode node,int level){
        if (levels.size() == level) {
            // start the current level
            levels.add(new ArrayList<Integer>());
        }
            // 填充数据
            levels.get(level).add(node.data);

            if (node.leftChild != null){
                levelOrderTraversal(node.leftChild,level+1);
            }
            if (node.rightChild != null){
                levelOrderTraversal(node.rightChild,level+1);
            }

        System.out.println("levels = " + levels);
    }


    public static void levelOrderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        levelOrderTraversal(root,0);
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println("前序遍历");
        preOrderTraveralWithStack(node);
        System.out.println("中序");
        inOrderTraveralWithStack(node);
        System.out.println("后序");
        postOrderBinaryTreeWithStack(node);
        System.out.println("层序遍历");
        levelOrderTraversalWithQueue(node);
        System.out.println("层序遍历--2");
        levelOrderTraversal(node);

    }
   
}
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

后序遍历： 使用一个反向栈
层序遍历： 使用队列，将子节点offer()进去就出队