二叉树的各种操作(递归和非递归遍历,树深度,结点个数等等)

Posted on | In |
Words count in article: 3.7k

二叉树的各种操作(递归和非递归遍历,树深度,结点个数等等)

二叉树建立

先给出结点结构: 

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

    public Node(int val) {
        this.val = val;
    }
}

两种建立方式:

  • 可以根据二叉树根节点和左右子结点的下标关系递归建立二叉树，层次输入二叉树结点；
  • 也可以使用输入流前序建立二叉树(注意空树要输入-1)；

1、根据下标关系

1
2
3
4
5
6
7
8
9
// given a arr to build
static Node createTree(int arr[], int i) {
    if (i >= arr.length || arr[i] == -1)
        return null;
    Node root = new Node(arr[i]);
    root.left = createTree(arr, 2 * i + 1);
    root.right = createTree(arr, 2 * i + 2);
    return root;
}

大致过程如下:
这里写图片描述

2、前序输入(cin)建立

1
2
3
4
5
6
7
8
9
10
11
// cin method	
static Node buildTree(Scanner cin) {
    Node root = null;
    int data = cin.nextInt();
    if (data != -1) {
        root = new Node(data);
        root.left = buildTree(cin);
        root.right = buildTree(cin);
    }
    return root;
}

过程如下:
这里写图片描述

前序遍历

1、递归前序

1
2
3
4
5
6
7
static void preOrder(Node T) {
    if (T == null)
        return;
    System.out.print(T.val + " ");
    preOrder(T.left);
    preOrder(T.right);
}

2、非递归前序

前序遍历顺序为: 根结点->左子树->右子树，所以对于正在访问的根结点，可以直接访问，访问完之后，按照相同的方式访问左子树，再访问右子树，过程如下 :

  • 如果当前节点p不为空，访问结点p，并将结点p入栈，并继续访问左子树(直到左子树为空)；
  • 否则将栈顶元素出栈，并访问栈顶的元素的右子树；
  • 直到栈为空且p为空，循环结束。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void iterativePre(Node root) {
    Stack<Node> s = new Stack<>();
    Node p = root;
    while (!s.empty() || p != null) {
        if (p != null) {//也可以写一个while循环，直到左子树为空
            s.push(p);
            System.out.print(p.val + " ");
            p = p.left;
        } else {
            p = s.pop();
            p = p.right;
        }
    }
}

也可以将上面的一直访问到左子树为空写成一个while循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
static void iterativePre2(Node root) {
    Stack<Node> s = new Stack<>();
    Node p = root;
    while (!s.empty() || p != null) {
        while (p != null) { // while循环，直到左子树为空
            s.push(p);
            System.out.print(p.val + " ");
            p = p.left;
        }
        p = s.pop();
        p = p.right;
    }
}

还有另外一种写法是:　

  • 先把根节点入栈，然后每次出栈一个元素，先访问这个元素，然后如果它的右子树存在，就入栈，如果它的左子树存在也入栈；
  • 为什么要先入右子树呢，因为，前序遍历是中->左->右，而栈可以逆序，所以先右再左；

这个方法在后续遍历的双栈法中有体现，那个只是这个稍微的修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void iterativePre3(Node root) {
    if (root == null)
        return;
    Node p = root;
    Stack<Node> stack = new Stack<>();
    stack.add(p);
    while (!stack.isEmpty()) {
        p = stack.pop();
        System.out.print(p.val + " ");
        if (p.right != null)// 先右再左即可
            stack.push(p.right);
        if (p.left != null)
            stack.push(p.left);
    }
}

中序遍历

1、递归中序

1
2
3
4
5
6
7
static void inOrder(Node T) {
    if (T == null)
        return;
    inOrder(T.left);
    System.out.print(T.val + " ");
    inOrder(T.right);
}

2、非递归中序

中序遍历 : 左子树->根->右子树，过程如下：

  • 当前节点不空!= null，压入栈中(和前序遍历不同的是，不需要打印)，当前节点向左；
  • 当前节点为空== null，从栈中拿出一个并且打印(在这里打印) ，当前节点向右；

直到栈为空且p为空，循环结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 1)、当前节点不空(!=null)，压入栈中(和前序遍历不同的是，不需要打印)，当前节点向左；
* 2)、当前节点为空(==null)，从栈中拿出一个并且打印(在这里打印) ，当前节点向右；
*/
static void iterativeIn(Node root) {
    if (root == null)
        return;
    Stack<Node> s = new Stack<>();
    Node p = root;
    while (!s.empty() || p != null) {
        if (p != null) {
            s.push(p);
            p = p.left;
        } else {
            p = s.pop();
            System.out.print(p.val + " "); //在这里打印
            p = p.right;
        }
    }
}

