二叉排序树（Binary Sort Tree）
前言： 二叉排序树是二叉树中十分重要的一种，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
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
91
92
93
| package day7_test;
public class Node {
public int val;
public Node right;
public Node left;
public Node searchNode(int index){
if(this.val == index){
return this;
}else if(index < this.val) {
if(this.left == null){
return null;
}else{
return this.left.searchNode(index);
}
}else {
if (this.right == null){
return null;
}else {
return this.right.searchNode(index);
}
}
}
public Node searchParent(int index){
if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
return this;
}else {
if(index < this.val && this.left != null){
return this.left.searchParent(index);
}else if (index >= this.val && this.right != null){
return this.right.searchParent(index);
}else {
return null;
}
}
}
public void add(Node node){
if(node == null){
return;
}
if(node.val < this.val){
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 infix(){
if(this.left != null){
this.left.infix();
}
System.out.println(this);
if (this.right != null){
this.right.infix();
}
}
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node[" +
"val=" + val +
']';
}
}
|
二叉排序树的添加功能
思路：
每传进来一个node节点，我们就与当前节点进行比较
node的val值 < 当前节点的val值：
向左进行递归，一直递归到this.left == null时，加入node节点
node的val值 >= 当前节点的val值：
向右进行递归，知道this.right == null时，加入node节点
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void add(Node node){
if(node == null){
return;
}
if(node.val < this.val){
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);
}
}
}
|
结果：
Node[val=0]
Node[val=1]
Node[val=3]
Node[val=5]
Node[val=7]
Node[val=9]
Node[val=10]
Node[val=12]
二叉排序树删除功能详解
思路：
首先分三种情况进行处理：
① 所删除的节点为叶子节点（left 和right 节点上为空）
② 所删除的节点为非叶子节点，并且left 或 right节点上只有一个不为空
③ 所删除的节点为非叶子节点，并且left 和 right 都不为空
在处理这三种情况之前，先再Node节点类中增添方法，用来查询要删除的目标节点targetNode 以及targetNode的父节点 parent节点
代码如下：
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
|
public Node searchNode(int index){
if(this.val == index){
return this;
}else if(index < this.val) {
if(this.left == null){
return null;
}else{
return this.left.searchNode(index);
}
}else {
if (this.right == null){
return null;
}else {
return this.right.searchNode(index);
}
}
}
public Node searchParent(int index){
if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
return this;
}else {
if(index < this.val && this.left != null){
return this.left.searchParent(index);
}else if (index >= this.val && this.right != null){
return this.right.searchParent(index);
}else {
return null;
}
}
}
|
情况一：删除的是叶子节点
步骤：【
- 找到目标节点targetNode 及其它的父节点 parent
- 确定targetNode是parent的left节点 还是right 节点
- parent.left = null 或 parent.right = null ;
】
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Node targetNode = root.searchNode(index);
if (targetNode == null){
System.out.println("没有找到要删除的节点！");
return;
}
if (root.left == null && root.right == null){
root = null;
return;
}
Node parent = root.searchParent(index);
if(targetNode.left == null && targetNode.right == null){
if(parent.left!= null && parent.left.val == targetNode.val){
parent.left = null;
}else if(parent.right != null && parent.right.val == targetNode.val ) {
parent.right = null;
}
}
|
情况二：要删除的节点只有一个子节点
步骤【
找到父节点和targetNode目标节点后
先判断targetNode的left 和right 是否为空 ，如果不为空再判断是否有parent节点，因为很可能这个节点是root节点 ，root节点没有parent节点
接下来就是四种判断
targetNode 有左节点 ，targetNode是parent的左节点；—–> parent.left = targetNode.left;
targetNode 有左节点 ，targetNode是parent的右节点；—–> parent.right = targetNode.left;
targetNode 有右节点 ，targetNode是parent的左节点；—–>parent.left = targetNode.right;
targetNode 有右节点 ，targetNode是parent的右节点；—–>parent.right = targetNode.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
|
else{
if(targetNode.left != null){
if(parent != null){
if (parent.left == targetNode){
parent.left = targetNode.left;
}else{
parent.right = targetNode.left;
}
}else {
root = targetNode.left;
}
}
else {
if(parent != null){
if (parent.left == targetNode){
parent.left = targetNode.right;
}else{
parent.right = targetNode.right;
}
}else {
root = targetNode.right;
}
}
}
|
情况三：要删除的节点只有一个子节点
这种情况我们有两种解决办法
步骤 【
方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
】
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
else if (targetNode.left != null && targetNode.right !=null){
int tempMax = 0;
Node tempNode = targetNode.left;
while(tempNode.right != null){
tempNode = tempNode.right;
}
tempMax = tempNode.val;
deleteNode(tempMax);
targetNode.val = tempMax;
}
|
main方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void main(String[] args) {
int arr[] ={7,3,10,12,5,1,9,0};
BinarySortTree b = new BinarySortTree();
for(int i=0;i<arr.length;i++){
b.add(new Node(arr[i]));
}
b.infix(b.root);
b.deleteNode(3);
b.deleteNode(12);
b.deleteNode(5);
b.deleteNode(1);
b.deleteNode(7);
b.deleteNode(9);
b.deleteNode(10);
b.deleteNode(0);
System.out.println("删除之后~~~");
b.infix(b.root);
}
|
整体代码实现：
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
| package day7_test;
public class BinarySortTree {
public Node root;
public static void main(String[] args) {
int arr[] ={7,3,10,12,5,1,9,0};
BinarySortTree b = new BinarySortTree();
for(int i=0;i<arr.length;i++){
b.add(new Node(arr[i]));
}
b.infix(b.root);
b.deleteNode(3);
b.deleteNode(12);
b.deleteNode(5);
b.deleteNode(1);
b.deleteNode(7);
b.deleteNode(9);
b.deleteNode(10);
b.deleteNode(0);
System.out.println("删除之后~~~");
b.infix(b.root);
}
public void deleteNode(int index){
if (root == null){
return;
}
else{
Node targetNode = root.searchNode(index);
if (targetNode == null){
System.out.println("没有找到要删除的节点！");
return;
}
if (root.left == null && root.right == null){
root = null;
return;
}
Node parent = root.searchParent(index);
if(targetNode.left == null && targetNode.right == null){
if(parent.left!= null && parent.left.val == targetNode.val){
parent.left = null;
}else if(parent.right != null && parent.right.val == targetNode.val ) {
parent.right = null;
}
}
else if (targetNode.left != null && targetNode.right !=null){
int tempMax = 0;
Node tempNode = targetNode.left;
while(tempNode.right != null){
tempNode = tempNode.right;
}
tempMax = tempNode.val;
deleteNode(tempMax);
targetNode.val = tempMax;
}
else{
if(targetNode.left != null){
if(parent != null){
if (parent.left == targetNode){
parent.left = targetNode.left;
}else{
parent.right = targetNode.left;
}
}else {
root = targetNode.left;
}
}
else {
if(parent != null){
if (parent.left == targetNode){
parent.left = targetNode.right;
}else{
parent.right = targetNode.right;
}
}else {
root = targetNode.right;
}
}
}
}
}
public void add(Node node){
if (root == null){
root = node;
}else {
root.add(node);
}
}
public void infix(Node root){
if (root == null){
System.out.println("空树！");
return;
}
root.infix();
}
}
|
运行结果：
删除3 后
Node[val=0]
Node[val=1]
Node[val=5]
Node[val=7]
Node[val=9]
Node[val=10]
Node[val=12]
删除3,12,5,1 后
Node[val=0]
Node[val=7]
Node[val=9]
Node[val=10]
删除3,12,5,1,7,9 后
Node[val=0]
Node[val=10]
删除所有的之后
空树！
