二叉搜索树

二叉搜索树(没有重复元素)的特征是:对于树中的每一个节点,它的左子树中的节点的值都小于该节点的值,而它的右子树中节点的值都大于该节点的值。

表示二叉搜索树

二叉搜索树(Binary Search Tree, BST)可以用一个链式节点的集合来表示二叉树。 每个节点都包含一个数值和两个称为left和right的链接,分别指向左孩子和右孩子。

树的节点类
1
2
3
4
5
6
7
8
9
10
11
12
13
/** This inner class is static, because it does not access
*any instance members defined in its outer class
*/
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}

TreeNode<Integer> root = new TreeNode<>(60);

变量root指向根节点。如果树为空,root的值为null。

树的遍历

二叉树分为根节点、左子树和右子树,分别表示为 +、1、2。
二叉树本身是递归定义的,相应的遍历很自然就成为一种递归问题。

递归遍历操作的关键点是递归体和递归出口:

  • 递归出口是二叉树的空子树或叶节点,此时为空操作,递归不继续进行,只能回退;
  • 递归体是对二叉树根节点或左、右子树进行相应处理。

基于递归的遍历算法易于编写,操作简单,但可读性差,系统需要维护相应的工作栈,效率不是很高。递归转化为非递归的基本思想是如何实现原本是系统完成的递归工作栈,为此,可以仿照递归执行过程中工作栈状态变化而得到。

对二叉树进行前序、中序和后序遍历时都开始于根节点或结束于根节点,经由路线也相同。彼此差别在于对节点访问时机的选择不同。三种遍历方式都是沿着左子树不断深入下去,当到达二叉树左下节点而无法往下深入时,就向上逐一返回,行进到最近深入时曾遇到节点的右子树,然后进行同样的深入和返回,直到最终从根节点的右子树返回到根节点。
这样,遍历时返回顺序与深入节点顺序恰好相反,因此可以在实现二叉树遍历过程中,使用一个工作栈来保存当前深入到的节点信息,以供后面返回需要时使用。

中序遍历(inorder traversal)

遍历顺序为: 1+2 可以递增顺序显示BST中所有节点。
中序遍历的黄金口诀:当前节点为空,从栈中弹出一个元素,当前节点向右移动;当前节点不为空,压栈,当前节点向左移动

  • 中序遍历访问左子二叉树
  • 访问根节点
  • 中序遍历访问右子二叉树
inorder递归遍历
1
2
3
4
5
6
7
8
9
10
11
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); // 递归遍历右子树 1+2
}
中序非递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void inorder() {
inorder(root);
}

protected void inorder(TreeNode<E> root) {
if (root == null)
return;
java.util.Stack<TreeNode<E>> stack = new java.util.Stack<>();
TreeNode<E> current = root;
while (!stack.empty() || current != null) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
TreeNode<E> node = stack.pop();
System.out.print(node.element + " ");
current = node.right;
}
}
}

前序遍历(preorder traversal)

+12 深度优先遍历法(depth-first traversal)与前序遍历法相同。

  • 访问根节点
  • 前序遍历访问左子二叉树
  • 前序遍历访问右子二叉树
