Data Structure Binary Tree

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.[1] Some authors allow the binary tree to be the empty set as well.

前言

    二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

二叉树

二叉树介绍:

二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。常见的树有一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。

二叉树特点:

由二叉树定义以及图示分析得出二叉树有以下特点:
1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。
2)左子树和右子树是有顺序的,次序不能任意颠倒。
3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

二叉树图解:


二叉树代码:

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
/**
* @Auther: Arsenal
* @Date: 2020-03-24 19:28
* @Description: 二叉树
*/
public class BinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1, "宋江");
BinaryTree binaryTree = new BinaryTree(root);
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊");
HeroNode node4 = new HeroNode(4, "林冲");
HeroNode node5 = new HeroNode(5, "关胜");
root.setLeftHeroNode(node2);
root.setRightHeroNode(node3);
node3.setRightHeroNode(node4);
node3.setLeftHeroNode(node5);

/* System.out.println("========前序遍历========");
binaryTree.preOrder(root); // 1,2,3,5,4
System.out.println("========中序遍历========");
binaryTree.midOrder(root); // 2,1,5,3,4
System.out.println("========后序遍历========");
binaryTree.posOrder(root); // 2,5,4,3,1*/

/*System.out.println("========前序遍历========");
HeroNode heroNode = binaryTree.preOrderSearch(6);
System.out.println(heroNode);
System.out.println("========中序遍历========");
heroNode = binaryTree.midOrderSearch(5);
System.out.println(heroNode);
System.out.println("========后序遍历========");
heroNode = binaryTree.posOrderSearch(3);
System.out.println(heroNode);*/

binaryTree.preOrder(root);
System.out.println("==========删除节点后==========");
binaryTree.deleteHeroNode(3);
binaryTree.preOrder(root);

}
}

/**
* 二叉树
*/
class BinaryTree {
private HeroNode root;

public BinaryTree(HeroNode root) {
this.root = root;
}

/**
* 前序遍历
* @param root 根节点
*/
public void preOrder(HeroNode root) {
if (root == null) {
System.out.println("该树为空树");
} else {
root.preOrder();
}
}

/**
* 中序遍历
* @param root 根节点
*/
public void midOrder(HeroNode root) {
if (root == null) {
System.out.println("该树为空树");
} else {
root.midOrder();
}
}

/**
* 后序遍历
* @param root 根节点
*/
public void posOrder(HeroNode root) {
if (root == null) {
System.out.println("该树为空树");
} else {
root.posOrder();
}
}

// ===========================================

/**
* 根据编号前序查询节点
* @param no 编号
* @return
*/
public HeroNode preOrderSearch(int no) {
if (root == null) {
System.out.println("该树为空树");
} else {
return root.preOrderSearch(no);
}
return null;
}

/**
* 根据编号中序查询节点
* @param no 编号
* @return
*/
public HeroNode midOrderSearch(int no) {
if (root == null) {
System.out.println("该树为空树");
} else {
return root.midOrderSearch(no);
}
return null;
}

/**
* 根据编号后序查询节点
* @param no 编号
* @return
*/
public HeroNode posOrderSearch(int no) {
if (root == null) {
System.out.println("该树为空树");
} else {
return root.posOrderSearch(no);
}
return null;
}

// ===========================================

/**
* 删除节点
* @param no 节点编号
*/
public void deleteHeroNode(int no) {
if (root != null) {

// 如果删除的是根节点本身,直接置null
if (root.getNo() == no) {
root = null;
} else {
// 递归删除
root.deleteHeroNode(no);
}

} else {
System.out.println("空树无法删除");
}
}
}

