用java源代码学数据结构<七>: BST

 
/* 
 * 以int类为例 
 * 其它的类必须能够比较 
 * */  
  
//二叉搜索树的节点点  
    class BSTNode{        
  
        int item;  
        BSTNode lc;  
        BSTNode rc;  
        BSTNode p;        
          
        public BSTNode(int item){  
            this.item = item;  
        }         
    }     
  
  
public class BST{  
          
    //BST的根  
    transient BSTNode root;  
      
    //树的大小  
    transient int size = 0;   
      
    public BST(){  
        root = null;  
    }  
      
    public BST(int rootData){  
        root = new BSTNode(rootData);  
        size++;  
    }  
      
    //向二叉树搜索树中插入一个节点  
    private void addNode(BSTNode z){  
        if (root==null) {  
            root = z;  
            return;  
        }  
        BSTNode y = null;  
        BSTNode x = root;  
        while(x!=null){  
            //用y来保存x  
            y = x;  
            //找到z应该放置的位置  
            if(z.item < x.item)  
                x = x.lc;  
            else   
                x = x.rc;  
        }  
        z.p = y;  
        //如果y为null表示root为空  
        if (y==null) {  
            root = z;  
            return;  
        }  
        else {  
            //比较y和z,来设置y的lc和rc  
            if (z.item < y.item)   
                y.lc = z;  
            else   
                y.rc = z;  
        }  
        size++;  
          
    }  
      
    //找到BST中第一个元素为item的对象,从x节点开始找  
    private BSTNode findNodeByitem(BSTNode x,int item){  
        while (x!=null && x.item!=item) {  
            if (item < x.item)  
                x = x.lc;  
            else   
                x = x.rc;             
        }  
        return x;  
    }  
      
    private BSTNode minimum(BSTNode x){  
        if (x==null) {  
            return null;  
        }  
        while (x.lc!=null) {  
            x = x.lc;  
        }  
        return x;  
    }  
      
    private BSTNode maximum(BSTNode x){  
        if (x==null) {  
            return null;  
        }  
        while (x.rc!=null) {  
            x = x.rc;  
        }  
        return x;  
    }  
    private void transPlant(BSTNode u,BSTNode v){  
        if (u.p==null) {  
            root = v;  
        }  
        else {  
            if (u==u.p.lc) {  
                u.p.lc = v;  
            }  
            else {  
                u.p.rc = v;  
            }  
        }  
        if (v!=null) {  
            v.p = u.p;  
        }  
    }  
      
    //删除x节点   
    private void removeNode(BSTNode z){  
        if (z==null) {  
            return;  
        }  
        if (z.lc==null) {  
            transPlant(z, z.rc);  
        }  
        else {  
            if (z.rc==null) {  
                transPlant(z, z.lc);  
            }  
            else {  
                BSTNode y = minimum(z.rc);  
                if (y.p!=z) {  
                    transPlant(y, y.rc);  
                    y.rc = z.rc;  
                    y.rc.p = y;  
                }  
                transPlant(z, y);  
                y.lc = z.lc;  
                y.lc.p = y;  
            }  
        }  
        size--;  
    }  
      
      
    private BSTNode getNodeByitem(int item){  
        return findNodeByitem(root, item);  
    }  
      
    public void addItem(int item){  
        BSTNode t = new BSTNode(item);  
        addNode(t);  
    }  
      
    public void removeItem(int item){  
        BSTNode tBstNode = findNodeByitem(root, item);  
        removeNode(tBstNode);  
    }  
      
    public int getMax(){  
        return maximum(root).item;  
    }  
      
    public int getMin(){  
        return minimum(root).item;  
    }  
      
    private void print(BSTNode x){  
        if (x==null) {  
            return ;  
        }  
        print(x.lc);  
        System.out.print("["+x.item+"]");  
        print(x.rc);  
    }  
      
    public void printAll(){  
        if (root==null) {  
            return;  
        }  
        print(root);  
    }  
      
      
    public static void main(String[] args) {  
        BST bst = new BST();  
        bst.addItem(15);  
        bst.addItem(6);  
        bst.addItem(18);  
        bst.addItem(3);  
        bst.addItem(7);  
        bst.addItem(17);  
          
        bst.printAll();  
        System.out.println();  
          
        bst.removeItem(6);  
        bst.printAll();  
        System.out.println();  
          
        bst.removeItem(10);  
        bst.printAll();  
        System.out.println();  
          
        System.out.println("Max="+bst.getMax());  
        System.out.println("Min="+bst.getMin());  
    }  
      
      
  
}  

补充：软件开发 , Java ,

上一个：算法小题：m个相同的苹果，放在n个相同的盘子中，求有多少种结果
下一个： 用java源代码学数据结构<二>: Vector 详解