0%

查找-二叉搜索树（Java实现）

发表于 更新于 分类于

前言

如果查找的数据集是有序的线性表，并且是顺序存储的，查找可以用折半查找、插值查找、斐波那契查找算法（详细算法见：有序表查找（折半、插值、斐波那契查找））等实现。但是正是因为他们是顺序的，所以在插入和删除操作中需要耗费大量时间，也就是说这些算法适合静态查找（只有查找操作），不适合动态查找（不仅有查找操作还有插入删除等操作）。而二叉搜索树正适合动态查找。

定义

二叉搜索树又称为二叉排序树，它或者是空树，或者是具有下列性质的二叉树：

  1. 如果它的左子树不为空，那么左子树的所有节点都小于根节点的值；
  2. 如果它的右子树不为空，那么右子树的所有节点都大于根节点的；
  3. 它的左、右子树也分别是二叉搜索树.

二叉树是递归定义的数据结构，其中序遍历是递增的有序序列。

操作

1. 插入
插入节点的过程是：若原二叉查找树为空，则直接插入；否则，若关键字 k 小于根节点关键字，则插入到左子树中，若关键字 k 大于根节点关键字，则插入到右子树中。注意每次插入的节点必是叶节点。

2. 删除
二叉查找树的删除操作是相对复杂一点，它要按 3 种情况来处理：

  • 若被删除节点 t 是叶子节点，则直接删除，不会破坏二叉排序树的性质；
  • 若节点 t 只有左子树或只有右子树，则让 t 的子树成为 t 父节点的子树，替代 t 的位置；
  • 若节点 t 既有左子树，又有右子树，则用 t 的直接前驱或者直接后继代替 t，然后从二叉查找树中删除这个后继，这样就转换成了第一或第二种情况。

3. 查找
查找是从根节点开始，若二叉树非空，将给定值与根节点的关键字比较，若相等，则查找成功；若不等，则当给定值小于根节点关键字时，在根节点的左子树中查找，否则在根节点的右子树中查找。
其查找平均时间复杂度为O(logn)，但是最差情况为插入的节点是有序的，则该二叉搜索树会变成左斜树(或者右斜树或者可以理解为“链表”)，即最差时间复杂度为O(n)，故而查找性能不是严格意义上的O(logn)，不稳定。

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
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
public class SortedBinaryTree<E> {

	private Node<E> root; // 根节点

	private int size; // 二叉树元素个数

	/**
	 * 二叉树节点
	 */
	private static class Node<E> {
		E element; // 节点元素
		Node<E> lChild; // 左孩子
		Node<E> rChild; // 右孩子

		public Node(E element) {
			this(element, null, null);
		}

		public Node(E element, Node<E> lChild, Node<E> rChild) {
			this.element = element;
			this.lChild = lChild;
			this.rChild = rChild;
		}
	}

	public SortedBinaryTree(List<E> elements) {
		for (E e : elements) {
			add(e);
		}
	}

	public SortedBinaryTree(E[] elements) {
		for (E e : elements) {
			add(e);
		}
	}

	public SortedBinaryTree() {
	}

	/**
	 * 判断当前元素是否存在于树中
	 * 
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return search(root, element);
	}

	/**
	 * 递归搜索,查找当前以curRoot为根节点的树中element存在与否
	 * 
	 * @param curRoot
	 * @param element
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private boolean search(Node<E> curRoot, E element) {
		if (curRoot == null)
			return false;
		Comparable<? super E> e = (Comparable<? super E>) element;
		int cmp = e.compareTo(curRoot.element);
		if (cmp > 0) {
			// 查找的元素大于当前根节点对应的元素,向右走
			return search(curRoot.rChild, element);
		} else if (cmp < 0) {
			// 查找的元素小于当前根节点对应的元素,向左走
			return search(curRoot.lChild, element);
		} else {
			// 查找的元素等于当前根节点对应的元素,返回true
			return true;
		}
	}

	/**
	 * 非递归搜索,查找当前以curRoot为根节点的树中的element是否存在
	 * 
	 * @param curRoot
	 *            二叉排序树的根节点
	 * @param element
	 *            被搜索的元素
	 * @param target
	 *            target[0]指向查找路径上最后一个节点: 如果当前查找的元素存在,则target[0]指向该节点
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private boolean find(Node<E> curRoot, E element, Node<E>[] target) {
		if (curRoot == null)
			return false;
		Node<E> tmp = curRoot;
		Comparable<? super E> e = (Comparable<? super E>) element;
		while (tmp != null) {
			int cmp = e.compareTo(tmp.element);
			target[0] = tmp;
			if (cmp > 0) {
				// 查找的元素大于当前节点对应的元素,向右走
				tmp = tmp.rChild;
			} else if (cmp < 0) {
				// 查找的元素小于当前节点对应的元素,向左走
				tmp = tmp.lChild;
			} else {
				// 查找的元素等于当前根节点对应的元素,返回true
				return true;
			}
		}
		return false;
	}

	/**
	 * 向二叉排序树中添加元素,如果当前元素已经存在,则添加失败,返回false,如果当前元素不存在,则添加成功,返回true
	 * 
	 */
	@SuppressWarnings("unchecked")
	public boolean add(E element) {
		if (root == null) {
			root = new Node<E>(element);
			size++;
			return true;
		}
		Node<E>[] target = new Node[1];
		if (!find(root, element, target)) {
			// 当前元素不存在,插入元素
			// 此时target节点即为需要插入的节点的父节点
			Comparable<? super E> e = (Comparable<? super E>) element;
			int cmp = e.compareTo(target[0].element);
			Node<E> newNode = new Node<E>(element);
			if (cmp > 0) {
				// 插入的元素大于target指向的节点元素
				target[0].rChild = newNode;
			} else {
				// 插入的元素小于target指向的节点元素
				target[0].lChild = newNode;
			}
			size++;
			return true;
		}
		return false;
	}