/**
* 节点
*/
class HeroNode {
private int no;
private String name;
private HeroNode leftHeroNode;
private HeroNode rightHeroNode;

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

/**
* 前序遍历:先输出父节点,再遍历左子树和右子树
*/
public void preOrder() {
System.out.println(this);
if (this.getLeftHeroNode() != null) {
this.getLeftHeroNode().preOrder();
}

if (this.getRightHeroNode() != null) {
this.getRightHeroNode().preOrder();
}
}

/**
* 中序遍历:先遍历左子树,再输出父节点,再遍历右子树
*/
public void midOrder() {

if (this.getLeftHeroNode() != null) {
this.getLeftHeroNode().midOrder();
}

System.out.println(this);

if (this.getRightHeroNode() != null) {
this.getRightHeroNode().midOrder();
}
}

/**
* 后序遍历:先遍历左子树,再遍历右子树,最后输出父节点
*/
public void posOrder() {
if (this.getLeftHeroNode() != null) {
this.getLeftHeroNode().posOrder();
}

if (this.getRightHeroNode() != null) {
this.getRightHeroNode().posOrder();
}

System.out.println(this);
}

// ======================================

/**
* 根据编号前序查询节点
* @param no 编号
* @return
*/
public HeroNode preOrderSearch(int no) {

HeroNode resHero = null;

if (this.getNo() == no) {
return this;
}

// 向左子树递归查询
if (this.getLeftHeroNode() != null) {
resHero = this.getLeftHeroNode().preOrderSearch(no);
}
// 左子树找到直接返回
if (resHero != null) {
return resHero;
}

// 向右子树递归查询
if (this.getRightHeroNode() != null) {
resHero = this.getRightHeroNode().preOrderSearch(no);
}

return resHero;
}

/**
* 根据编号中序查询节点
* @param no 编号
* @return
*/
public HeroNode midOrderSearch(int no) {

HeroNode resHero = null;

// 向左子树递归查询
if (this.getLeftHeroNode() != null) {
resHero = this.getLeftHeroNode().midOrderSearch(no);
}
// 左子树找到直接返回
if (resHero != null) {
return resHero;
}

// 和当前节点比较,如果是则返回
if (this.getNo() == no) {
return this;
}

// 向右子树递归查询
if (this.getRightHeroNode() != null) {
resHero = this.getRightHeroNode().midOrderSearch(no);
}

return resHero;
}

/**
* 根据编号后序查询节点
* @param no 编号
* @return
*/
public HeroNode posOrderSearch(int no) {

HeroNode resHero = null;

// 向左子树递归查询
if (this.getLeftHeroNode() != null) {
resHero = this.getLeftHeroNode().posOrderSearch(no);
}
// 左子树找到直接返回
if (resHero != null) {
return resHero;
}

// 向右子树递归查询
if (this.getRightHeroNode() != null) {
resHero = this.getRightHeroNode().posOrderSearch(no);
}

// 左子树找到直接返回
if (resHero != null) {
return resHero;
}

// 和当前节点比较,如果是则返回
if (this.getNo() == no) {
return this;
}

return resHero;
}

// ===========================================

/**
* 递归删除结点 1.如果删除的节点是叶子节点,则删除该节点 2.如果删除的节点是非叶子节点,则删除该子树
* @param no
*/
public void deleteHeroNode(int no) {

/*
* 思路
* 1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
* 2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
* 3. 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
* 4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
* 5. 如果第4步也没有删除结点,则应当向右子树进行递归删除.
*/

if (this.getLeftHeroNode() != null && this.getLeftHeroNode().getNo() == no) {
this.setLeftHeroNode(null);
return;
}

if (this.getRightHeroNode() != null && this.getRightHeroNode().getNo() == no) {
this.setRightHeroNode(null);
return;
}

// 左子树递归
if (this.getLeftHeroNode() != null) {
this.getLeftHeroNode().deleteHeroNode(no);
}

// 右子树递归
if (this.getRightHeroNode() != null) {
this.getRightHeroNode().deleteHeroNode(no);
}
}

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 getLeftHeroNode() {
return leftHeroNode;
}

public void setLeftHeroNode(HeroNode leftHeroNode) {
this.leftHeroNode = leftHeroNode;
}

public HeroNode getRightHeroNode() {
return rightHeroNode;
}

public void setRightHeroNode(HeroNode rightHeroNode) {
this.rightHeroNode = rightHeroNode;
}

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

顺序存储二叉树

顺序存储二叉树的概念

从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组,看下面的示意图。

要求:
1)右图的二叉树的结点,要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7];

