二叉排序树
# 二叉排序树定义
二叉排序树(Binary Sort Tree)，又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树；
注：如果有相同的值，可以将该节点放在左子节点或右子节点
比如对于这样一个数组{7, 3, 10, 12, 5, 1, 9}，对应的二叉排序树为：
此时添加一个元素 2 ，对应的二叉排序树为：
当对这棵树进行中序遍历时，其结果将按照从小到大排序。
构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提髙査找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的査找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。
# Java实现二叉排序树
# 1. 结点类定义
二叉排序树本质上还是二叉树，所以结点类的定义和普通二叉树类似，我们多增加一个指向双亲结点的指针，方便后续的删除操作。
由于二叉排序树在插入结点时需要进行比较，所以数据元素必须是可以比较的，即实现了Compare接口。
import java.util.Optional;
/**
* 二叉排序树节点类
* @author hukai
*
* @param <E>
*/
public class BSTNode<E extends Comparable<E>> {
// 数据元素
private E element;
// 双亲，左孩子，右孩子结点
private BSTNode<E> parent, leftNode, rightNode;
public BSTNode() {}
public BSTNode(E element) {
super();
this.element = element;
}
// getter setter...
}
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
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
# 2. 查找操作
二叉排序树的查找可以用递归来实现：
- 先将要查找的关键字和根节点进行比较;
- 若和根节点值相同，则返回根节点值；若比根节点小，就递归查找左子树，若比根节点大，则递归查找右子树。
代码实现：
/**
* 查找节点
* @param element
* @return
*/
public BSTNode<E> search(E element){
int cmp = element.compareTo(this.getElement());
if (cmp < 0) {
// 如果查找的值小于当前结点，向左子树递归查找
return Optional.ofNullable(this.getLeftNode()).map(n -> n.search(element)).orElse(null);
}else if (cmp > 0) {
//如果查找的值大于于当前结点，向右子树递归查找
return Optional.ofNullable(this.getRightNode()).map(n -> n.search(element)).orElse(null);
}else{
// 等于当前节点，说明已经找到，直接返回
return this;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
查找最大最小元素就更简单，从根节点一直往左走，直到无路可走就可得到最小值；从根节点一直往右走，直到无路可走，就可以得到最大值。
/**
* 查找当前结点下最小结点
* @return
*/
public BSTNode<E> searchMinNode(){
BSTNode<E> minNode = this;
while (minNode.getLeftNode() != null) {
minNode = minNode.getLeftNode();
}
return minNode;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 3. 插入操作
插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。
代码实现：
/**
* 添加结点
* @param node
*/
public void add(BSTNode<E> node){
if (node == null) return;
int cmp = node.getElement().compareTo(this.getElement());
//判断传入的结点的值，和当前子树的根结点的值关系
if (cmp < 0) {
//如果当前结点左子结点为null
if (this.getLeftNode() == null) {
node.setParent(this);
this.setLeftNode(node);
}else{
//递归的向左子树添加
this.getLeftNode().add(node);
}
}else{
//添加的结点的值大于当前结点的值
if (this.getRightNode() == null) {
node.setParent(this);
this.setRightNode(node);
}else{
//递归的向右子树添加
this.getRightNode().add(node);
}
}
}
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
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
# 3. 删除操作
对于二叉排序树中的节点A，对它的删除分为三种情况：
- A为叶子结点，直接将A删除即可；
- A只有一个子节点，就直接将A的子节点连至A的父节点上，并将A删除；
- A有两个子节点，我们就以右子树内的最小节点取代A，怎么得最小节点，前面有说；
代码实现：
/**
* 移除指定结点
* @param targetNode
*/
private void remove(BSTNode<E> targetNode){
final BSTNode<E> parent = targetNode.getParent();
// 当前结点叶子结点，直接删除即可
if (targetNode.getLeftNode() == null && targetNode.getRightNode() == null) {
// 判断当前结点是双亲结点的左子结点，还是右子结点
if (parent != null && parent.getLeftNode() != null && parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(null);
}else if(parent != null && parent.getRightNode() != null && parent.getRightNode().getElement().equals(targetNode.getElement())){
parent.setRightNode(null);
}
targetNode.setParent(null);// 将当前结点的指针情空
}else if (targetNode.getLeftNode() != null && targetNode.getRightNode() != null){
// 删除有两颗子树的节点
// 找到右子树内的最小节点,该节点一定是一个叶子结点
BSTNode<E> minNode = targetNode.getRightNode().searchMinNode();
final E element = minNode.getElement();
// 移除最小节点
this.remove(minNode);
// 将最小结点的值替换当前结点的值
targetNode.setElement(element);
}else{
// 删除只有一颗子树的结点
// 如果要删除的结点有左子结点
if (targetNode.getLeftNode() != null) {
// 非根结点
if(parent != null) {
// 当前结点 是 parent 的左子结点
if (parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(targetNode.getLeftNode());
}else{
parent.setRightNode(targetNode.getLeftNode());
}
}else{
// 当前结点为根结点
root = root.getLeftNode();
}
}else{
if(parent != null) {
// 当前结点 是 parent 的左子结点
if (parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(targetNode.getRightNode());
}else{
parent.setRightNode(targetNode.getRightNode());
}
}else{
// 当前结点为根结点
root = root.getRightNode();
}
}
}
}
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
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
# 4. 完整实现
结点类：
import java.util.Optional;
/**
* 二叉排序树节点类
* @author hukai
*
* @param <E>
*/
public class BSTNode<E extends Comparable<E>> {
// 数据元素
private E element;
// 双亲，左孩子，右孩子结点
private BSTNode<E> parent, leftNode, rightNode;
public BSTNode() {}
public BSTNode(E element) {
super();
this.element = element;
}
// getter setter...
/**
* 查找节点
* @param element
* @return
*/
public BSTNode<E> search(E element){
int cmp = element.compareTo(this.getElement());
if (cmp < 0) {
// 如果查找的值小于当前结点，向左子树递归查找
return Optional.ofNullable(this.getLeftNode()).map(n -> n.search(element)).orElse(null);
}else if (cmp > 0) {
//如果查找的值大于于当前结点，向右子树递归查找
return Optional.ofNullable(this.getRightNode()).map(n -> n.search(element)).orElse(null);
}else{
// 等于当前节点，说明已经找到，直接返回
return this;
}
}
/**
* 查找当前结点下最小结点
* @return
*/
public BSTNode<E> searchMinNode(){
BSTNode<E> minNode = this;
while (minNode.getLeftNode() != null) {
minNode = minNode.getLeftNode();
}
return minNode;
}
/**
* 添加结点
* @param node
*/
public void add(BSTNode<E> node){
if (node == null) return;
int cmp = node.getElement().compareTo(this.getElement());
//判断传入的结点的值，和当前子树的根结点的值关系
if (cmp < 0) {
//如果当前结点左子结点为null
if (this.getLeftNode() == null) {
node.setParent(this);
this.setLeftNode(node);
}else{
//递归的向左子树添加
this.getLeftNode().add(node);
}
}else{
//添加的结点的值大于当前结点的值
if (this.getRightNode() == null) {
node.setParent(this);
this.setRightNode(node);
}else{
//递归的向右子树添加
this.getRightNode().add(node);
}
}
}
}
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
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
二叉排序树：
package com.hukai.demo.tree.binarySortTree;
/**
* 二叉排序树
* @author hukai
*
* @param <E>
*/
public class BinarySortTree<E extends Comparable<E>> {
// 根结点
private BSTNode<E> root;
// 元素个数
private int size = 0;
public BinarySortTree(){}
public BinarySortTree(E[] arr){
if (arr == null || arr.length == 0) return;
for (int i = 0; i < arr.length; i++) {
this.addNode(arr[i]);
}
}
/**
* 搜索结点
* @param element
* @return
*/
public BSTNode<E> searchNode(E element){
// 如果查找元素为空或根结点为空直接返回null
if (element == null || root == null) return null;
return root.search(element);
}
/**
* 添加结点
* @param element
* @return
*/
public BSTNode<E> addNode(E element){
if (element == null) return null;
BSTNode<E> node = new BSTNode<E>(element);
// 如果为空树
if (this.isEmpty()) {
root = node;
}else{
root.add(node);
}
size++;
return node;
}
/**
* 删除结点
* @param element
*/
public void removeNode(E element){
// 搜索需要删除的结点
final BSTNode<E> targetNode = this.searchNode(element);
//如果没有找到要删除的结点
if(targetNode == null) return;
//如果我们发现当前这颗二叉排序树只有一个结点
if(root.getLeftNode() == null && root.getRightNode() == null) {
root = null;
size = 0;
return;
}
// 删除结点
this.remove(targetNode);
size--;
}
/**
* 移除指定结点
* @param targetNode
*/
public void remove(BSTNode<E> targetNode){
final BSTNode<E> parent = targetNode.getParent();
// 当前结点叶子结点，直接删除即可
if (targetNode.getLeftNode() == null && targetNode.getRightNode() == null) {
// 判断当前结点是双亲结点的左子结点，还是右子结点
if (parent != null && parent.getLeftNode() != null && parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(null);
}else if(parent != null && parent.getRightNode() != null && parent.getRightNode().getElement().equals(targetNode.getElement())){
parent.setRightNode(null);
}
// 清空指针
targetNode.setParent(null);
}else if (targetNode.getLeftNode() != null && targetNode.getRightNode() != null){
// 删除有两颗子树的节点
// 找到右子树内的最小节点,该节点一定是一个叶子结点
BSTNode<E> minNode = targetNode.getRightNode().searchMinNode();
final E element = minNode.getElement();
// 移除最小节点
this.remove(minNode);
// 将最小结点的值替换当前结点的值
targetNode.setElement(element);
}else{
// 删除只有一颗子树的结点
// 如果要删除的结点有左子结点
if (targetNode.getLeftNode() != null) {
// 非根结点
if(parent != null) {
// 当前结点 是 parent 的左子结点
if (parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(targetNode.getLeftNode());
}else{
parent.setRightNode(targetNode.getLeftNode());
}
}else{
// 当前结点为根结点
root = root.getLeftNode();
}
}else{
if(parent != null) {
// 当前结点 是 parent 的左子结点
if (parent.getLeftNode().getElement().equals(targetNode.getElement())) {
parent.setLeftNode(targetNode.getRightNode());
}else{
parent.setRightNode(targetNode.getRightNode());
}
}else{
// 当前结点为根结点
root = root.getRightNode();
}
}
}
}
/**
* 中序遍历
* @param node
*/
public void inOrderTraverse(BSTNode<E> node){
if (node == null) return;
// 中序遍历左子树
inOrderTraverse(node.getLeftNode());
// 访问根节点
System.out.print(node.getElement() + "\t");
// 中序遍历右子树
inOrderTraverse(node.getRightNode());
}
/**
* 是否为空树
* @return
*/
public boolean isEmpty(){
return root == null && size == 0;
}
/**
* 获取根结点
* @return
*/
public BSTNode<E> root(){
return root;
}
public int size(){
return size;
}
}
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
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
# 二叉排序树总结
- 二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点。只要找到合适的插入和删除位置后，仅需要修改链接指针即可。插入删除的时间性能比较好；
- 对于二叉排序树的查找，走的是根结点到要查找结点的路径，其比较次数等于给定值的结点在二叉排序树的层次；
编辑 (opens new window)
上次更新: 2022/03/20, 16:39:15