二叉查找树（Binary Search Tree）又称二叉排序树（Binary Sort Tree），亦称二叉搜索树。，或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
二叉排序树通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT(Size Balanced Tree),AVL,红黑树等.故不失为一种好的动态排序方法.
二叉查找树的实现（java）
节点实现类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class BinaryNode<T> { T element; BinaryNode<T> left; BinaryNode<T> right; public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) { super(); this.element = element; this.left = left; this.right = right; } public BinaryNode(T element) { this(element, null, null); } } |
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 |
public class BinarySearchTree<T extends Comparable<? super T>> { private BinaryNode<T> root; public BinarySearchTree() { root = null; } public void makeEmpty() { root = null; } public boolean isEmpty() { return root == null; } public boolean contains(T x) { return contains(x, root); } private boolean contains(T x, BinaryNode<T> t) { if (x == null) throw new IllegalArgumentException("参数异常！"); if (t == null) return false; int compareResult = x.compareTo(t.element); if (compareResult == 0) return true; else if (compareResult < 0) return contains(x, t.left); else return contains(x, t.right); } public T findMax() { if (isEmpty()) return null; return findMax(root); } // 递归 private T findMax(BinaryNode<T> t) { if (t.right == null) return t.element; else return findMax(t.right); } public T findMin() { if (isEmpty()) return null; return findMin(root); } // 非递归 private T findMin(BinaryNode<T> t) { while (t.left != null) { t = t.left; } return t.element; } public void insert(T x) { root = insert(x, root); } // 递归 private BinaryNode<T> insert(T x, BinaryNode<T> t) { if (x == null) throw new IllegalArgumentException("参数异常！"); if (t == null) return new BinaryNode<T>(x); int compareResult = x.compareTo(t.element); if (compareResult < 0) t.left = insert(x, t.left); else if (compareResult > 0) t.right = insert(x, t.right); else ; return t; } public void remove(T x) { root = remove(x, root); } private BinaryNode<T> remove(T x, BinaryNode<T> t) { if (x == null) throw new IllegalArgumentException("参数异常！"); if (t == null) return null; int compareResult = x.compareTo(t.element); if (compareResult < 0) t.left = remove(x, t.left); else if (compareResult > 0) t.right = remove(x, t.right); else if (t.left != null && t.right != null) { t.element = findMin(t.right); t.right = remove(t.element, t.right); } else t = (t.left != null) ? t.left : t.right; return t; } public static void main(String[] f) { BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>(); System.out.println(bst.contains(1)); bst.insert(1); bst.insert(3); bst.insert(6); bst.insert(5); System.out.println(bst.contains(1)); System.out.println(bst.findMax()); System.out.println(bst.findMin()); System.out.println(bst.contains(5)); bst.remove(5); System.out.println(bst.contains(5)); } } |
