public class BinarySearchTreesNode<T> {
	private int key;
	private T satelliteData;
	private BinarySearchTreesNode<T> parent, leftChild, rightChild;

	public BinarySearchTreesNode(int key, T satelliteData) {
		// TODO 自动生成的构造函数存根
		this.key = key;
		this.satelliteData = http://www.mamicode.com/satelliteData;>
2.     BST的建立
/**
 * @author Administrator
 * 
 */
public class BinarySearchTree<T> {
	private BinarySearchTreesNode<T> root;

	public BinarySearchTree() {
		// TODO 自动生成的构造函数存根
		root = null;
	}

	public BinarySearchTreesNode<T> getRoot() {
		return root;
	}

	public void setRoot(BinarySearchTreesNode<T> root) {
		this.root = root;
	}

	public BinarySearchTree(BinarySearchTreesNode<T> binarySearchTreesNode) {
		// TODO 自动生成的构造函数存根
		root = binarySearchTreesNode;
	}
}

二、   BST遍历
可以使用一般二叉树的遍历方法。
1.     中序遍历
	/* 算法导论288页伪代码，中序遍历， */
	public void inOrderTreeWalk(BinarySearchTreesNode<T> binarySearchTreesNode) {
		if (binarySearchTreesNode != null) {
			inOrderTreeWalk(binarySearchTreesNode.getLeftChild());
			System.out.println(binarySearchTreesNode.getKey() + ":"
					+ binarySearchTreesNode.getSatelliteData());
			inOrderTreeWalk(binarySearchTreesNode.getRightChild());
		}

	}

	public void inOrderTreeWalk() {
		inOrderTreeWalk(root);
	}
三、   BST的其他操作
1.     查找
《算法导论》P290 递归版本和循环版本
2.     最大key节点和最小key节点
《算法导论》P291 
public static BinarySearchTreesNode<String> getMinimum(BinarySearchTree<String> binarySearchTree) {
		BinarySearchTreesNode<String> node=binarySearchTree.getRoot();
		while (node.getLeftChild()!=null) {
			node=node.getLeftChild();
		}
		return node;	
	}
3.     后继和前驱
后继：节点x的后继指的是大于x.key的最小key的节点。两种情况：
1）  x的右子树不为空：后继为x的右子树最小key节点。
2）  x的右子树为空，x为左节点：返回x的父节点；
3）  x的右子树为空，x为右节点：x的父类节点都是有节点，则最终返回null；只要x的父类节点有左节点点，则返回该父类节点的父节点即可。
伪代码：
TREE-SUCCESSOR(X)
if x.right≠NIL
return TREE-MINIMUM(x.right)
y=x.parent
while y≠NIL and x==y.right
    x=y
    y=y.parent
return y
*******************************************************************************
《算法导论》P293页课后题12.2-3要求写出前驱的伪代码。同理，前驱即节点x的前驱指的是小于x.key的最大key的节点。仿照上面伪代码：
TREE-PREDECESSOR(X)
if x.left≠NIL
return TREE-MAXIMUM(x.left)
y=x.parent
while y≠NIL and x==y.left
    x=y
    y=y.parent
return y
4.     插入
插入节点一定是叶子节点，所以不断遍历到最后符合条件的位置即可。
/*
	 * 算法导论294页伪代码，BinarySearchTreesNode<T>
	 * x从root开始遍历，只要binarySearchTreesNode.getKey()<x.getKey()则遍历左边，反之遍历右边
	 * 最后temp是插入位置，x=null
	 */
	public void insert(BinarySearchTreesNode<T> binarySearchTreesNode) {
		BinarySearchTreesNode<T> temp = null;
		BinarySearchTreesNode<T> x = root;
		while (x != null) {
			temp = x;
			if (binarySearchTreesNode.getKey() < x.getKey()) {
				x = x.getLeftChild();
			} else {
				x = x.getRightChild();
			}
		}
		if (temp == null) {
			root = binarySearchTreesNode;
		} else if (binarySearchTreesNode.getKey() < temp.getKey()) {
			temp.setLeftChild(binarySearchTreesNode);
		} else {
			temp.setRightChild(binarySearchTreesNode);
		}
		// System.out.println("插入完成！");
	}

5.     删除
较复杂，《算法导论》P296
****************************************************************************
四、   BST转化为双向链表
参考：http://blog.csdn.net/ljianhui/article/details/22338405
java实现：待续
****************************************************************************
【一道面试题】：BST如何高效地找到中位数。
参考：http://blog.csdn.net/hhygcy/article/details/4654305
答案：BST转化为双向链表，双向链表是排好序的，两个指针一个速度是另一个两倍，快的移到最后，慢的即中位数。