logo头像

待到风起时,扬帆济沧海

二叉树

树的基本概念

 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点都只有有限个子节点或无子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;
  • 树里面没有环路(cycle)

树的三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)

  • 节点的高度=节点到叶子结点的最长路径(边数)
  • 节点的深度=根节点到这个节点所经历的边的个数
  • 节点的层数=节点的深度+1
  • 树的高度=根节点的高度
    1_2.png

1.png

  • 节点:上图的圆圈,比如A,B,C等都是表示节点。节点一般代表一些实体,在java面向对象编程中,节点一般代表对象。
  • 边:连接节点的线称为边,边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java当中通常表示引用。

 树有很多种,向上面的一个节点有多余两个的子节点的树,称为多路树,后面会讲解2-3-4树和外部存储都是多路树的例子。而每个节点最多只能有两个子节点的一种形式称为二叉树,本篇博客重点讲解二叉查找树。

2.png

  • 路径:顺着节点的边从一个节点走到另一个节点,所经过的节点的顺序排列就称为“路径”。
  • 根:树顶端的节点称为根。一棵树只有一个根,如果要把一个节点和边的集合称为树,那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。
  • 父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;B是D的父节点。
  • 子节点:一个节点含有的子树的根节点称为该节点的子节点;D是B的子节点。
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;比如上图的D和E就互称为兄弟节点。
  • 叶节点:没有子节点的节点称为叶节点,也叫叶子节点,比如上图的H、E、F、G都是叶子节点。
  • 子树:每个节点都可以作为子树的根,它和它所有的子节点、子节点的子节点等都包含在子树中。
  • 节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推。
  • 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
  • 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;

遍历树(深度优先遍历)

遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历,中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。

  • 中序遍历:左子树——》根节点——》右子树
  • 前序遍历:根节点——》左子树——》右子树
  • 后序遍历:左子树——》右子树——》根节点

层序遍历(广度优先遍历)

3.png

删除节点

删除节点是二叉搜索树中最复杂的操作,删除的节点有三种情况,前两种比较简单,但是第三种却很复杂。

  • 该节点是叶节点(没有子节点)
  • 该节点有一个子节点
  • 该节点有两个子节点

该节点是叶节点(没有子节点)

要删除叶节点,只需要改变该节点的父节点引用该节点的值,即将其引用改为null即可。删除节点,我们要先找到该节点,并记录该节点的父节点。在检查该节点是否有子节点。如果没有子节点,接着检查其是否是根节点,如果是根节点,只需要将其设置为null即可。如果不是根节点,是叶节点,那么断开父节点和其的关系即可。

4.png

删除有一个子节点的节点

删除有一个子节点的节点,我们只需要将其父节点原本指向该节点的引用,改为指向该节点的子节点即可。

5.png

删除有两个子节点的节点

6.png

当删除的节点存在两个子节点,那么删除之后,两个子节点的位置我们就没办法处理了。既然处理不了,我们就想到一种办法,用另一个节点来代替被删除的节点,那么用哪一个节点来代替呢?我们知道二叉搜索树中的节点是按照关键字来进行排列的,某个节点的关键字次高节点是它的中序遍历后继节点。用后继节点来代替删除的节点,显然该二叉搜索树还是有序的。

7.png

那么如何找到删除节点的中序后继节点呢?其实我们稍微分析,这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点,只有这样代替删除节点后才能满足二叉搜索树的特性。 

删除有两个子节点的节点-后继节点确认方法

如果删除的X的左子树L和右子树均R存在,则存在两种删除的思路,一种是在左子树L中寻找最大值节点LMax(LMax比为叶子节点),删除LMax并用LMax代替x即可;另一种思路则是在右子树R中寻找最小值节点RMin(RMin必为叶子节点),删除RMin并用RMin代替x即可。

真的需要删除吗?

在Node节点增加isDel状态属性,再可以不破坏树的情况下完成删除,显示查找时候判断一下即可

8.png

需要确定后继节点没有子节点,如果后继节点存在子节点,分情况讨论

  • 后继节点是删除节点的右子节点

9.png

  • 后继节点是删除节点的右子节点的左子节点

10.png

完整代码

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
package tree

import (
"fmt"
)

type Node struct {
Value int
Left *Node
Right *Node
}

type BinaryTree struct {
Root *Node
}

/**
查找节点
查找某个节点,我们必须从根节点开始遍历。
①、查找值比当前节点值大,则搜索右子树;
②、查找值等于当前节点值,停止搜索(终止条件);
③、查找值小于当前节点值,则搜索左子树;
树的效率:查找节点的时间取决于这个节点所在的层数,每一层最多有2n-1个节点,总共N层共有2n-1个节点,那么时间复杂度为O(logN),底数为2。
*/
func (this *BinaryTree) Find(data int) *Node {
current := this.Root
for current != nil {
if current.Value > data {
current = current.Left
} else if current.Value < data {
current = current.Right
} else {
return current
}
}
return nil
}

