【笔记】Java实现二叉树遍历以及常用算法

发表于 | 分类于

[笔记系列文章说明]: 该类型的文章是笔者学习过程中整理的学习笔记.

分类

常用二叉树有:
完全二叉树,平衡二叉树,红黑树,满二叉树等

二叉树有4种遍历方式

  1. 前序遍历:

    首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

  2. 中序遍历:

    首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

  3. 后序遍历:

    首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

  4. 层次遍历:

    即按照层次访问，访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同,通常先左后右）

    CODE

    先抽象出树实体
    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
    package test;

    /**
     * 树的模型
     *
     * @author lxz
     *
     */
    public class Tree {
        private Tree leftTree;// 左子树
        private Tree rightTree;// 右子树
        private Object data;// 节点数据

        public Tree() {
        }

        public Tree(Object data) {
            this.data = data;
        }

        /*
         * 求data所对应结点的层数，
         * 如果对象不在树中,结果返回-1;
         * 否则结果返回该对象在树中所处的层次,
         * 规定根节点为第一层
         */
        public int level(Object data) {
            int leftLevel, rightLevel;
            if (this == null)
                return -1;
            if (data == this.data)
                return 1;
            leftLevel = leftTree == null ? -1 : leftTree.level(data);
            rightLevel = rightTree == null ? -1 : rightTree.level(data);
            if (leftLevel < 0 && rightLevel < 0)
                return -1;
            return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1;
        }

        /*
         *  将树中的每个节点的孩子对换位置
         */
        public void exChange() {
            if (this == null)
                return;
            if (leftTree != null)
                leftTree.exChange();
            if (rightTree != null)
                rightTree.exChange();
            Tree temp = leftTree;
            leftTree = rightTree;
            rightTree = temp;
        }


        public Tree getLeftTree() {
            return leftTree;
        }

        public void setLeftTree(Tree leftTree) {
            this.leftTree = leftTree;
        }

        public Tree getRightTree() {
            return rightTree;
        }

        public void setRightTree(Tree rightTree) {
            this.rightTree = rightTree;
        }

        public Object getData() {
            return data;
        }

        public void setData(Object data) {
            this.data = data;
        }

    }
再写遍历树的各种算法
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
package test;

import java.util.Stack;

public class TreeUtil {

    /*
     * 先序遍历二叉树-递归
     *
     * @param tree
     */
    public static void preOrder(Tree tree) {
        if (tree != null) {
            System.out.print(tree.getData().toString());
            preOrder(tree.getLeftTree());
            preOrder(tree.getRightTree());
        }
    }

    /*
     * 先序遍历二叉树-后进先出堆栈
     *
     * @param tree
     */
    public static void stackPreOrder(Tree tree) {
        Stack<Tree> stack = new Stack<Tree>();
        if (tree != null) {
            stack.push(tree);// 放入本
            while (!stack.isEmpty()) {
                tree = stack.pop();
                System.out.print(tree.getData());
                if (tree.getRightTree() != null) {
                    stack.push(tree.getRightTree());// 放入右
                }
                if (tree.getLeftTree() != null) {
                    stack.push(tree.getLeftTree());// 放入左
                }
            }
        }
    }

    /*
     * 中序遍历二叉树-递归
     *
     * @param tree
     */
    public static void inOrder(Tree tree) {
        if (tree != null) {
            inOrder(tree.getLeftTree());
            System.out.print(tree.getData());
            inOrder(tree.getRightTree());
        }
    }

    /*
     * 中序遍历二叉树-后进先出堆栈
     *
     * @param tree
     */
    public static void stackInOrder(Tree tree) {
        Stack<Tree> stack = new Stack<Tree>();
        while (tree != null) {
            while (tree != null) {
                if (tree.getRightTree() != null) {
                    stack.push(tree.getRightTree());
                }
                stack.push(tree);
                tree = tree.getLeftTree();
            }
            tree = stack.pop();
            while (!stack.empty() && tree.getRightTree() == null) {
                System.out.print(tree.getData());
                tree = stack.pop();
            }
            System.out.print(tree.getData());
            if (!stack.empty()) {
                tree = stack.pop();
            } else {
                tree = null;
            }
        }
    }

