*来自《算法4》
定义二叉树
public BST extends Comparable<Key , Value>{
private Node root;///根节点
privare class Node{
private Key key; //键
private Value val;//值
private Node left,right//指向子树的链接
private int N;//以该结点为根的子树中的结点总数
private Node(Key key,Value val,int N){
this.key=key,this.val=val;this.N=N;
}
private void put(Key key){}
private void get(Key key,Value val){}
}
}
二叉查找树的查找和排序方法的实现
public Value get(Key key){
return get(root,key);
}
private Value get(Node x,Key key){
//以x为根结点的子树中查找并返回key所对应值
//如何找不到返回null
if（x==null） return null;
}
int cmp=key.compareTo(x.key);
if（cmp<0）{
return get(x.left,key);
}
else if（cmp>0）{
return get(key,x.right);
}
else{
return x.val;
}
public void put(Key key,Value val){
//查找key,找到则更新它的值，否则为它创建一个新的结点
root=put(root,key,val);
}
private Node put(Node x,Key key,Value val){
//如果key存在以x为根结点的子树则更新它的值，否则
//将以key和val为键值对插入到该子树中
if(x==null) return new Node(key,val,1);
int cmp=key.compareTo(x.key);
if（cmp<0）{
return put(x.left,key,val);
}
else if（cmp>0）{
return get(key,x.right,val);
}
else x.val=val;
x.N=size(x.left+1)+size(x.right+1)+1;
return x;
}