	/**
	 * 删除二叉排序树中的元素,如果当前元素不存在,则删除失败,返回false;如果当前元素存在,则删除该元素,重构二叉树,返回true
	 * 
	 * @param element
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public boolean remove(E element) {
		Node<E>[] target = new Node[1];
		if (find(root, element, target)) {
			// 被删除的元素存在,则继续执行删除操作
			remove(target[0]);
			return true;
		}
		return false;
	}

	/**
	 * 释放当前节点
	 * 
	 * @param node
	 */
	private void free(Node<E> node) {
		node.element = null;
		node.lChild = null;
		node.rChild = null;
		node = null;
	}

	/**
	 * 删除二叉排序树中指定的节点
	 * 
	 * @param node
	 */
	private void remove(Node<E> node) {
		Node<E> tmp;
		if (node.lChild == null && node.rChild == null) {
			// 当前node为叶子节点,删除当前节点,则node = null;
			node = null;
		} else if (node.lChild == null && node.rChild != null) {
			// 如果被删除的节点左子树为空,则只需要重新连接其右子树
			tmp = node;
			node = node.rChild;
			free(tmp);
		} else if (node.lChild != null && node.rChild == null) {
			// 如果被删除的节点右子树为空,则只需要重新连接其左子树
			tmp = node;
			node = node.lChild;
			free(tmp);
		} else {
			// 当前被删除的节点左右子树均存在,不为空
			// 找到离当前node节点对应元素且最近的节点target(左子树的最右边节点 或者 右子树最左边节点)
			// 将node节点元素替换成target节点的元素,将target节点删除
			tmp = node; // tmp是target的父节点
			Node<E> target = node.lChild; // 找到左子树最大子树
			while (target.rChild != null) { // 在左子树中进行右拐
				tmp = target;
				target = target.rChild;
			}
			node.element = target.element; // node.element元素替换为target.element
			if (tmp == node) {
				// tmp == node 说明没有在左子树中进行右拐,也就是node节点的左孩子没有右孩子,
				// 需要重新连接tmp节点左孩子
				tmp.lChild = target.lChild;
			} else {
				// tmp != node, 进行了右拐,那么将重新连接tmp的右子树,将target.lChild赋值给tmp.rChild
				tmp.rChild = target.lChild;
			}
			// 释放节点
			free(target);
		}
		// 删除成功,size--;
		size--;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size() == 0;
	}

	public List<E> preOrderTraverse() {
		List<E> list = new ArrayList<E>();
		preOrderTraverse(root, list);
		return list;
	}

	private void preOrderTraverse(Node<E> curRoot, List<E> list) {
		if (curRoot == null)
			return;
		E e = curRoot.element;
		list.add(e);
		preOrderTraverse(curRoot.lChild, list);
		preOrderTraverse(curRoot.rChild, list);
	}

	public List<E> inOrderTraverse() {
		List<E> list = new ArrayList<E>();
		inOrderTraverse(root, list);
		return list;
	}

	private void inOrderTraverse(Node<E> curRoot, List<E> list) {
		if (curRoot == null)
			return;
		inOrderTraverse(curRoot.lChild, list);
		list.add(curRoot.element);
		inOrderTraverse(curRoot.rChild, list);
	}

	public List<E> postOrderTraverse() {
		List<E> list = new ArrayList<E>();
		postOrderTraverse(root, list);
		return list;
	}

	private void postOrderTraverse(Node<E> curRoot, List<E> list) {
		if (curRoot == null)
			return;
		inOrderTraverse(curRoot.lChild, list);
		inOrderTraverse(curRoot.rChild, list);
		list.add(curRoot.element);
	}

	/**
	 * 返回中序遍历结果
	 */
	@Override
	public String toString() {
		return inOrderTraverse().toString();
	}

	public static void main(String[] args) {
		Integer[] elements = new Integer[] { 62, 88, 58, 47, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 48, 50 };
		SortedBinaryTree<Integer> tree = new SortedBinaryTree<Integer>(elements);
		System.out.println(tree);
		System.out.println(tree.contains(93));
		System.out.println(tree.size());
		System.out.println(tree.remove(47));
		System.out.println(tree.preOrderTraverse());
		System.out.println(tree.size());
	}

}

Github地址
SortedBinaryTree