/**
要插入节点,必须先找到插入的位置。
与查找操作相似,由于二叉搜索树的特殊性,待插入的节点也需要从根节点开始进行比较,小于根节点则与根节点左子树比较,
反之则与右子树比较,直到左子树为空或右子树为空,则插入到相应为空的位置,
在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树,才能插入到正确的位置。
*/
func (this *BinaryTree) Insert(data int) bool {
addNode := &Node{Value: data, Left: nil, Right: nil}
if this.Root == nil {
this.Root = addNode
return true
}
current := this.Root
var parentNode *Node
for current != nil {
parentNode = current
//===判断
if current.Value > data { //当前值比插入值大,搜索左子节点
current = current.Left
if current == nil {
parentNode.Left = addNode
return true
}
} else {
current = current.Right
if current == nil {
parentNode.Right = addNode
return true
}
}
//===判断

}
return false
}

/**
中序遍历
*/
func (this *BinaryTree) InfixOrder(current *Node) {
if current != nil {
this.InfixOrder(current.Left)
fmt.Printf("%d,", current.Value)
this.InfixOrder(current.Right)
}
}

/**
前序遍历
*/
func (this *BinaryTree) PreOrder(current *Node) {
if current != nil {
fmt.Printf("%d,", current.Value)
this.PreOrder(current.Left)
this.PreOrder(current.Right)
}
}

/**
后序遍历
*/
func (this *BinaryTree) PostOrder(current *Node) {
if current != nil {
this.PostOrder(current.Left)
this.PostOrder(current.Right)
fmt.Printf("%d,", current.Value)
}
}


/**
层次遍历(广度遍历)
*/
func (this *BinaryTree) LevelOrder() [][]int {

valueList := make([][]int, 0)
if this.Root == nil {
return valueList
}
queue := make([]*Node, 0)
queue = append(queue, this.Root)
for len(queue) > 0 {
lvLenght := len(queue) //当前层队列有几个数据
lvArr := make([]int, 0)
lvQue := make([]*Node, 0)
for i := 0; i < lvLenght; i++ {
//弹出数据
node := queue[0]
queue = queue[1:]
lvArr = append(lvArr, node.Value)
if node.Left != nil {
lvQue = append(lvQue, node.Left)
}
if node.Right != nil {
lvQue = append(lvQue, node.Right)
}
}
queue = append(queue, lvQue...)
valueList = append(valueList, lvArr)
}
return valueList
}

/**
查找最大值
直接从树的右边开始找到最后
*/
func (this *BinaryTree) FindMax() *Node {
current := this.Root
max := current
for current != nil {
if current.Right != nil {
max = current.Right
}
current = current.Right
}
return max
}

/**
查找最小值
直接从树的左边开始找到最后
*/
func (this *BinaryTree) FindMin() *Node {
current := this.Root
min := current
for current != nil {
if current.Left != nil {
min = current.Left
}
current = current.Left
}
return min
}

func (this *BinaryTree) Delete(key int) bool {
current := this.Root
parent := this.Root
isLeftChild := false
//查找删除值,找不到直接返回false
for current.Value != key {
parent = current
if current.Value > key {
isLeftChild = true
current = current.Left
} else {
isLeftChild = false
current = current.Right
}
if current == nil {
return false
}
}
if current.Left == nil && current.Right == nil { //如果当前节点没有子节点
if current == this.Root {
this.Root = nil
} else if isLeftChild {
parent.Left = nil
} else {
parent.Right = nil
}
return true
} else if current.Left != nil && current.Right == nil { //有子左节点
if current == this.Root {
this.Root = current.Left
} else if isLeftChild {
parent.Left = current.Left
} else {
parent.Right = current.Left
}
return true
} else if current.Left == nil && current.Right != nil { //有子右节点
if current == this.Root {
this.Root = current.Right
} else if isLeftChild {
parent.Left = current.Right
} else {
parent.Right = current.Right
}
return true
} else {
successor := this.getSuccessor(current)
if current == this.Root {
this.Root = successor
} else if isLeftChild {
parent.Left = successor
} else {
parent.Right = successor
}
}
return false
}

/**
后继节点查找
*/
func (this *BinaryTree) getSuccessor(delNode *Node) *Node {
successorParent := delNode
successor := delNode
current := delNode.Left
for current != nil {
successorParent = successor
successor = current
current = current.Right
}
if successor != delNode.Left {
successorParent.Right = nil //删除引用
successor.Left = successorParent
successor.Right = delNode.Right
}
return successor
}

评论系统未开启,无法评论!