preorder递归遍历
1
2
3
4
5
6
7
8
9
10
public void preorder() {
preorder(root);
}
protected void preorder(TreeNode<E> root) {
if (root == null)
return;
System.out.println(root.element + " "); // 递归遍历根节点
preorder(root.left); // 递归遍历左子树
preorder(root.right); // 递归遍历右子树 +12
}
前序非递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void preorder() {
preorder(root);
}
protected void preorder(TreeNode<E> root) {
if (root == null)
return;
Stack<TreeNode<E>> stack = new Stack<>();
stack.push(root);

while (!stack.empty()) {
TreeNode<E> node = stack.pop();
System.out.print(node.element + " ");

// Push the right child onto the stack
// first so the left is processed first
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}

后序遍历(postorder traversal)

12+

  • 后序遍历访问左子二叉树
  • 后序遍历访问右子二叉树
  • 访问根节点
postorder递归遍历
1
2
3
4
5
6
7
8
9
10
public void postorder() {
postorder(root);
}
protected void postorder(TreeNode<E> root) {
if (root == null)
return;
postorder(root.left); // 递归遍历左子树
postorder(root.right); // 递归遍历右子树
System.out.println(root.element + " "); // 递归遍历根节点 12+
}
后序非递归遍历
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 void postorder() {
postorder(root);
}

protected void postorder(TreeNode<E> root) {
if (root == null) return;

// Create two stacks
Stack<TreeNode<E>> stack1 = new Stack<>();
Stack<TreeNode<E>> stack2 = new Stack<>();

// push root to stack1
stack1.push(root);
while (!stack1.empty()) {
// Pop node from stack1 and push onto stack2
TreeNode<E> node = stack1.pop();
stack2.push(node);

if (node.left != null)
stack1.push(node.left);
if (node.right != null)
stack1.push(node.right);
}

// Display elements in stack2
while (!stack2.empty()) {
System.out.print(stack2.pop().element + " ");
}
}

广度优先遍历(breadth-first traversal)

广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void breadthFirstTraversal() {
if (root == null)
return;

// Queue Deque Linkedlist
java.util.Queue<TreeNode<E>> queue = new java.util.LinkedList<>();

queue.add(root);
while (!queue.isEmpty()) {
TreeNode<E> current = queue.element();
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
System.out.println(queue.remove().element + " ");
}
}

搜索一个元素

二叉搜索树中搜索一个元素,可以从根节点向下扫描,知道找到匹配元素,或者达到一棵空子树为止。

在BST中搜索一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean search(E e) {
TreeNode<E> current = root; // 当前指针指向根节点
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left; // 比当前指针的元素小,则往左
} else if (e.compareTo(current.element) > 0) {
current = current.right; // 比当前指针的元素大,则往右
} else { // 元素匹配
return true; // 找到元素 return true
}
}
return false;
}

插入一个元素

BST中插入一个元素,需要确定在书中插入的位置,关键思路是确定新节点的父节点所在的位置。

  • 如果树是空的,使用新元素创建一个根节点;
  • 否则,寻找新节点的父节点的位置
  • 为该元素创建一个新节点,如果新元素的值小于父元素的值,左子节点;如果新元素的值大于父元素的值,右子节点;BST没有重复元素,重复则不插入
在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
28
29
30
31
public boolean insert(E e) {
if (root == null) {
root = createNewNode(e); // 创建一个节点,树为空该节点成为根节点
} else {
TreeNode<E> parent = null; // 定位父节点
TreeNode<E> current = root; // 当前指针指向根节点

while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false; // 元素已经在树中,return false
}
}
// 为元素e创建一个节点
if (e.compareTo(parent.element) < 0) {
parent.left = createNewNode(e);
} else {
parent.right = createNewNode(e);
}
}
size++;
return true;
}
public TreeNode<E> createNewNode(E e) {
return new TreeNode<>(e);
}

删除BST中的一个元素

为了从一棵二叉搜索树中删除一个元素,首先需要定位该元素位置,然后再删除该元素以及重新连接树前,考虑两种情况–该节点有或者没有左子节点。
情况1:当前节点没有左子结点。只需将该节点的父节点和该节点的右子节点相连。如果当前节点是叶子节点,属于情况1;

情况2:当前节点有左子结点。假设rightMost指向包含current节点的左子树中的最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。使用rightMost节点中的元素替代current节点中的元素值,将parentOfRightMost节点和rightMost节点的左子节点相连,然后删除rightMost节点。 rightMost作为最大值不能有右节点,但是可能会有左子节点!

