数据结构之二叉树（九）：二叉排序树(BST)的创建和使用_建立二叉排序树的方法

二叉排序树(BST)的创建和使用

前言：
不同数列存储方式的优缺点：
数组：下标查找，查找速度快。缺点：添加慢。
链表：添加速度块。缺点：查找慢。
树存储：利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

二叉排序树
(Binary Sort(Search) Tree)，又叫二叉查找树。对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
相同的值，可将该节点放在左子节点或右子节点。

二叉排序树分析：
给定一示例数组，[7，3，10，12，5，1，9]
构建二叉排序树步骤如下：
首先取数组第一个元素作为树的根节点：

取出数组第二个节点，与根元素比较，小于7作为左子树

接着取下一个元素，与7比较大小，大于7，作为右子树

继续遍历取数组元素，比价大小后放置。

最后的效果图便是：

创建二叉排序树参考代码：

package Tree07;

public class BinarySortTreeDemo {
	public static void main(String[] args) {
		int[] arr= {7,3,10,12,5,1,9};
		BinarySortTree binarySortTree=new BinarySortTree();
		//循环的添加节点到二叉排序树
		for(int i=0;i<arr.length;i++) {
			binarySortTree.add(new Node(arr[i]));
		}
		//中序遍历二叉树
		binarySortTree.middleShow();
	}
}
//创建二叉排序树
class BinarySortTree{
	private Node root;
	//添加节点的方法
	public void add(Node node) {
		if(root==null) {
			root=node;//如果root为空则直接让node作为root
		}else {
			root.add(node);
		}
	}
	//中序遍历
	public void middleShow() {
		if(root!=null) {
			root.middleShow();
		}else {
			System.out.println("树为空，不能遍历");
		}
	}
}
//创建Node节点
class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
		this.value=value;
	}
	
	//添加节点的方法
	//递归的形式添加节点
	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 middleShow() {
		if(this.left!=null) {
			this.left.middleShow();
		}
		System.out.print(this.value+" ");
		if(this.right!=null) {
			this.right.middleShow();
		}
	}
}

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

运行结果：

二叉排序树的删除

二叉排序树的删除情况可能有三种：
1.删除叶子节点，比如上图中的2，5，9，12。
2.删除只有一颗子树的节点，比如上图中的节点1.
3.删除有两棵子树的节点，如上图中的节点 3，10，7.

那么删除的思路分析便要分三种情况
1.删除叶子节点
1）先找到要删除的节点
2）再找到要删除节点的父节点（可能是根节点，要先判断是否有父节点）
3）确定目标节点是左子节点还是右子节点
4)左子节点，令父节点的左子节点为空，右子节点，令父节点的右子节点为空。
2.删除只有一棵子树的节点
1）先找到要删除的节点
2）再找到要删除节点的父节点（可能是根节点，要先判断是否有父节点）
3)确定目标节点的子节点是左子节点还是右子节点
4)确定目标节点是它的父节点的左子节点还是右子节点
5.1）当删除的目标节点是它的父节点的左子节点，那么删除后它的子节点放到目标节点父节点的左子节点。
5.2）当删除的目标节点是它的父节点的右子节点，那么删除后它的子节点放到目标节点父节点的右子节点。
3.删除有两棵子树的节点
1）先找到要删除的节点
2）再找到要删除节点的父节点
3）从目标节点的右子树中找到最小的节点
4）用一个临时变量，将最小节点的值保存到temp
5）删除该最小节点
6）将目标节点赋给最小节点。

代码分析：
首先在Node类中实现根据传入值查找当前节点和其父节点的两种方法
如下：

//查找要删除的节点
	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);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//查找要删除节点的父节点
	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;//没有找到父节点
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

之后便可以实现deleteNode方法（根据上面的代码分析）

