数据结构—二叉排序树（Java）
博客说明
文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！
说明
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大
代码
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
| package cn.guizimo.binarysorttree;
public class BinarySortTree {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTreeDemo binarySortTree = new BinarySortTreeDemo();
for(int i = 0; i< arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
System.out.println("中序遍历");
binarySortTree.infixOrder();
binarySortTree.delNode(12);
System.out.println("当前根节点root=" + binarySortTree.getRoot());
System.out.println("删除后中序遍历");
binarySortTree.infixOrder();
}
}
class BinarySortTreeDemo {
private Node root;
public Node getRoot() {
return root;
}
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
public int delRightTreeMin(Node node) {
Node target = node;
while(target.left != null) {
target = target.left;
}
delNode(target.value);
return target.value;
}
public void delNode(int value) {
if (root == null) {
return;
} else {
Node targetNode = search(value);
if (targetNode == null) {
return;
}
if (root.left == null && root.right == null) {
root = null;
return;
}
Node parent = searchParent(value);
if (targetNode.left == null && targetNode.right == null) {
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
int i = delRightTreeMin(targetNode.right);
targetNode.value = i;
} else {
if (targetNode.left != null) {
if (parent != null) {
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {
parent.right = targetNode.right;
}
} else {
root = targetNode.left;
}
} else {
if (parent != null) {
if (parent.left.value == value) {
parent.left = targetNode.right;
} else if (parent.right.value == value) {
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("");
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public Node search(int value) {
if (value == this.value) {
return this;
} else if (value < this.value) {
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
public Node searchParent(int value) {
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
if (value < this.value && this.left != null) {
return this.left.searchParent(value);
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value);
} else {
return null;
}
}
}
public void add(Node node) {
if (node == null) {
return;
}
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
|
测试
感谢
尚硅谷
以及勤劳的自己
