XMD

无语

算法基础13：数结构

发表于 更新于 分类于 ，
本文字数： 34k 阅读时长 ≈ 30 分钟

基础部分

为什么要学习树结构

  1. 数组存储方式的分析

    优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检素速度。

    缺点：如果要检素具体某个值，或者插入值（按一定顺序）会整体移动，效率较低。

  2. 链式存储方式的分析

    优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

    缺点：在进行检素时，效率仍然较低，比如（检素某个值，需要从头节点开始遍历）

  3. 树存储方式的分析

    能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree),既可以保证数据的检索速度，同时也可以保证数据的插入，别除，修改的速度。
    案例：[7,3,10,1,5,9,12]

常用术语

二叉树

二叉树的遍历

需求说明

二叉树的遍历思路分析

前序遍历、中序遍历、后序遍历 代码

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
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "无用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
//        HeroNode node5 = new HeroNode(5, "关胜");

        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
//        node3.setLeft(node5);

        binaryTree.setRoot(node1);


        System.out.println("前序遍历");
        binaryTree.preOrder();

        System.out.println("中序遍历");
        binaryTree.infixOrder();

        System.out.println("中序遍历");
        binaryTree.postOrder();
    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    //前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //先输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //后序遍历方法
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //先输出父节点
        System.out.println(this);
    }

}

输出结果

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='无用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='林冲'}
中序遍历
HeroNode{no=2, name='无用'}
HeroNode{no=1, name='宋江'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='林冲'}
中序遍历
HeroNode{no=2, name='无用'}
HeroNode{no=4, name='林冲'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=1, name='宋江'}

二叉树的查找

需求说明

思路分析

前序查找、中序查找、后序查找 代码

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
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "无用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
//        HeroNode node5 = new HeroNode(5, "关胜");

        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
//        node3.setLeft(node5);

        binaryTree.setRoot(node1);

//
//        System.out.println("前序遍历");
//        binaryTree.preOrder();
//
//        System.out.println("中序遍历");
//        binaryTree.infixOrder();
//
//        System.out.println("中序遍历");
//        binaryTree.postOrder();




        System.out.println("前序遍历");
        HeroNode heroNode1 = binaryTree.preOrderSearch(2);
        System.out.println(heroNode1);

        System.out.println("中序遍历");
        HeroNode heroNode2 =  binaryTree.infixOrderSearch(3);
        System.out.println(heroNode2);

        System.out.println("中序遍历");
        HeroNode heroNode3 = binaryTree.postOrderSearch(4);
        System.out.println(heroNode3);

    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }


    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    //前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //先输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //后序遍历方法
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //先输出父节点
        System.out.println(this);
    }


    /**
     * 前序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //1,则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2,如果左递归前序查找，找到结点，则返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //1,左递归前序查找，找到结点，则返回，否继续判断，
        //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode infixOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }


        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        return resNode;
    }

    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode postOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        if (resNode != null) {
            return resNode;
        }

        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

}

二叉树的删除结点

需求说明

思路分析

删除结点 代码

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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "无用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");

        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        binaryTree.setRoot(node1);

//
//        System.out.println("前序遍历");
//        binaryTree.preOrder();
//
//        System.out.println("中序遍历");
//        binaryTree.infixOrder();
//
//        System.out.println("中序遍历");
//        binaryTree.postOrder();



//        System.out.println("前序遍历");
//        HeroNode heroNode1 = binaryTree.preOrderSearch(2);
//        System.out.println(heroNode1);
//
//        System.out.println("中序遍历");
//        HeroNode heroNode2 = binaryTree.infixOrderSearch(3);
//        System.out.println(heroNode2);
//
//        System.out.println("中序遍历");
//        HeroNode heroNode3 = binaryTree.postOrderSearch(4);
//        System.out.println(heroNode3);

        System.out.println("删除前");
        binaryTree.infixOrder();
        binaryTree.delOrder(3);
        System.out.println("删除后");
        binaryTree.infixOrder();

    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void delOrder(int no) {
        if (this.root != null) {
            this.root.delNode(no);
        } else {
            System.out.println("二叉树为空，无法删除");
        }
    }


    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }


    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }


    //递归删除结点
    //1,如果删除的节点是叶子节点，则侧删除该节点
    //2,如果删除的节点是非叶子节点，则删除该子树
    public void delNode(int no) {
        //思路
        /*
        1。因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结，
        2。如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.1eft=null;并且就返回（结束递归删除）
        3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=ul1;并且就返回（结束递归删除）
        4。如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
        5。如果第4步也没有删除结点，则应当向右子树进行递归删除，
      */
        //2如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this,1eft=nu11;并且就返回（结束递归删除）
        if (this.left != null && this.left.no == no){
            this.left = null;
            return;
        }

        //3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=nu11;并且就返回（结束递归删除）
        if (this.right != null && this.right.no == no){
            this.right = null;
            return;
        }
        //4,我们就需要向左子树进行递归删除
        if (this.left != null){
            this.left.delNode(no);
        }

        //5
        if (this.right != null){
            this.right.delNode(no);
        }
    }


    //前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //先输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //后序遍历方法
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //先输出父节点
        System.out.println(this);
    }


    /**
     * 前序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //1,则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2,如果左递归前序查找，找到结点，则返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //1,左递归前序查找，找到结点，则返回，否继续判断，
        //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode infixOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }


        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        return resNode;
    }

    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode postOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        if (resNode != null) {
            return resNode;
        }

        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

}

顺序存储二叉树

要求：

  1. 右图的二叉树的结点，要求以数组的方式来存放arr:[1,2,3,4,5,6,6]
  2. 要求在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

代码实现 (前序遍历)

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
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};

        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder();//1 2 4 5 3 6 7
    }
}

//编写一个ArrayBinaryTree,实现顺序存储二叉树遍历
class ArrBinaryTree {
    //存储数据节点的数据
    private int[] arr;

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder(){
        this.preOrder(0);
    }


    /**
     * 编写一个方法，完成顺序存储二叉树的前序遍历
     *
     * @param index 数组下标
     */
    public void preOrder(int index) {
        //如果数组为空，或者arr,length=0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }

        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if ((2 * index + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        //向右递归遍历
        if ((2 * index + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }
}

中序遍历、后序遍历 就不写了

顺序存储二叉树应用实例
八大排序算法中的堆排序，就会使用到顺序存储二叉树，关于堆排序，我们放在<<树结构实际应用>>章节讲解。

线索化二叉树

问题分析：

  1. 当我们对上面的二叉树进行中序遍历时，数列为8,3,10,1,6,14}
  2. 但是6,8,10,14这几个节点的左右指针，并没有完全的利用上
  3. 如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点怎么办？
  4. 解决方案 线索二又树

代码实现（比较难理解）

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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
public class TreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node3 = new HeroNode(3, "吴用");
        HeroNode node6 = new HeroNode(6, "卢俊义");
        HeroNode node8 = new HeroNode(8, "林冲");
        HeroNode node10 = new HeroNode(10, "关胜");
        HeroNode node14 = new HeroNode(14, "武松");

        node1.setLeft(node3);
        node1.setRight(node6);

        node3.setLeft(node8);
        node3.setRight(node10);

        node6.setLeft(node14);

        TreadedBinaryTree binaryTree = new TreadedBinaryTree();
        binaryTree.setRoot(node1);
        binaryTree.treadedNodes();

        HeroNode node10Left = node10.getLeft();
        System.out.println("node10 前驱：" + node10Left);

        HeroNode node10Right = node10.getRight();
        System.out.println("node10 后驱：" + node10Right);
    }
}