从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
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
public boolean delete(E e) {
// 如果current为root,那么parent为null
TreeNode<E> parent = null; // 指向current节点的父节点
TreeNode<E> current = root; // 指向二叉搜索树中包含该元素的节点

while (current != null) { // 递归寻找current节点
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
break; // 找到包含e的current节点
}
}

if (current == null) {
return false; // 元素不在树内
}

// 情况1:当前节点没有左子节点
if (current.left == null) {
//只需将该节点的父节点和该节点的右子节点相连
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element) < 0) {
parent.left = current.right; // e是父节点的左子结点
} else {
parent.right = current.right; // e是父节点的右子结点
}
}
} else {
// 情况2:当前节点有左子节点
TreeNode<E> parentOfRightMost = current; // rightMost节点的父节点
TreeNode<E> rightMost = current.left; // 当前节点的左子树最右端的节点

while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // 向右不断递归
}
// 用rightMost节点的内容替换current中的内容
current.element = rightMost.element;
// rightMost的父节点和rightMost的左子节点相连
if (parentOfRightMost.right == rightMost) {
// rightMost是右子节点
parentOfRightMost.right = rightMost.left;
} else {
// rightMost是左子节点
parentOfRightMost.left = rightMost.left;
}
}
size--;
return true;
}

找出叶子节点和非叶子结点

找出叶子节点的个数
1
2
3
4
5
6
7
8
9
10
11
12
public int getNumberOfLeaves() {
return getNumberOfLeaves(root);
}

protected int getNumberOfLeaves(TreeNode<E> root) {
if (root ==null)
return 0;
// If node has no children return 1
// else return the sum of all the leaves
return root.left == null && root.right == null ?
1 : getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
}
找出非叶子节点的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
public int getNumberOfNonLeaves() {
return getNumberOfNonLeaves(root);
}

protected int getNumberOfNonLeaves(TreeNode<E> root) {
if (root == null) return 0;

// If node has children return 0
// else return 1 plus the sum of the nonleaves
return (root.left == null && root.right == null) ? 0 :
1 + getNumberOfNonLeaves(root.left) +
getNumberOfNonLeaves(root.right) ;
}

实现equals和clone方法

树的equals方法
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean equals(BST<E> tree) {
if (tree.size != size) return false;
return equals(root, tree.root);
}

/** Equals helper */
protected boolean equals(TreeNode<E> root1, TreeNode<E> root2) {
if (root1 == root2) return true;
if (root1 == null || root2 == null) return false;
return root1.element.equals(root2.element) &&
equals(root1.left, root2.left) &&
equals(root1.right, root2.right);
}
树的clone方法
1
2
3
4
5
6
7
8
9
10
11
12
13
public BST<E> clone() throws CloneNotSupportedException {
BST<E> cloneBST = new BST<>();
clone(cloneBST, root);
return cloneBST;
}

/** Clone helper */
protected void clone(BST<E> clone, TreeNode<E> root) {
if (root == null) return;
clone.insert(root.element);
clone(clone, root.left);
clone(clone, root.right);
}

BST类

使用一个Tree的接口来定义树的所有常用操作,提供AbstractTree的抽象类部分实现了Tree,最后实现了BST类。

Tree接口

Tree.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
public interface Tree<E> extends Iterable<E>{
/** Return true 如果搜索成功 */
boolean search(E e);

/** 向二叉搜索树插入元素 Return true 如果成功添加 */
boolean insert(E e);

/** Return true 如果成功从树中删除元素 */
boolean delete(E e);

/** 中序遍历打印节点 1+2 */
void inorder();

/** 后序遍历打印节点 12+ */
void postorder();

/** 前序遍历打印节点 +12 */
void preorder();

/** 广度优先遍历打印节点 */
void breadthFirstTraversal();

/** 返回树中节点数 */
int getSize();

/** Return true 如果树为空 */
boolean isEmpty();
}

AbstractTree抽象类

