二叉查找树简介
二叉查找树(Binary Search Tree), 也成二叉搜索树、有序二叉树(ordered binary tree)、排序二叉树(sorted binary tree)，
是指一棵空树或者具有下列性质的的二叉树：
1. 若任意节点的左子树不空，在左子树上所有结点的值均小于或等于它的根结点的值；
2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左子树、右子树也分别为二叉查找树。
4. 没有键值相等的结点(no duplicate nodes)
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度低。为O(log n)。二叉查找树是基础的数据结构，
用于构建更为抽象的数据结构，如集合，关联数组等。
结构示意图
简单的二叉查找树
实现
创建内部类Node作为树的节点，Node结点拥有左孩子(Left)和右孩子(Right)两个结点以及结点自身的值。
对于二叉查找树的基本算法插入(Insertion)、查找(Searching)、删除(Deletion)、遍历，递归方法使用的比较多。
毕竟树本身就是一种递归结构。~v~。广度优先遍历(breadthFisrt)使用到了队列这一数据结构。
删除元素算法相比其它算法而言有些复杂，我们需要考虑四种情况：
1. 待删除的元素是叶子节点；
2. 待删除的元素有右子树无左子树；
3. 待删除的元素有左子树无右子树；
4. 待删除的元素既有左子树又有右子树。
第一种情况： 删除叶子节点，只需要判断该叶子结点是父节点的左孩子还是右孩子，相应的将父节点的左孩子或右孩子
设为null。
第二种情况： 有右子树无左子树，判断待删除节点是父节点的左孩子还是右孩子，相应的将父节点的左孩子或右孩子设为
待删除节点的右子树。
第三种情况： 有左子树无右子树，判断待删除节点是父节点的左孩子还是右孩子，相应的将父节点的左孩子或右孩子设为
待删除节点的左子树。
第四种情况： 既有左子树又有右子树，这种情况的做法不唯一，此处只列出一种：从待删除节点的左子树找出最大值替代
待删除节点的值。
首先假定待删除节点(node)左子树的最大值为node的左孩子left，如果left右子树为空，则left的值为最大值，
替换掉node的值，相应的将left余下的节点上移。
若果left右子树不为空，找出left右子树最大值(最右边的节点)即为node整个左子树的最大值largestNode，
替换掉node的值，并将largestNode父节点的右子树设为null。
整体实现的代码如下：
1 import java.util.ArrayDeque; 2 import java.util.Collection; 3 import java.util.NoSuchElementException; 4 import java.util.Queue; 5 /** 6 * data structure unbalanced binary search tree 7 * @author michael 8 * @param <E> 9 */ 10 public class BinarySearchTree<E extends Comparable<E>> { 11 12 /** 13 * 二叉树节点个数 14 */ 15 int size = 0; 16 17 /** 18 * 根节点 19 */ 20 Node<E> root; 21 22 public BinarySearchTree() { 23 // TODO Auto-generated constructor stub 24 } 25 26 /** 27 * 插入一个元素 28 * 若根节点为空，新建一个节点作为根节点并把element(需要插入的值)赋给根节点； 29 * 根节点不为空，将element与根节点的值进行比较 30 * 若小于等于根节点的值，判断根节点的左子树是否为空 31 * 如果为空，新建左子树并赋值； 32 * 否则，递归调用比较。 33 * 若大于根节点的值，判断根节点的右子树是否为空 34 * 如果为空，新建右子树并赋值； 35 * 否则，递归调用比较。 36 * @param element 需要插入的值 37 */ 38 public void add(E element) { 39 if(root == null) { 40 root = new Node<E>(null, element, null); 41 } else { 42 addNode(root, element); 43 } 44 size++; 45 } 46 47 /** 48 * 插入一个元素的具体实现(递归) 49 * @param current 当前节点 50 * @param element 需要插入的值 51 */ 52 private void addNode(Node<E> current, E element) { 53 // assert current not null 54 if(element.compareTo(current.item) <= 0) { 55 if(current.left == null) { 56 current.left = new Node<E>(null, element, null); 57 } else { 58 addNode(current.left, element); 59 } 60 } else { 61 if(current.right == null) { 62 current.right = new Node<E>(null, element, null); 63 } else { 64 addNode(current.right, element); 65 } 66 } 67 } 68 69 /** 70 * 查找一个元素是否为二叉树节点值 71 * 首先和根节点的值进行比较 72 * 若相等，找到，返回true； 73 * 不相等，再和左孩子的值进行比较 74 * 如果小于等于左孩子的值，则将左孩子作为根节点递归调用。 75 * 否则将右孩子作为根节点递归调用。 76 * @param element 待查找的元素 77 * @return 找到返回true；树为空或未找到返回false 78 */ 79 public boolean contains(E element) { 80 return containsNode(root, element); 81 } 82 83 /** 84 * contains具体实现(递归) 85 * @param current 当前节点 86 * @param element 待查找的元素 87 * @return 88 */ 89 private boolean containsNode(Node<E> current, E element) { 90 if(current == null) { 91 return false; 92 } 93 94 if(element.equals(current.item)) { 95 return true; 96 } else if(element.compareTo(current.item) <= 0) { 97 return containsNode(current.left, element); 98 } else { 99 return containsNode(current.right, element); 100 } 101 } 102 103 /** 104 * 获得指定元素的父节点 105 * 如果element等于根节点的值，本身为根节点，无父节点，返回null 106 * 如果element小于等于当前节点(current)的值 107 * 判断当前节点的左孩子(left)是否为空 108 * 空，二叉树没有element元素，返回null 109 * 不空，将左孩子的值和element比较，等于返回current；否则，将left作为当前节点递归调用。 110 * 否则(element大于当前节点的值) 111 * 判断当前节点的右孩子(right)是否为空 112 * 空，二叉树没有element元素，返回null 113 * 不空，将右孩子的值和element比较，等于返回current；否则，将right作为当前节点递归调用。 114 * @param current 当前节点 115 * @param element 待查找元素 116 * @return 117 */ 118 private Node<E> getParent(Node<E> current, E element) { 119 // assert root not null 120 if(element.equals(root.item)) { 121 return null; 122 } 123 124 if(element.compareTo(current.item) <= 0) { 125 if(current.left == null) { 126 return null; 127 } else if(element.equals(current.left.item)) { 128 return current; 129 } else { 130 return getParent(current.left, element); 131 } 132 } else { 133 if(current.right == null) { 134 return null; 135 } else if(element.equals(current.right.item)) { 136 return current; 137 } else { 138 return getParent(current.right, element); 139 } 140 } 141 } 142 143 /** 144 * 给定元素值获得该元素节点 145 * @param root 根节点 146 * @param element 给定元素 147 * @return 该元素节点 148 */ 149 private Node<E> getNode(Node<E> root, E element) { 150 if(root == null) { 151 return null; 152 } 153 154 if(element.equals(root.item)) { 155 return root; 156 } else if(element.compareTo(root.item) <= 0) { 157 return getNode(root.left, element); 158 } else { 159 return getNode(root.right, element); 160 } 161 } 162 163 /** 164 * 删除元素 165 * 删除元素为 166 * 叶子节点 167 * 有右子树无左子树 168 * 有左子树无右子树 169 * 既有右子树又有左子树 170 * @param element 待删除的元素 171 */ 172 public void remove(E element) { 173 Node<E> node = getNode(root, element); 174 175 if(node == null) { 176 throw new NoSuchElementException(); 177 } 178 179 Node<E> parent = getParent(root, element); 180 181 if(size == 1) { 182 root = null; 183 } else if(node.left == null && node.right == null) { 184 removeLeaf(parent, node); 185 } else if(node.left == null && node.right != null) { 186 if(element.compareTo(parent.item) < 0) { 187 parent.left = node.right; 188 } else { 189 parent.right = node.right; 190 } 191 } else if(node.left != null && node.right == null) { 192 if(element.compareTo(parent.item) < 0) { 193 parent.left = node.left; 194 } else { 195 parent.right = node.left; 196 } 197 } else { 198 Node<E> largest = node.left; 199 if(largest.right == null) { 200 node.item = largest.item; 201 node.left = largest.left; 202 largest = null; 203 } else { 204 while(largest.right != null) { 205 largest = largest.right; 206 } 207 Node<E> largestParent = getParent(node, largest.item); 208 largestParent.right = null; 209 node.item = largest.item; 210 } 211 } 212 size--; 213 } 214 215 /** 216 * 删除叶子节点 217 * 判断待删除的叶子节点是父节点的左孩子还是右孩子，相应的将父节点的左孩子或右孩子设为null 218 * @param parent 父节点 219 * @param leaf 叶子节点 220 */ 221 private void removeLeaf(Node<E> parent, Node<E> leaf) { 222 E element = leaf.item; 223 if(element.compareTo(parent.item) < 0) { 224 parent.left = null; 225 } else { 226 parent.right = null; 227 } 228 } 229 230 /** 231 * 先序遍历 232 * 根结点-左子树-右子树 233 * @param root 根结点 234 * @param container 存储容器 235 */ 236 public void preOrder(Collection<E> container) { 237 preOrderNode(root, container); 238 } 239 240 private void preOrderNode(Node<E> root, Collection<E> container) { 241 if(root != null) { 242 container.add(root.item); 243 preOrderNode(root.left, container); 244 preOrderNode(root.right, container); 245 } 246 247 } 248 249 /** 250 * 中序遍历 251 * 左子树-根结点-右子树 252 * @param root 根结点 253 * @param container 存储容器 254 */ 255 public void inOrder(Collection<E> container) { 256 inOrderNode(root, container); 257 } 258 259 private void inOrderNode(Node<E> root, Collection<E> container) { 260 if(root != null) { 261 inOrderNode(root.left, container); 262 container.add(root.item); 263 inOrderNode(root.right, container); 264 } 265 } 266 267 /** 268 * 后序遍历 269 * 左子树-右子树-根结点 270 * @param root 根结点 271 * @param container 存储容器 272 */ 273 public void postOrder(Collection<E> container) { 274 postOrderNode(root, container); 275 } 276 277 private void postOrderNode(Node<E> root, Collection<E> container) { 278 if(root != null) { 279 postOrderNode(root.left, container); 280 postOrderNode(root.right, container); 281 container.add(root.item); 282 } 283 } 284 285 /** 286 * 广度优先遍历 287 * 使用队列 将同一高度的节点依次入队出队。 288 * @param container 存储容器 289 */ 290 public void breadthFirst(Collection<E> container) { 291 Node<E> node = root; 292 Queue<Node<E>> q = new ArrayDeque<Node<E>>(); 293 while(node != null) { 294 container.add(node.item); 295 if(node.left != null) { 296 q.add(node.left); 297 } 298 if(node.right != null) { 299 q.add(node.right); 300 } 301 if(!q.isEmpty()) { 302 node = q.poll(); 303 } else { 304 node = null; 305 } 306 } 307 } 308 309 /** 310 * 获取二叉查找树的大小 311 * @return size 312 */ 313 public int size() { 314 return size; 315 } 316 317 /** 318 * 最小值 319 * @return 二叉查找树最小值 320 */ 321 public E min() { 322 return getMin(root); 323 } 324 325 /** 326 * 获取最小值 327 * 根据性质，最小值为二叉查找树最左边的节点值 328 * @param root 根结点 329 * @return 最小值 330 */ 331 public E getMin(Node<E> root) { 332 // assert root not null 333 if(root.left == null) { 334 return root.item; 335 } else { 336 return getMin(root.left); 337 } 338 } 339 340 /** 341 * 最大值 342 * @return 二叉查找树最大值 343 */ 344 public E max() { 345 return getMax(root); 346 } 347 348 /** 349 * 获取最大值 350 * 根据性质，最大值为二叉查找树最右边的节点值 351 * @param root 352 * @return 最大值 353 */ 354 public E getMax(Node<E> root) { 355 // assert root not null 356 if(root.right == null) { 357 return root.item; 358 } else { 359 return getMax(root.right); 360 } 361 } 362 363 /** 364 * 内部类 表示树节点 365 * @author michael 366 * @param <E> 367 */ 368 private static class Node<E> { 369 E item; 370 Node<E> left; 371 Node<E> right; 372 373 /** 374 * 构造一个新节点并指定左孩子和右孩子 375 * @param left 左孩子 376 * @param item 节点值 377 * @param right 右孩子 378 */ 379 Node(Node<E> left, E item, Node<E> right) { 380 this.left = left; 381 this.item = item; 382 this.right = right; 383 } 384 } 385 386 }
Fork me on GitHub:https://github.com/michaelwong95