class TreadedBinaryTree {
    private HeroNode root;

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre总是保留前一个结点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void treadedNodes() {
        this.treadedNodes(root);
    }


    /**
     * //编写对二叉树进行中序线索化的方法
     *
     * @param node 就是当前需要线索化的结点
     */
    public void treadedNodes(HeroNode node) {
        //如果node==nu1ll,不能线素化
        if (node == null) {
            return;
        }
        ///(一)先线素化左子树
        treadedNodes(node.getLeft());

        //(二)线素化当前结点[有难度]
        //处理当前结点的前驱结点
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        //!!!每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;

        //(三)在线索化右子树
        treadedNodes(node.getRight());
    }


    public void delOrder(int no) {
        if (this.root != null) {
            this.root.delNode(no);
        } else {
            System.out.println("二叉树为空，无法删除");
        }
    }


    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }


    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    //说明
    //1。如果1 eftType=0表示指向的是左子树，如果1则表示指向前驱结点
    //2,如果rightType=0表示指向是右子树，如果1表示指向后继结点
    private int leftType;
    private int rightType;

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }


    //递归删除结点
    //1,如果删除的节点是叶子节点，则侧删除该节点
    //2,如果删除的节点是非叶子节点，则删除该子树
    public void delNode(int no) {
        //思路
        /*
        1。因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结，
        2。如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.1eft=null;并且就返回（结束递归删除）
        3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=ul1;并且就返回（结束递归删除）
        4。如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
        5。如果第4步也没有删除结点，则应当向右子树进行递归删除，
      */
        //2如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this,1eft=nu11;并且就返回（结束递归删除）
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }

        //3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=nu11;并且就返回（结束递归删除）
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //4,我们就需要向左子树进行递归删除
        if (this.left != null) {
            this.left.delNode(no);
        }

        //5
        if (this.right != null) {
            this.right.delNode(no);
        }
    }


    //前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //先输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //后序遍历方法
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //先输出父节点
        System.out.println(this);
    }


    /**
     * 前序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //1,则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2,如果左递归前序查找，找到结点，则返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //1,左递归前序查找，找到结点，则返回，否继续判断，
        //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode infixOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }


        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        return resNode;
    }

    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode postOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        if (resNode != null) {
            return resNode;
        }

        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

}

遍历线索化二叉树

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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
/**
 * 线索化二叉树
 *
 * @author：XMD
 * @date: 13.9.22
 */