AbstractTree.java 抽象类部分地实现了Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public abstract class AbstractTree<E> implements Tree<E> {
@Override /** 中序遍历打印节点 1+2 */
public void inorder() {
}

@Override /** 后序遍历打印节点 12+ */
public void postorder() {
}

@Override /** 前序遍历打印节点 +12 */
public void preorder() {
}

@Override /** Return true 如果树为空 */
public boolean isEmpty() {
return getSize() == 0;
}
}

具体的BST

BST.java 具体定义了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
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/* 因为每个节点只遍历一次,遍历的时间复杂度都是O(n)
* 搜索、插入和删除的时间复杂度是树的高度。
* 最差的情况下,树的高度为O(n)
* 如果树是平衡的,高度将是O(logn)
*/

public class BST<E extends Comparable<E>> extends AbstractTree<E> {
protected TreeNode<E> root; //根节点
protected int size = 0; //节点数目

/** 默认构造方法 */
public BST() {
}
/** 泛型数组构造二叉搜索树 */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}

@Override
public boolean search(E e) {
TreeNode<E> current = root; // 当前指针指向根节点
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left; // 比当前指针的元素小,则往左
} else if (e.compareTo(current.element) > 0) {
current = current.right; // 比当前指针的元素大,则往右
} else { // 元素匹配
return true; // 找到元素 return true
}
}
return false;
}

@Override
public boolean insert(E e) {
if (root == null) {
root = createNewNode(e); // 创建一个节点,树为空该节点成为根节点
} else {
TreeNode<E> parent = null; // 定位父节点
TreeNode<E> current = root; // 当前指针指向根节点

while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false; // 元素已经在树中,return false
}
}
// 为元素e创建一个节点
if (e.compareTo(parent.element) < 0) {
parent.left = createNewNode(e);
} else {
parent.right = createNewNode(e);
}
}
size++;
return true;
}

public TreeNode<E> createNewNode(E e) {
return new TreeNode<>(e);
}

/** 为了从一棵二叉搜索树中删除一个元素,首先需要定位该元素位置,
* 然后在删除该元素以及重新连接树之前,考虑两种情况:
* 1)该节点有左子节点
* 2)该节点没有左子节点
*/
@Override
public boolean delete(E e) {
// 如果current为root,那么parent为null
TreeNode<E> parent = null; // 指向current节点的父节点
TreeNode<E> current = root; // 指向二叉搜索树中包含该元素的节点

while (current != null) { // 递归寻找current节点
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
break; // 找到包含e的current节点
}
}

if (current == null) {
return false; // 元素不在树内
}

// 情况1:当前节点没有左子节点
if (current.left == null) {
//只需将该节点的父节点和该节点的右子节点相连
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element) < 0) {
parent.left = current.right; // e是父节点的左子结点
} else {
parent.right = current.right; // e是父节点的右子结点
}
}
} else {
// 情况2:当前节点有左子节点
TreeNode<E> parentOfRightMost = current; // rightMost节点的父节点
TreeNode<E> rightMost = current.left; // 当前节点的左子树最右端的节点

while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // 向右不断递归
}
// 用rightMost节点的内容替换current中的内容
current.element = rightMost.element;
// rightMost的父节点和rightMost的左子节点相连
if (parentOfRightMost.right == rightMost) {
// rightMost是右子节点
parentOfRightMost.right = rightMost.left;
} else {
// rightMost是左子节点
parentOfRightMost.left = rightMost.left;
}
}
size--;
return true;
}

@Override
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); // 递归遍历右子树 1+2
}

@Override
public void postorder() {
postorder(root);
}
protected void postorder(TreeNode<E> root) {
if (root == null)
return;
postorder(root.left); // 递归遍历左子树
postorder(root.right); // 递归遍历右子树
System.out.println(root.element + " "); // 递归遍历根节点 12+
}

@Override
public void preorder() {
preorder(root);
}
protected void preorder(TreeNode<E> root) {
if (root == null)
return;
System.out.println(root.element + " "); // 递归遍历根节点
preorder(root.left); // 递归遍历左子树
preorder(root.right); // 递归遍历右子树 +12
}