2)要求在遍历数组 arr时,仍然可以以 前序遍历,中序遍历和后序遍历的方式完成结点的遍历。

顺序存储二叉树的特点:

1)顺序二叉树通常只考虑完全二叉树;
2)第n个元素的左子节点为 2 * n + 1;
3)第n个元素的右子节点为 2 * n + 2;
4)第n个元素的父节点为 (n-1) / 2。

顺序存储二叉树图解:

顺序存储二叉树代码:

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
/**
* @Auther: Arsenal
* @Date: 2020-03-25 19:36
* @Description: 顺序存储二叉树
* 要求: 右图的二叉树的结点,要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7] 要求在遍历数组
* arr时,仍然可以以 前序遍历,中序遍历和后序遍历的 方式完成结点的遍历
* 顺序存储二叉树的特点:
* 1)顺序二叉树通常只考虑完全二叉树
* 2)第n个元素的左子节点为 2 * n + 1
* 3)第n个元素的右子节点为 2 * n + 2
* 4)第n个元素的父节点为 (n-1) / 2
*/
public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
System.out.println("========前序遍历========");
arrayBinaryTree.preOrder(0); // 1,2,4,5,3,6,7
System.out.println("");
System.out.println("========中序遍历========");
arrayBinaryTree.midOrder(0); // 2,4,5,1,3,6,7
System.out.println("");
System.out.println("========后序遍历========");
arrayBinaryTree.posOrder(0); // 2,4,5,3,6,7,1
}
}

class ArrayBinaryTree {
private int[] arr;

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

/**
* 前序遍历:先输出父节点,再遍历左子树和右子树
* @param index 数组下标
*/
public void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("空数组");
return;
}

System.out.print(arr[index] + " ");

if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}

if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}
}

/**
* 中序遍历:先遍历左子树,再输出父节点,再遍历右子树
* @param index 数组下标
*/
public void midOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("空数组");
return;
}

if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}

System.out.print(arr[index] + " ");

if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}
}

/**
* 后序遍历:先遍历左子树,再遍历右子树,最后输出父节点
* @param index 数组下标
*/
public void posOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("空数组");
return;
}

if ((2 * index + 1) < arr.length) {
preOrder(2 * index + 1);
}

if ((2 * index + 2) < arr.length) {
preOrder(2 * index + 2);
}

System.out.print(arr[index] + " ");
}
}

线索化二叉树

线索二叉树基本介绍:

1)n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为”线索”);
2)这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种;
3)一个结点的前一个结点,称为前驱结点;
4)一个结点的后一个结点,称为后继结点。

当线索化二叉树后,Node节点的 属性 left 和 right ,有如下情况:
1)left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点;
2)right指向的是右子树,也可能是指向后继节点,比如 ① 节点right 指向的是右子树,而⑩ 节点的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
/**
* @Auther: Arsenal
* @Date: 2020-03-25 19:30
* @Description: 线索化二叉树
*/
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
// 测试一把中序线索二叉树的功能
HeroNode root = new HeroNode(1, "America");
HeroNode node2 = new HeroNode(3, "Clinton");
HeroNode node3 = new HeroNode(6, "Bush");
HeroNode node4 = new HeroNode(8, "Obama");
HeroNode node5 = new HeroNode(10, "Trump");
HeroNode node6 = new HeroNode(14, "Biden");

// 二叉树,后面我们要递归创建, 现在简单处理使用手动创建
root.setLeftHeroNode(node2);
root.setRightHeroNode(node3);
node2.setLeftHeroNode(node4);
node2.setRightHeroNode(node5);
node3.setLeftHeroNode(node6);