//删除节点
	public void delNode(int value) {
		if(root==null) {
			return;
		}else {
			//首先找到要删除节点 targetNode
			Node targetNode=search(value);
			//可能找不到节点
			if(targetNode==null) {
				return;
			}
			//如果我们发现当前这颗二叉树只有一个节点
			if(root.left==null&&root.right==null) {
				root=null;
				return;
			}
			//去找targetNode的父节点
			Node parent=searchParent(value);
			//如果删除的节点是叶子节点
			if(targetNode.left==null&&targetNode.right==null) {
				//判断targetNode是父节点的左子节点，还是右子节点
				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 minVal=delRightTreeMin(targetNode.right);
				targetNode.value=minVal;
			}else {//删除只有一棵子树的节点
				//如果删除的节点有左子节点
				if(targetNode.left!=null) {
					//如果tatgetNode是parent的左子节点
					if(parent.left.value==value) {
						parent.left=targetNode.left;
					}else {//targetNode是parent的右子节点
						parent.right=targetNode.left;
					}
				}else {//删除的节点有右子节点
					//如果tatgetNode是parent的左子节点
					if(parent.left.value==value) {
						parent.left=targetNode.right;
					}else {//targetNode是parent的右子节点
						parent.right=targetNode.right; 
					}
				}
			}
		}
	}
	//返回以node为根节点的二叉排序树的最小节点的值
	//删除node为根节点的二叉排序树的最小节点
	public int delRightTreeMin(Node node) {
		Node target=node;
		//循环查找左节点，就会找到最小值
		while(target.left!=null) {
			target=target.left;
		}
		//这时target指向了最小节点
		//删除最小节点
		delNode(target.value);
		return target.value;
	}
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

全部代码：

package Tree07;

public class BinarySortTreeDemo {
	public static void main(String[] args) {
		int[] arr= {7,3,10,12,5,1,9,2};
		BinarySortTree binarySortTree=new BinarySortTree();
		//循环的添加节点到二叉排序树
		for(int i=0;i<arr.length;i++) {
			binarySortTree.add(new Node(arr[i]));
		}
		//中序遍历二叉树
		System.out.println("中序遍历结果如下：");
		binarySortTree.middleShow();
		
		//binarySortTree.delNode(2);
		//binarySortTree.middleShow();
		System.out.println();
		binarySortTree.delNode(7);
		binarySortTree.middleShow();
	}
}
//创建二叉排序树
class BinarySortTree{
	private Node root;
	//删除节点
	public void delNode(int value) {
		if(root==null) {
			return;
		}else {
			//首先找到要删除节点 targetNode
			Node targetNode=search(value);
			//可能找不到节点
			if(targetNode==null) {
				return;
			}
			//如果我们发现当前这颗二叉树只有一个节点
			if(root.left==null&&root.right==null) {
				root=null;
				return;
			}
			//去找targetNode的父节点
			Node parent=searchParent(value);
			//如果删除的节点是叶子节点
			if(targetNode.left==null&&targetNode.right==null) {
				//判断targetNode是父节点的左子节点，还是右子节点
				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 minVal=delRightTreeMin(targetNode.right);
				targetNode.value=minVal;
			}else {//删除只有一棵子树的节点
				//如果删除的节点有左子节点
				if(targetNode.left!=null) {
					//如果tatgetNode是parent的左子节点
					if(parent.left.value==value) {
						parent.left=targetNode.left;
					}else {//targetNode是parent的右子节点
						parent.right=targetNode.left;
					}
				}else {//删除的节点有右子节点
					//如果tatgetNode是parent的左子节点
					if(parent.left.value==value) {
						parent.left=targetNode.right;
					}else {//targetNode是parent的右子节点
						parent.right=targetNode.right; 
					}
				}
			}
		}
	}
	//返回以node为根节点的二叉排序树的最小节点的值
	//删除node为根节点的二叉排序树的最小节点
	public int delRightTreeMin(Node node) {
		Node target=node;
		//循环查找左节点，就会找到最小值
		while(target.left!=null) {
			target=target.left;
		}
		//这时target指向了最小节点
		//删除最小节点
		delNode(target.value);
		return target.value;
	}
	//查找以node根节点的二叉排序树的最小节点的
	//查找要删除节点
	public Node search(int value) {
		if(root==null) {
			return null;
		}else {
			return root.search(value);
		}
	}
	//查找删除节点的父节点
	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;//如果root为空则直接让node作为root
		}else {
			root.add(node);
		}
	}
	//中序遍历
	public void middleShow() {
		if(root!=null) {
			root.middleShow();
		}else {
			System.out.println("树为空，不能遍历");
		}
	}
}
//创建Node节点
class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
		this.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 middleShow() {
		if(this.left!=null) {
			this.left.middleShow();
		}
		System.out.print(this.value+" ");
		if(this.right!=null) {
			this.right.middleShow();
		}
	}
}





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