@Override
public void breadthFirstTraversal() {
if (root == null)
return;
Queue<TreeNode<E>> queue = new LinkedList<>(); // Queue Deque Linkedlist
queue.add(root);
while (!queue.isEmpty()) {
TreeNode<E> current = queue.element();
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
System.out.println(queue.remove().element + " ");
}
}

/**以数组线性表返回节点的路径:
* 从根节点开始到该元素所在的节点
* 元素可能不在树中
*/
public ArrayList<TreeNode<E>> path(E e) {
ArrayList<TreeNode<E>> list = new ArrayList<>();
TreeNode<E> current = root;
while (current != null) {
list.add(current);
if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else {
break;
}
}
return list;
}

public int height() {
return height(root);
}
public int height(TreeNode<E> root) {
if (root == null)
return 0;
return 1 + Math.max(height(root.left), height(root.right));
}

@Override
public int getSize() {
return size;
}

public TreeNode<E> getRoot() {
return root;
}

public void clear() {
root = null;
size = 0;
}
/** 测试完全二叉树,完全二叉树的节点格式为 2^depth - 1 */
public boolean isFullBST() {
return size == Math.pow(2, height()) - 1 ? true : false;
}
/** 找出叶子节点的个数 */
public int getNumberOfLeaves() {
return getNumberOfLeaves(root);
}

protected int getNumberOfLeaves(TreeNode<E> root) {
if (root ==null)
return 0;
// If node has no children return 1
// else return the sum of all the leaves
return root.left == null && root.right == null ?
1 : getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
}

public int getNumberOfNonLeaves() {
return getNumberOfNonLeaves(root);
}

protected int getNumberOfNonLeaves(TreeNode<E> root) {
if (root == null) return 0;

// If node has children return 0
// else return 1 plus the sum of the nonleaves
return (root.left == null && root.right == null) ? 0 :
1 + getNumberOfNonLeaves(root.left) +
getNumberOfNonLeaves(root.right) ;
}

/** Returns true if two trees are equal.
Otherwise returns false (recursive) */
public boolean equals(BST<E> tree) {
if (tree.size != size) return false;
return equals(root, tree.root);
}

/** Equals helper */
protected boolean equals(TreeNode<E> root1, TreeNode<E> root2) {
if (root1 == root2) return true;
if (root1 == null || root2 == null) return false;
return root1.element.equals(root2.element) &&
equals(root1.left, root2.left) &&
equals(root1.right, root2.right);
}

@Override /** Override the protected clone method
defined in the Object class, and deep copy BST */
public BST<E> clone() throws CloneNotSupportedException {
BST<E> cloneBST = new BST<>();
clone(cloneBST, root);
return cloneBST;
}

/** Clone helper */
protected void clone(BST<E> clone, TreeNode<E> root) {
if (root == null) return;
clone.insert(root.element);
clone(clone, root.left);
clone(clone, root.right);
}

@Override
public Iterator<E> iterator() {
return new InorderIterator();
}

private class InorderIterator implements Iterator<E> {
private ArrayList<E> list = new ArrayList<>();
private int current = 0; // 指向线性表中的第一个元素

public InorderIterator() {
inorder();
}

private void inorder() {
inorder(root);
}
private void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}

@Override
public boolean hasNext() {
if (current < list.size()) // 检查current是否在list范围内
return true;
return false;
}
@Override
public E next() {
return list.get(current++); // 返回当前元素 然后current+1
}
@Override
public void remove() {
delete(list.get(current)); // 删除当前元素
list.clear(); // 清空线性表
inorder(); // 创建一个新的线性表,每次通过迭代器删除一个元素都要重新构造整个线性表
}

/* 在使得remove方法不被迭代器支持后,
* 无须为树中的元素维护一个线性表使得迭代器更加高效。
* 可以使用栈来存储节点
*
public void remove() {
throw new UnsupportedOparetionException("removing
an element from the iterator is not supported");
}
*/
}