    /*
     * 后序遍历二叉树-递归
     *
     * @param tree
     */
    public static void postOrder(Tree tree) {
        if (tree != null) {
            postOrder(tree.getLeftTree());
            postOrder(tree.getRightTree());
            System.out.print(tree.getData());
        }
    }

    /*
     * 中序遍历二叉树-后进先出堆栈
     *
     * @param tree
     */
    public static void stackPostOrder(Tree tree) {
        Tree tempTree = tree;
        Stack<Tree> stack = new Stack<Tree>();
        while (tree != null) {
            for (; tree.getLeftTree() != null; tree = tree.getLeftTree()) {
                stack.push(tree);
            }
            while (tree != null
                    && (tree.getRightTree() == null || tree.getRightTree() == tempTree)) {
                System.out.print(tree.getData());
                tempTree = tree;
                if (stack.empty()) {
                    return;
                }
                tree = stack.pop();
            }
            stack.push(tree);
            tree = tree.getRightTree();
        }
    }

    /*
     * 层次遍历二叉树
     *
     * @param tree
     */
    public static void layerOrder(Tree tree) {
        Tree[] array = new Tree[100];// 最多遍历100个
        array[0] = tree;
        int front = 0;
        int rear = 1;
        while (front < rear) {
            if (array[front] != null) {
                System.out.print(array[front].getData());
                if (array[front].getLeftTree() != null) {
                    array[rear++] = array[front].getLeftTree();
                }
                if (array[front].getRightTree() != null) {
                    array[rear++] = array[front].getRightTree();
                }
                front++;
            }
        }
    }

    /*
     * 计算树的高度
     *
     * @param tree
     *
     * @return
     */
    public static int height(Tree tree) {
        int leftTreeHeight = 0;
        int rightTreeHeight = 0;
        if (tree != null) {
            leftTreeHeight = height(tree.getLeftTree());
            rightTreeHeight = height(tree.getRightTree());
            return leftTreeHeight > rightTreeHeight ? leftTreeHeight
                    : rightTreeHeight;
        } else {
            return 0;
        }
    }

    /*
     * 求二叉树的结点总数
     *
     * @param tree
     *
     * @return
     */
    public static int nodes(Tree tree) {
        if (tree == null)
            return 0;
        else {
            int left = nodes(tree.getLeftTree());
            int right = nodes(tree.getRightTree());
            return left + right + 1;
        }
    }

    /*
     * 求二叉树叶子节点的总数
     */
    public static int leaf(Tree tree) {
        if (tree == null)
            return 0;
        else {
            int left = leaf(tree.getLeftTree());
            int right = leaf(tree.getRightTree());
            if (tree.getLeftTree() == null && tree.getRightTree() == null)
                return left + right + 1;
            else
                return left + right;

        }
    }

    /*
     * 求二叉树父节点个数
     *
     * @param tree
     *
     * @return
     */
    public static int fatherNodes(Tree tree) {
        if (tree == null
                || (tree.getLeftTree() == null && tree.getRightTree() == null))
            return 0;
        else {
            int left = fatherNodes(tree.getLeftTree());
            int right = fatherNodes(tree.getRightTree());
            return left + right + 1;
        }
    }

    /*
     * 求只有一个孩子结点的父节点个数
     */
    public static int oneChildFather(Tree tree) {
        int left, right;
        if (tree == null
                || (tree.getRightTree() == null && tree.getLeftTree() == null))
            return 0;
        else {
            left = oneChildFather(tree.getLeftTree());
            right = oneChildFather(tree.getRightTree());
            if ((tree.getLeftTree() != null && tree.getRightTree() == null)
                    || (tree.getLeftTree() == null && tree.getRightTree() != null))
                return left + right + 1;
            else
                return left + right;/* 加1是因为要算上根节点 */
        }
    }