public class TreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node3 = new HeroNode(3, "吴用");
        HeroNode node6 = new HeroNode(6, "卢俊义");
        HeroNode node8 = new HeroNode(8, "林冲");
        HeroNode node10 = new HeroNode(10, "关胜");
        HeroNode node14 = new HeroNode(14, "武松");

        node1.setLeft(node3);
        node1.setRight(node6);

        node3.setLeft(node8);
        node3.setRight(node10);

        node6.setLeft(node14);

        TreadedBinaryTree binaryTree = new TreadedBinaryTree();
        binaryTree.setRoot(node1);
        binaryTree.treadedNodes();

        HeroNode node10Left = node14.getLeft();
        System.out.println("node10 前驱：" + node10Left);

        HeroNode node10Right = node14.getRight();
        System.out.println("node10 后驱：" + node10Right);

        System.out.println("使用线索化的遍历遍历线索化二叉树");
        binaryTree.treadedList();


    }
}

class TreadedBinaryTree {
    private HeroNode root;

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre总是保留前一个结点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void treadedNodes() {
        this.treadedNodes(root);
    }


    //遍历线索化二叉树的方法
    public void treadedList() {
        //定义一个变量，存储当前遍历的结点，从root开始
        HeroNode node = root;
        while (node != null) {
            //循环的找到1 eftType==1的结点，第一个找到就是8结点
            //后面随着遍历而变化，因为当1 eftType==1时，说明该结点是按照线索化
            //处理后的有效结点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前这个结点
            System.out.println(node);
            //如果当前结点的右指针指向的是后继结点，就一直输出
            while (node.getRightType() == 1) {
                //获取到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.getRight();
        }
    }


    /**
     * //编写对二叉树进行中序线索化的方法
     *
     * @param node 就是当前需要线索化的结点
     */
    public void treadedNodes(HeroNode node) {
        //如果node==nu1ll,不能线素化
        if (node == null) {
            return;
        }
        ///(一)先线素化左子树
        treadedNodes(node.getLeft());

        //(二)线素化当前结点[有难度]
        //处理当前结点的前驱结点
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        //!!!每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;

        //(三)在线索化右子树
        treadedNodes(node.getRight());
    }


    public void delOrder(int no) {
        if (this.root != null) {
            this.root.delNode(no);
        } else {
            System.out.println("二叉树为空，无法删除");
        }
    }


    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }


    public HeroNode preOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.preOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.infixOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode heroNode = null;
        if (this.root != null) {
            heroNode = this.root.postOrderSearch(no);
        } else {
            System.out.println("二叉树为空，无法查找");
        }
        return heroNode;
    }

}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    //说明
    //1。如果1 eftType=0表示指向的是左子树，如果1则表示指向前驱结点
    //2,如果rightType=0表示指向是右子树，如果1表示指向后继结点
    private int leftType;
    private int rightType;

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }


    //递归删除结点
    //1,如果删除的节点是叶子节点，则侧删除该节点
    //2,如果删除的节点是非叶子节点，则删除该子树
    public void delNode(int no) {
        //思路
        /*
        1。因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结，
        2。如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.1eft=null;并且就返回（结束递归删除）
        3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=ul1;并且就返回（结束递归删除）
        4。如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
        5。如果第4步也没有删除结点，则应当向右子树进行递归删除，
      */
        //2如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this,1eft=nu11;并且就返回（结束递归删除）
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }

        //3,如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this,right=nu11;并且就返回（结束递归删除）
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //4,我们就需要向左子树进行递归删除
        if (this.left != null) {
            this.left.delNode(no);
        }

        //5
        if (this.right != null) {
            this.right.delNode(no);
        }
    }


    //前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历方法
    public void infixOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //先输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //后序遍历方法
    public void postOrder() {
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //先输出父节点
        System.out.println(this);
    }


    /**
     * 前序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        //1,则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2,如果左递归前序查找，找到结点，则返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //1,左递归前序查找，找到结点，则返回，否继续判断，
        //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }


    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode infixOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }


        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        return resNode;
    }

    /**
     * 中序查找
     *
     * @param no 查找条件 编号
     * @return 如果返回节点信息 没有找到返回null
     */
    public HeroNode postOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }

        if (resNode != null) {
            return resNode;
        }

        //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

}

-------------本文结束感谢您的阅读-------------

相关文章