/** Returns an iterator for traversing the elements in preorder */
public java.util.Iterator<E> preorderIterator() {
return new PreorderIterator();
}

// Inner class preorderIterator
private class PreorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list =
new java.util.ArrayList<>();
private int current = 0; // Point to the current element in list

public PreorderIterator() {
preorder(); // Traverse binary tree and store elements in list
}

/** Preorder traversal from the root */
private void preorder() {
preorder(root);
}

/** preorder traversal from a subtree */
private void preorder(TreeNode<E> root) {
if (root == null) return;
list.add(root.element);
preorder(root.left);
preorder(root.right);
}

@Override /** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;

return false;
}

@Override /** Get the current element and move to the next */
public E next() {
return list.get(current++);
}

@Override /** Remove the current element */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
preorder(); // Rebuild the list
}
}

/** This inner class is static, because it does not access
any instance members defined in its outer class */
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
}

BST的测试用例

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
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
import java.util.Iterator;

public class TestBST {
public static void main(String[] args) throws Exception {
// 广度优先遍历和树的高度
BST<String> strTree = new BST<>();
strTree.insert("George");
strTree.insert("Micheal");
strTree.insert("Tom");
strTree.insert("Adam");
strTree.insert("Jones");
strTree.insert("Peter");
strTree.insert("Daniel");

System.out.print("\nBreadth-first: ");
strTree.breadthFirstTraversal();
System.out.print("\nHeight of tree: ");
System.out.println(strTree.height());


// 测试完全二叉树
Integer[] numbers1 = {2, 4, 3, 1, 8, 5, 6, 7};
Integer[] numbers2 = {4, 2, 1, 3, 8, 5, 9};
Integer[] numbers3 = {10, 4, 2, 1, 3, 8, 5, 9, 15, 12, 11, 13, 21, 19, 25};
BST<Integer> intTree1 = new BST<>(numbers1);
BST<Integer> intTree2 = new BST<>(numbers2);
BST<Integer> intTree3 = new BST<>(numbers3);

System.out.print("\nIs tree #1 a full binary tree? ");
System.out.println(intTree1.isFullBST());
System.out.print("\nIs tree #2 a full binary tree? ");
System.out.println(intTree2.isFullBST());
System.out.print("\nIs tree #3 a full binary tree? ");
System.out.println(intTree3.isFullBST());


// 找出叶子节点和非叶子节点
Integer[] numbers = {60, 55, 45, 47, 59, 100, 76, 107, 101};
BST<Integer> intTree = new BST<>(numbers);

System.out.println("Number of leaf nodes: " +
intTree.getNumberOfLeaves());
System.out.println("Number of nonleaf nodes: " +
intTree.getNumberOfNonLeaves());


// 前序遍历
Integer[] numbers4 = {60, 55, 45, 48, 59, 100, 76, 107, 101};
BST<Integer> intTree4 = new BST<>(numbers4);

System.out.print("intTree: ");
intTree4.preorder();


// 测试clone方法
BST<Integer> intTreeCopy = intTree.clone();

// 测试equals方法
System.out.println("\nIs intTree equal to intTree2? " +
intTree.equals(intTree2));
System.out.println("Is intTree equal to intTreeCopy? " +
intTree.equals(intTreeCopy));

// 前序遍历
System.out.print("intTreeCopy: ");
intTreeCopy.preorder();
System.out.println();

// 测试前序迭代器
BST<String> tree0 = new BST<>();
tree0.insert("George");
tree0.insert("Michael");
tree0.insert("Tom");
tree0.insert("Adam");
tree0.insert("Jones");
tree0.insert("Peter");
tree0.insert("Daniel");

Iterator<String> iterator = tree0.preorderIterator();
while (iterator.hasNext())
System.out.print(iterator.next().toUpperCase() + " ");
System.out.println();
}
}

0%