同理，那个一直访问左孩子那里也可以改成whlie:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void iterativeIn2(Node root) {
    if (root == null)
        return;
    Stack<Node> s = new Stack<>();
    Node p = root;
    while (!s.empty() || p != null) {
        while (p != null) { //这里改成while
            s.push(p);
            p = p.left;
        }
        p = s.pop();
        System.out.print(p.val + " "); //在这里打印
        p = p.right;
    }
}

后序遍历

1、递归后序

1
2
3
4
5
6
7
static void postOrder(Node T) {
    if (T == null)
        return;
    postOrder(T.left);
    postOrder(T.right);
    System.out.print(T.val + " ");
}

2、非递归后序

1)、双栈法

这个其实就是非递归前序(iterativePre3)的稍微一点改进。

  • 首先，前序遍历入栈(iterativePre3)的顺序是先 右　再左；
  • 这时，我们可以做到反过来先　左　再右，这样遍历的顺序可以做到 **”中右左”**，而后续遍历是 “左右中”，正好是前面那个的相反，所以我们再使用一个栈反转保存即可；

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 非递归后续1(双栈法解决非递归后续)
* 后续遍历是要实现　　　左->右->中
* 这个方法和前序遍历的第二种方法　只是多了一个栈而已
* 因为　前序遍历是  中->左->右　　压栈顺序是 右->左
* 这样，我们就很容易实现　中->右->左遍历　　压栈顺序是　左->右
* 而后续遍历是要实现  左->右->中，
* 我们把上面的　　中右左　压入到另一个栈中　就实现了　左右中
*/
static void iterativePos(Node root) {
    Stack<Node> s = new Stack<>(), s2 = new Stack<>();
    Node p;
    s.push(root);
    while (!s.empty()) {
        p = s.pop();
        s2.push(p);
        if (p.left != null) s.push(p.left); //这里是先左再右  (非递归前序是先右再左)
        if (p.right != null) s.push(p.right);
    }
    while (!s2.empty())
        System.out.print(s2.pop().val + " ");
}

2)、设置pre结点

过程如下:

  • 对于任一结点p，先将其入栈；
  • 可以访问的情况: ①若p不存在左孩子和右孩子，则可以直接访问它。②或者p存在左孩子或者右孩子，但是左孩子和右孩子都已经被访问过了，则也可以直接访问该结点；
  • 若非上述两种情况，则将右孩子和左孩子依次入栈。这样可以保证每次取栈顶元素时，左孩子在右孩子前面被访问，根结点在左孩子和右孩子访问之后被访问；

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*** 非递归后续2(设置pre结点) */
static void iterativePos2(Node root) {
    Node cur, pre = null;
    Stack<Node> s = new Stack<>();
    s.push(root);
    while (!s.empty()) { 
        cur = s.peek();
        // 两种可以访问的情况
        if ((cur.left == null && cur.right == null) ||
            ((pre != null) && (pre == cur.left || pre == cur.right))) {
            System.out.print(cur.val + " ");
            s.pop();
            pre = cur;
        } else {
            if (cur.right != null) s.push(cur.right);
            if (cur.left != null) s.push(cur.left);
        }
    }
}

层次遍历

很简单。利用队列BFS即可，每次访问完p，若左右孩子存在，则入队，直至队空；

1
2
3
4
5
6
7
8
9
10
11
12
static void levelOrder(Node root) {
    if (root == null)
        return;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node now = queue.poll();
        System.out.print(now.val + " ");
        if (now.left != null) queue.add(now.left);
        if (now.right != null) queue.add(now.right);
    }
}

寻找树中有没有值为x的结点

递归条件有两个，一个是为空代表没找到，找到了的话直接返回，否则递归查找左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
//查找某个值为x的结点
static Node search(Node T, int x) {
    if (T == null)
        return null;
    if (T.val == x)
        return T;
    else {
        if (search(T.left, x) == null)
            return search(T.right, x);
        else
            return search(T.left, x);
    }
}

统计树中结点的个数

树中结点的个数等于根节点(1) + 左子树结点个数 + 右子树的个数，递归求解即可。