    /*
     * 求二叉树只拥有左孩子的父节点总数
     */
    public static int leftChildFather(Tree tree) {
        if (tree == null)
            return 0;
        else {
            int left = leftChildFather(tree.getLeftTree());
            int right = leftChildFather(tree.getRightTree());
            if ((tree.getLeftTree() != null && tree.getRightTree() == null))
                return left + right + 1;
            else
                return left + right;
        }
    }

    /*
     * 求二叉树只拥有右孩子的结点总数
     */
    public static int rightChildFather(Tree tree) {
        if (tree == null || tree.getRightTree() == null)
            return 0;
        else {
            int left = rightChildFather(tree.getLeftTree());
            int right = rightChildFather(tree.getRightTree());
            if (tree.getLeftTree() == null && tree.getRightTree() != null)
                return left + right + 1;
            else
                return left + right;
        }
    }

    /*
     * 计算有两个节点的父节点的个数
     */
    public static int doubleChildFather(Tree tree) {
        int left, right;
        if (tree == null)
            return 0;
        else {
            left = doubleChildFather(tree.getLeftTree());
            right = doubleChildFather(tree.getRightTree());
            if (tree.getLeftTree() != null && tree.getRightTree() != null)
                return (left + right + 1);/* 加1是因为要算上根节点 */
            else
                return (left + right);
        }
    }

    /*
     *  递归求所有结点的和
     */
    public static int getSumByRecursion(Tree tree) {
        if (tree == null) {
            return 0;
        } else {
            int left = getSumByRecursion(tree.getLeftTree());
            int right = getSumByRecursion(tree.getRightTree());
            return Integer.parseInt(tree.getData().toString()) + left + right;
        }
    }

    /*
     *  非递归求二叉树中所有结点的和
     */
    public static int getSumByNoRecursion(Tree tree) {
        Stack<Tree> stack = new Stack<Tree>();
        int sum = 0;
        if (tree != null) {
            stack.push(tree);
            while (!stack.isEmpty()) {
                tree = stack.pop();
                sum += Integer.parseInt(tree.getData().toString());
                if (tree.getLeftTree() != null)
                    stack.push(tree.getLeftTree());
                if (tree.getRightTree() != null)
                    stack.push(tree.getRightTree());
            }
        }
        return sum;
    }

}
Test
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
package test;

public class TreeTest {

    public static void main(String[] args) {
        //根节点是A
        Tree treeA = new Tree("A");
        Tree treeB = new Tree("B");
        Tree treeC = new Tree("C");
        Tree treeD = new Tree("D");
        Tree treeE = new Tree("E");
        Tree treeF = new Tree("F");
        Tree treeG = new Tree("G");
        Tree treeH = new Tree("H");
        Tree treeI = new Tree("I");
        treeA.setLeftTree(treeB);
        treeA.setRightTree(treeC);
        treeB.setLeftTree(treeD);
        treeB.setRightTree(treeE);
        treeE.setRightTree(treeF);
        treeF.setLeftTree(treeG);
        treeG.setLeftTree(treeH);
        treeH.setLeftTree(treeI);
        System.out.println("先序遍历二叉树-递归:");
        TreeUtil.preOrder(treeA);
        System.out.println("\n先序遍历二叉树-堆栈:");
        TreeUtil.stackPreOrder(treeA);
        System.out.println("\n中序遍历二叉树-递归:");
        TreeUtil.inOrder(treeA);
        System.out.println("\n中序遍历二叉树-堆栈:");
        TreeUtil.stackInOrder(treeA);
        System.out.println("\n后序遍历二叉树-递归:");
        TreeUtil.postOrder(treeA);
        System.out.println("\n层次遍历二叉树:");
        TreeUtil.layerOrder(treeA);
    }
}

结果


先序遍历二叉树-递归:
ABDEFGHIC
先序遍历二叉树-堆栈:
ABDEFGHIC
中序遍历二叉树-递归:
DBEIHGFAC
中序遍历二叉树-堆栈:
DBEIHGFAC
后序遍历二叉树-递归:
DIHGFEBCA
层次遍历二叉树:
ABCDEFGHI