// 测试中序线索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(root);
threadedBinaryTree.setMidOrderThreadedBinaryTree(root);

// 测试: 以10号节点测试
HeroNode leftNode = node5.getLeftHeroNode();
HeroNode rightNode = node5.getRightHeroNode();
System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
System.out.println("10号结点的后继结点是=" + rightNode); // 1

// 当线索化二叉树后,能在使用原来的遍历方法
// threadedBinaryTree.infixOrder();
System.out.println("使用线索化的方式遍历 线索化二叉树");
threadedBinaryTree.midOrderThreadedList(); // 8, 3, 10, 1, 14, 6
}
}

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

public ThreadedBinaryTree(HeroNode root) {
this.root = root;
}

// 中序遍历线索化二叉树的方法
public void midOrderThreadedList() {
// 定义一个变量,存储当前遍历的结点,从root开始
HeroNode node = root;
while (node != null) {
// 循环的找到leftType == 1的结点,第一个找到就是8结点
// 后面随着遍历而变化,因为当leftType==1时,说明该结点是按照线索化
// 处理后的有效结点
while (node.getLeftType() == 0) {
node = node.getLeftHeroNode();
}

// 打印当前这个结点
System.out.println(node);
// 如果当前结点的右指针指向的是后继结点,就一直输出
while (node.getRightType() == 1) {
// 获取到当前结点的后继结点
node = node.getRightHeroNode();
System.out.println(node);
}
// 替换这个遍历的结点
node = node.getRightHeroNode();
}
}

/**
* 设置为中序线索化二叉树
*/
public void setMidOrderThreadedBinaryTree(HeroNode node) {
// 如果node==null, 不能线索化
if (node == null) {
return;
}

// (一)先线索化左子树
setMidOrderThreadedBinaryTree(node.getLeftHeroNode());
// (二)线索化当前结点[有难度]

// 处理当前结点的前驱结点
// 以8结点来理解
// 8结点的.left = null , 8结点的.leftType = 1
if (node.getLeftHeroNode() == null) {
// 让当前结点的左指针指向前驱结点
node.setLeftHeroNode(pre);
// 修改当前结点的左指针的类型,指向前驱结点
node.setLeftType(1);
}

// 处理后继结点
if (pre != null && pre.getRightHeroNode() == null) {
// 让前驱结点的右指针指向当前结点
pre.setRightHeroNode(node);
// 修改前驱结点的右指针类型
pre.setRightType(1);
}
// !!! 每处理一个结点后,让当前结点是下一个结点的前驱结点
pre = node;

// (三)在线索化右子树
setMidOrderThreadedBinaryTree(node.getRightHeroNode());
}
}

/**
* 节点
*/
class HeroNode {
private int no;
private String name;
private HeroNode leftHeroNode;
private HeroNode rightHeroNode;

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

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 getLeftHeroNode() {
return leftHeroNode;
}

public void setLeftHeroNode(HeroNode leftHeroNode) {
this.leftHeroNode = leftHeroNode;
}

public HeroNode getRightHeroNode() {
return rightHeroNode;
}

public void setRightHeroNode(HeroNode rightHeroNode) {
this.rightHeroNode = rightHeroNode;
}

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;
}

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

树的常用术语

树的常用术语(结合示意图理解):
1)节点
2)根节点
3)父节点
4)子节点
5)叶子节点 (没有子节点的节点)
6)节点的权(节点值)
7)路径(从root节点找到该节点的路线)
8)层
9)子树
10)树的高度(最大层数)
11)森林 :多颗子树构成森林

延伸

    二叉树基础
    二叉树-百度百科
    韩顺平数据结构和算法
    Data Structure and Algorithms - Tree

Content
  1. 1. 前言
  2. 2. 二叉树
  3. 3. 顺序存储二叉树
  4. 4. 线索化二叉树
  5. 5. 树的常用术语
  6. 6. 延伸
var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "//hm.baidu.com/hm.js?xxxxxx"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();