二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点。
代码如下:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BST<T extends Comparable<? super T>> {
private Node<T> root;
public BST() {
}
public void put(T item) {
root = this.put(root, item);
}
/**
* 创建二叉排序树
*
* @param x
* @param item
* @return
*/
private Node<T> put(Node<T> x, T item) {
if (x == null) {
x = new Node<T>(item, null, null);
return x;
}
if (item.compareTo(x.item) < 0) {
x.left = put(x.left, item);
} else {
x.right = put(x.right, item);
}
return x;
}
public Node<T> search(T s) {
return search(this.root, s);
}
/**
* 递归查找要查找的值
*
* @param x
* @param s
* @return
*/
private Node<T> search(Node<T> x, T s) {
if (x == null) {
return null;
}
if (s.compareTo(x.item) < 0) {
return search(x.left, s);
} else if (s.compareTo(x.item) > 0) {
return search(x.right, s);
}
return x;
}
public Node<T> min() {
return min(root);
}
/**
* 查找二叉排序树中值最小的结点
*
* @param x
* @return
*/
private Node<T> min(Node<T> x) {
if (x.left == null) {
return x;
}
return min(x.left);
}
public Node<T> max() {
return max(root);
}
/**
* 查找二叉排序树中值最大的结点
*
* @param x
* @return
*/
private Node<T> max(Node<T> x) {
if (x.right == null) {
return x;
}
return max(x.right);
}
public void deleteMin() {
root = deleteMin(root);
}
/**
* 删除二叉排序树中的最小结点
*
* @param x
* @return
*/
private Node<T> deleteMin(Node<T> x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
return x;
}
public void delete(T s) {
root = delete(root, s);
}
/**
* 删除结点，要分三种情况考虑
* 1、如果要删除的结点是叶子结点，那么直接将它删去
* 2、如果要删除的结点有左或右孩子，那么将此节点删去，用它的左或右孩子取代它
* 3、如果要删除的结点有左右孩子，那么先查找此节点的右子树的最小结点，将此结点赋给要删除的那个节点，之后将此节点删除，然后将原来要删除结点的左右孩子分别赋给此节点；
*
* @param x
* @param s
* @return
*/
private Node<T> delete(Node<T> x, T s) {
if (x == null) {
return null;
}
if (s.compareTo(x.item) < 0) {
x.left = delete(x.left, s);
} else if (s.compareTo(x.item) > 0) {
x.right = delete(x.right, s);
} else {
if (x.left == null) {
return x.right;
}
if (x.right == null) {
return x.left;
}
Node<T> temp = x;
x = min(temp.right);
x.right = deleteMin(temp.right);
x.left = temp.left;
}
return x;
}
public void preOrderTraverse() {
this.preOrderTraverse(root);
}
/**
* 前序遍历树
*
* @param x
*/
private void preOrderTraverse(Node<T> x) {
if (x != null) {
System.out.print(x.item + " ");
preOrderTraverse(x.left);
preOrderTraverse(x.right);
}
}
public void inOrderTraverse() {
this.inOrderTraverse(root);
}
/**
* 中序遍历树
*
* @param x
*/
private void inOrderTraverse(Node<T> x) {
if (x != null) {
inOrderTraverse(x.left);
System.out.print(x.item + " ");
inOrderTraverse(x.right);
}
}
public void postOrderTraverse() {
this.postOrderTraverse(root);
}
/**
* 后序遍历树
*
* @param x
*/
private void postOrderTraverse(Node<T> x) {
if (x != null) {
postOrderTraverse(x.left);
postOrderTraverse(x.right);
System.out.print(x.item + " ");
}
}
/**
* 层次遍历树
*/
public void leverTraverse() {
Queue<Node<T>> queue = new LinkedList<Node<T>>();
Node<T> pnode = null;
queue.offer(root);
while (!queue.isEmpty()) {
pnode = queue.poll();
System.out.print(pnode.item + " ");
if (pnode.left != null) {
queue.offer(pnode.left);
}
if (pnode.right != null) {
queue.offer(pnode.right);
}
}
System.out.println();
}
/**
* 二叉排序树的树节点
*/
private class Node<T> {
T item;
Node<T> left;
Node<T> right;
public Node(T item, Node<T> left, Node<T> right) {
this.item = item;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "数据为：" + this.item + " " + "左孩子为：" + (this.left == null ? "null" : this.left.item) + " " +
"右孩子为：" + (this.right == null ? "null" : this.right.item);
}
}
}
总结
优点：插入，删除操作的时间复杂度都是O(log(n))级的，即经过O(log(n))时间搜索到了需插入和删除的节点的位置，后经过O(1)级的时间就可以直接插入和删除，比有序顺序表的插入和删除O(n)(查找O(log(n))，移动节点O(n))快，而和无序顺序表插入O(1)，删除O(n)比，因为是有序的，所以查找的速度要快很多。
缺点：二叉排序树的构造不止和最终节点的顺序有关，还和节点插入和删除的顺序有关，在某些特殊的情况下，树的高度可以等于节点的数量，于是查找的时间复杂度就退化成了O(n)了,相当也无序顺序表的查找
Q.E.D.