1
2
3
4
5
6
7
//统计结点个数
static int count(Node T) {
    if (T == null)
        return 0;
    else
        return count(T.left) + count(T.right) + 1;
}

计算树的高度

也是递归求解，左右子树的高度中的比较高的加上根节点就是树的高度。

1
2
3
4
5
6
//计算二叉树的深度
static int depth(Node T) {
    if (T == null)
        return 0;
    return Math.max(depth(T.left), depth(T.right)) + 1;
}

判断两棵树是不是相等

也是递归求解，两棵树相等，既要根节点的值相等，而且左右子树也要相等。

1
2
3
4
5
6
7
8
9
//判断两棵树是不是相等
static boolean is_SameTree(Node T1, Node T2) {
    if (T1 == null && T2 == null)
        return true;
    else {
        return T1 != null && T2 != null && T1.val == T2.val
            && is_SameTree(T1.left, T2.left) && is_SameTree(T1.right, T2.right);
    }
}

完整测试代码

完整的测试代码，这里输入的样例树(就是建树的时候那个例子)如下:

这里写图片描述

代码:

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
import java.io.BufferedInputStream;
import java.util.*;

public class BinaryTree {

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

        public Node(int val) {
            this.val = val;
        }
    }

    // given a arr to build
    static Node createTree(int arr[], int i) {
        if (i >= arr.length || arr[i] == -1)
            return null;
        Node root = new Node(arr[i]);
        root.left = createTree(arr, 2 * i + 1);
        root.right = createTree(arr, 2 * i + 2);
        return root;
    }

    // cin method	
    static Node buildTree(Scanner cin) {
        Node root = null;
        int data = cin.nextInt();
        if (data != -1) {
            root = new Node(data);
            root.left = buildTree(cin);
            root.right = buildTree(cin);
        }
        return root;
    }

    static void preOrder(Node T) {
        if (T == null)
            return;
        System.out.print(T.val + " ");
        preOrder(T.left);
        preOrder(T.right);
    }

    static void iterativePre(Node root) {
        Stack<Node> s = new Stack<>();
        Node p = root;
        while (!s.empty() || p != null) {
            if (p != null) {
                s.push(p);
                System.out.print(p.val + " ");
                p = p.left;
            } else {
                p = s.pop();
                p = p.right;
            }
        }
    }


    static void iterativePre2(Node root) {
        Stack<Node> s = new Stack<>();
        Node p = root;
        while (!s.empty() || p != null) {
            while (p != null) { // while循环，直到左子树为空
                s.push(p);
                System.out.print(p.val + " ");
                p = p.left;
            }
            p = s.pop();
            p = p.right;
        }
    }

    /**
     * 理解 :  push右子树，再push左子树，这样的话弹栈的时候就是先访问左子树，再右子树
     */
    static void iterativePre3(Node root) {
        if (root == null)
            return;
        Node p = root;
        Stack<Node> stack = new Stack<>();
        stack.add(p);
        while (!stack.isEmpty()) {
            p = stack.pop();
            System.out.print(p.val + " ");
            if (p.right != null)
                stack.push(p.right);
            if (p.left != null)
                stack.push(p.left);
        }
    }


    static void inOrder(Node T) {
        if (T == null)
            return;
        inOrder(T.left);
        System.out.print(T.val + " ");
        inOrder(T.right);
    }

    /**
     * 1)、当前节点不空(!=null)，压入栈中(和前序遍历不同的是，不需要打印)，当前节点向左；
     * 2)、当前节点为空(==null)，从栈中拿出一个并且打印(在这里打印) ，当前节点向右；
     */
    static void iterativeIn(Node root) {
        if (root == null)
            return;
        Stack<Node> s = new Stack<>();
        Node p = root;
        while (!s.empty() || p != null) {
            if (p != null) {
                s.push(p);
                p = p.left;
            } else {
                p = s.pop();
                System.out.print(p.val + " "); //在这里打印
                p = p.right;
            }
        }
    }

    static void iterativeIn2(Node root) {
        if (root == null)
            return;
        Stack<Node> s = new Stack<>();
        Node p = root;
        while (!s.empty() || p != null) {
            while (p != null) { //这里改成while
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            System.out.print(p.val + " "); //在这里打印
            p = p.right;
        }
    }


    static void postOrder(Node T) {
        if (T == null)
            return;
        postOrder(T.left);
        postOrder(T.right);
        System.out.print(T.val + " ");
    }

    /**
     * 非递归后续1(双栈法解决非递归后续)
     * 后续遍历是要实现　　　左->右->中
     * 这个方法和前序遍历的第二种方法　只是多了一个栈而已
     * 因为　前序遍历是  中->左->右　　压栈顺序是 右->左
     * 这样，我们就很容易实现　中->右->左遍历　　压栈顺序是　左->右
     * 而后续遍历是要实现  左->右->中，
     * 我们把上面的　　中右左　压入到另一个栈中　就实现了　左右中
     */
    static void iterativePos(Node root) {
        Stack<Node> s = new Stack<>(), s2 = new Stack<>();
        Node p;
        s.push(root);
        while (!s.empty()) {
            p = s.pop();
            s2.push(p);
            if (p.left != null) s.push(p.left); //这里是先左再右  (非递归前序是先右再左)
            if (p.right != null) s.push(p.right);
        }
        while (!s2.empty())
            System.out.print(s2.pop().val + " ");
    }


    /*** 非递归后续2(设置pre结点) */
    static void iterativePos2(Node root) {
        Node cur, pre = null;
        Stack<Node> s = new Stack<>();
        s.push(root);
        while (!s.empty()) {
            cur = s.peek();
            // 两种可以访问的情况
            if ((cur.left == null && cur.right == null) ||
                    ((pre != null) && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.val + " ");
                s.pop();
                pre = cur;
            } else {
                if (cur.right != null) s.push(cur.right);
                if (cur.left != null) s.push(cur.left);
            }
        }
    }

    static void levelOrder(Node root) {
        if (root == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            System.out.print(now.val + " ");
            if (now.left != null) queue.add(now.left);
            if (now.right != null) queue.add(now.right);
        }
    }

    //查找某个值为x的结点
    static Node search(Node T, int x) {
        if (T == null)
            return null;
        if (T.val == x)
            return T;
        else {
            if (search(T.left, x) == null)
                return search(T.right, x);
            else
                return search(T.left, x);
        }
    }

    //统计结点个数
    static int count(Node T) {
        if (T == null)
            return 0;
        else
            return count(T.left) + count(T.right) + 1;
    }

    //计算二叉树的深度
    static int depth(Node T) {
        if (T == null)
            return 0;
        return Math.max(depth(T.left), depth(T.right)) + 1;
    }

    //判断两棵树是不是相等
    static boolean is_SameTree(Node T1, Node T2) {
        if (T1 == null && T2 == null)
            return true;
        else {
            return T1 != null && T2 != null && T1.val == T2.val
                    && is_SameTree(T1.left, T2.left) && is_SameTree(T1.right, T2.right);
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        //		int[] arr = {1,2,3,4,5,6,7,8,-1,9,-1,10,-1,11,-1, -1,-1,-1,-1,-1,-1,-1,-1};
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, -1, 9, -1, 10, -1, 11, -1};
        Node root = createTree(arr, 0);
        //		树结构和上面相同,输入: 1 2 4 8 -1 -1 -1 5 9 -1 -1 -1 3 6 10 -1 -1 -1 7 11 -1 -1 -1
        Node root2 = buildTree(cin);

        System.out.println("-------前序遍历-------");
        preOrder(root);
        System.out.println();
        iterativePre(root);
        System.out.println();
        iterativePre2(root);
        System.out.println();
        iterativePre3(root);

        System.out.println("\n" + "-------中序遍历-------");
        inOrder(root);
        System.out.println();
        iterativeIn(root);
        System.out.println();
        iterativeIn2(root);

        System.out.println("\n" + "-------后序遍历-------");
        postOrder(root);
        System.out.println();
        iterativePos(root);
        System.out.println();
        iterativePos2(root);

        System.out.println("\n" + "-------层次遍历-------");
        levelOrder(root);

        System.out.println("\n" + "------结点个数-------");
        System.out.println(count(root));

        System.out.println("\n" + "------二叉树深度-------");
        System.out.println(depth(root));

        System.out.println("\n" + "-----判断两棵树是不是相同-----");
        System.out.println(is_SameTree(root, root2));

        System.out.println("\n" + "-----寻找树中有没有值为3的结点-----");
        Node Find = search(root, 3);
        if (null == Find)
            System.out.println("没有找到结点");
        else
            System.out.println("这个结点的左右子结点的值是" + Find.left.val + " " + Find.right.val);
    }
}

运行效果如下图:

© 2021 — 2024 true | Site words total count: 328.5k
Theme — NexT.Pisces v5.1.4
0%