二叉排序树
在线性表中，我们可以通过数组和链表对数据进行查询、添加、删除。
在数组中查询的时间复杂度为O(1) , 添加删除的操作时间复杂度为O(n)
在链表中查询的时间复杂度为O(n) ，添加删除的操作时间复杂度为O(1) 【且当前已找到需要删除的数据】
因此我们通过二叉树来存储数据，以及与数据的一些处理。
二叉排序树的定义
二叉排序树(BST)，又称二叉查找树、二叉搜索树。
对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点比当前节点的值大。
特别说明，如果有相同的值，可以将该节点放在左子节点或右子节点。
比如对下面的一组数据（7，3，10，8，5，15，1），二叉排序树为：
验证是否为二叉树：
同样我们也可以进行中序遍历来验证
二叉排序树的创建和遍历
创建
之后的节点添加都类似。
最后添加完成
代码：
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
| class Node{
public int val;
public Node leftNode;
public Node rightNode;
public Node(int i) {
this.val = i;
}
public void infixOrder(){
if(this.leftNode != null){
this.leftNode.infixOrder();
}
System.out.print(this.val + "\t");
if(this.rightNode != null){
this.rightNode.infixOrder();
}
}
public void add(Node node){
if(node == null)
return;
if(node.val < this.val){
if(this.leftNode == null){
this.leftNode = node;
}else{
this.leftNode.add(node);
}
}else{
if(this.rightNode == null){
this.rightNode = node;
}else{
this.rightNode.add(node);
}
}
}
}
class Tree{
private Node root;
public Tree() {
}
public void infixOrder(){
if(this.root != null){
this.root.infixOrder();
}else{
System.out.println("二叉排序树为空");
}
}
public void add(Node node){
if(root == null){
root = node;
}else{
root.add(node);
}
}
}
public class BinarySortTree {
public static void main(String[] args) {
Node node1 = new Node(7);
Node node2 = new Node(3);
Node node3 = new Node(10);
Node node4 = new Node(8);
Node node5 = new Node(5);
Node node6 = new Node(15);
Node node7 = new Node(1);
Tree tree = new Tree();
tree.add(node1);
tree.add(node2);
tree.add(node3);
tree.add(node4);
tree.add(node5);
tree.add(node6);
tree.add(node7);
tree.infixOrder();
}
}
|
二叉排序树的删除
二叉排序树的删除需要考虑三种情况：
1、删除叶子节点
2、删除只有一个子树的节点
3、删除有两颗子树的节点
我们重新创建一个二叉排序树，节点值为：【7，3，10，12，5，1，9，2】
二叉排序树为：
第一种情况：删除节点2、5、9、12
1、找到需要删除的节点
2、找到需要删除节点的父节点
3、判断需要删除节点是父节点的左子节点或右子节点
4、如果为左子节点，parent.leftNode = null，如果为右子节点，parent.rightNode = null
删除节点2之后：
第二种情况：删除节点1
1、找到需要删除的节点targetNode
2、找到targetNode的父节点parent
3、确定targetNode的子结点是左子结点还是右子节点
4、确定targetNode是parent的左子节点还是右子节点。
5、如果targetNode有左子节点
5.1、如果targetNode是parent的左子节点 parent.leftNode = targetNode.left;
5.2、如果targetNode是parent的右子节点 parent.rightNode = targetNode.left;
6、如果targetNode有右子节点
5.1、如果targetNode是parent的左子节点 parent.leftNode = targetNode.right;
5.2、如果targetNode是parent的右子节点 parent.rightNode = targetNode.right;
删除节点1之后：
第三种情况 ：删除节点3，10
1、找到需要删除的节点targetNode
2、找到targetNode的父节点parent
3、从targetNode的右子树中找到最小的节点【或者左子树中找到最大节点】 。
4、用一个临时变量，将最小的节点的值保存到temp中。
5、删除右子树中最小的节点【或左子树中最大的节点】
6、targetNode.val = temp;
删除节点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
| class Node{
public int val;
public Node leftNode;
public Node rightNode;
public Node(int i) {
this.val = i;
}
public void infixOrder(){
if(this.leftNode != null){
this.leftNode.infixOrder();
}
System.out.print(this.val + "\t");
if(this.rightNode != null){
this.rightNode.infixOrder();
}
}
public void add(Node node){
if(node == null)
return;
if(node.val < this.val){
if(this.leftNode == null){
this.leftNode = node;
}else{
this.leftNode.add(node);
}
}else{
if(this.rightNode == null){
this.rightNode = node;
}else{
this.rightNode.add(node);
}
}
}
public Node Search(int val){
if(this.val == val){
return this;
}else if(this.val < val){
if(this.rightNode == null)
return null;
return this.rightNode.Search(val);
}else{
if(this.leftNode == null)
return null;
return this.leftNode.Search(val);
}
}
public Node SearchParent(int val){
if((this.leftNode != null && this.leftNode.val == val) || (this.rightNode != null && this.rightNode.val == val)) {
return this;
}else{
if (val < this.val && this.leftNode != null){
return this.leftNode.SearchParent(val);
}else if (val >= this.val && this.rightNode != null){
return this.rightNode.SearchParent(val);
}else{
return null;
}
}
}
}
class Tree{
private Node root;
public Tree() {
}
public void infixOrder(){
if(this.root != null){
this.root.infixOrder();
}else{
System.out.println("二叉排序树为空");
}
}
public void add(Node node){
if(root == null){
root = node;
}else{
root.add(node);
}
}
public Node Search(int val){
if(root == null){
return null;
}else{
return root.Search(val);
}
}
public Node SearchParent(int val){
if(this.root == null) {
return null;
}else{
return root.SearchParent(val);
}
}
public int delRightTreeMin(Node node){
Node target = node;
while(target.leftNode != null){
target = target.leftNode;
}
delNode(target.val);
return target.val;
}
public void delNode(int val){
if(root == null) {
return;
} else{
Node targetNode = Search(val);
if(targetNode == null){
return;
}
if(root.leftNode == null || root.rightNode == null){
root = null;
return;
}
Node parent = SearchParent(val);
if(targetNode.leftNode == null && targetNode.rightNode == null){
if(parent.leftNode != null && parent.leftNode.val == val){
parent.leftNode = null;
}else if(parent.rightNode != null && parent.rightNode.val == val){
parent.rightNode = null;
}
}else if(targetNode.leftNode != null && targetNode.rightNode != null){
int minVal = delRightTreeMin(targetNode.rightNode);
targetNode.val = minVal;
}else{
if(targetNode.leftNode != null){
if(parent != null){
if(parent.leftNode.val == val){
parent.leftNode = targetNode.leftNode;
}else{
parent.rightNode = targetNode.leftNode;
}
}else{
root = targetNode.leftNode;
}
}else{
if(parent != null){
if(parent.leftNode.val == val){
parent.leftNode = targetNode.rightNode;
}else{
parent.rightNode = targetNode.rightNode;
}
}else{
root = targetNode.rightNode;
}
}
}
}
}
}
|
测试：
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
| public static void main(String[] args) {
Node node1 = new Node(7);
Node node2 = new Node(3);
Node node3 = new Node(10);
Node node4 = new Node(12);
Node node5 = new Node(5);
Node node6 = new Node(1);
Node node7 = new Node(9);
Node node8 = new Node(2);
Tree tree = new Tree();
tree.add(node1);
tree.add(node2);
tree.add(node3);
tree.add(node4);
tree.add(node5);
tree.add(node6);
tree.add(node7);
tree.add(node8);
tree.infixOrder();
System.out.println();
tree.delNode(1);
tree.delNode(12);
tree.delNode(10);
tree.infixOrder();
}
|