二叉查找树(binary search tree)具有以下特征:

对于树中的每一个节点,它的左子树中节点的值都小于该节点的值,它的右子树中节点的值都大于该节点的值(即不包含重复元素)。

BST的Java实现:

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
public class BinarySearchTree<E extends Comparable<E>>{
private int size = 0;
private TreeNode<E> root = null;
//定义树节点TreeNode类
public static class TreeNode<E extends Comparable<E>>{
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e){
element = e;
}
}
//插入一个包含元素e的新节点
public boolean insert(E e){
if(root == null){
root = new TreeNode<E>(e);
size++;
return true;
}
TreeNode<E> current = root;
TreeNode<E> parent = null;
//确定插入点的父节点parent的位置
while(current != null){
if(e.compareTo(current.element) > 0){
parent = current;
current = current.right;
}
else if(e.compareTo(current.element) < 0){
parent = current;
current = current.left;
}
else
return false;
}
//将新节点添加到父节点下面
if(e.compareTo(parent.element) > 0)
parent.right = new TreeNode<E>(e);
else
parent.left = new TreeNode<E>(e);
size++;
return true;
}
//删除一个包含元素e的节点
public boolean delete(E e){
if(root == null)
return false;
TreeNode<E> current = root;
TreeNode<E> parent = null;
//确定被删节点的位置
while(current != null){
if(e.compareTo(current.element) > 0){
parent = current;
current = current.right;
}
else if(e.compareTo(current.element) < 0){
parent = current;
current = current.left;
}
else
break;
}
//被删节点不存在
if(current == null)
return false;
if(current.right == null)
parent.right = current.left;
else{
TreeNode<E> rCurrent = current.right;
TreeNode<E> rParent = current;
while(rCurrent.left != null){
rParent = rCurrent;
rCurrent = rCurrent.left;
}
current.element = rCurrent.element;
if(rParent.left == rCurrent)
rParent.left = rCurrent.right;
else
rParent.right = rCurrent.right;
}
size--;
return true;
}
//中序遍历该二叉树
public void inorder(){
inorder(root);
}
protected void inorder(TreeNode<E> root){
if(root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
//返回一个包含中序遍历结果的迭代器
public java.util.Iterator inorderIterator(){
return new InorderIterator();
}
public class InorderIterator implements java.util.Iterator{
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0;
public InorderIterator(){
inorder(root);
}
private void inorder(TreeNode<E> root){
if(root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
public boolean hasNext(){
if(current < list.size())
return true;
return false;
}
public Object next(){
return list.get(current++);
}
}
}
  • 遍历二叉树时,从根节点root开始,利用的是子节点与父节点的从属关系、左右子节点的大小关系,节点类TreeNode实现了Comparable类。插入新节点时,遍历确定插入点的父节点位置;删除节点时,遍历确定被删节点的位置。

  • 插入新节点时,注意BST不包含重复元素(L37)。

  • 删除节点时,需要判断该节点是否存在于二叉树。若存在,停止遍历;若不存在,超出节点范围,也会停止遍历。可以通过判断遍历停止位置是否超出节点范围,确定遍历停止的原因,从而确定该节点是否存在(L71)。

  • 删除节点时,根据BST的特征,可以使用左子树中节点的最大值,或右子树中节点的最小值覆盖该节点的值,同时将最值节点置空。这里使用的是后者:

    • 如果右子树为空,使用一个空节点覆盖被删节点,相当于将左子树直接添加为被删节点的父节点的左子树;
    • 如果右子树非空,通过遍历确定右子树中的最小值节点,即第一个左子树为空的节点。覆盖被删节点后,将最值节点置空时,需要考虑最值节点可能存在的右子树(左子树已经为空),
    • 确定最值节点与其父节点的从属关系,即最值节点为左节点还是右节点,最值节点置空后,其右子树相当于直接添加到其父节点下面,从属关系与最值节点一致(L86)。
  • BST的中序遍历,即是对树中的元素进行排序。

这里给出一个简单的例子:

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
public class TestBST{
public static void main(String[] args){
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
System.out.println(tree.insert(12));
System.out.println(tree.insert(45));
System.out.println(tree.insert(14));
System.out.println(tree.insert(32));
System.out.println(tree.insert(26));
System.out.println(tree.insert(48));
System.out.println(tree.insert(16));
System.out.println(tree.insert(14));//插入一个重复节点
System.out.println(tree.insert(20));
//inorder()实现的中序遍历
tree.inorder();
System.out.println();
System.out.println(tree.delete(24));//删除一个不存在的节点
System.out.println(tree.delete(32));
//迭代器中的中序遍历结果
java.util.Iterator it = tree.inorderIterator();
while(it.hasNext())
System.out.print(it.next() + " ");
}
}
输出结果为:
1
2
3
4
5
6
7
8
9
10
11
12
13
true
true
true
true
true
true
true
false
true
12 14 16 20 26 32 45 48
false
true
12 14 16 20 26 45 48
通过中序遍历的输出结果,可以判断添加、删除操作是否成功:
  • inorder()通过递归实现了中序遍历。

  • InorderIterator类实现了java.util.Iterator接口,将中序遍历结果添加到迭代器中。