二叉查找树的查找和排序方法的实现

*来自《算法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;
          }