import java.util.concurrent.ConcurrentLinkedQueue;
/**
 * Created by IntelliJ IDEA.
 * User: motor
 * Date: 2007-6-1
 * Time: 20:38:47
 * 排序二叉树.
 */
public class BSTree {
//定义根节点
    BSTNode root;
//定义树的深度
    int level;
//定义构造方法，创建一颗新二叉树
    public BSTree(){
        root=null;
    }
//判断二叉树是否为空
    public boolean isEmpty(){
        return root==null;
    }
//插入新节点
    public void insert(int o){
        if(isEmpty())
            this.root=new BSTNode(o);
        else{
            BSTNode tmp=this.root;
            boolean flag=false;
            while((tmp.left!=null||tmp.right!=null)&&!flag){
                if(tmp.left!=null&&tmp.right==null){
                    if(tmp.data>o)
                        tmp=tmp.left;
                    else
                        flag=true;
                }
                if(tmp.left==null&&tmp.right!=null){
                    if(tmp.data>o)
                        flag=true;
                    else
                        tmp=tmp.right;
                }
                if(tmp.left!=null&&tmp.right!=null){
                    if(tmp.data>o)
                        tmp=tmp.left;
                    else
                        tmp=tmp.right;
                }
            }
            if(tmp.data>o)
                tmp.left=new BSTNode(o);
            else
                tmp.right=new BSTNode(o);
        }
    }
//删除节点
    public BSTNode delete(int o){
        if(isEmpty()){
            System.err.println("这是一颗空二叉树");
            return null;
        }else{
            BSTNode tmp=root;
            BSTNode buf=null;
            boolean flag=true;
            while(tmp!=null){
                if(tmp.data>o){
                    buf=tmp;
                    tmp=tmp.left;
                    flag=true;
                }
                else if(tmp.data<o){
                    buf=tmp;
                    tmp=tmp.right;
                    flag=false;
                }
                else{
                    if(buf==null){
                        if(root.left==null&&root.right==null){
                            int n=root.data;
                            root=null;
                            return new BSTNode(n);
                        }else if(root.left!=null&&root.right!=null){
                            BSTNode N=root.left;
                            while(N.right!=null)
                                N=N.right;
                            N.right=root.right;
                            BSTNode rootin=root;
                            root=root.left;
                            rootin.left=null;
                            rootin.right=null;
                            return rootin;
                        }else{
                            if(root.left!=null){
                                BSTNode rootin=root;
                                root=root.left;
                                rootin.left=null;
                                return rootin;
                            }else{
                                BSTNode rootin=root;
                                root=root.right;
                                rootin.right=null;
                                return rootin;
                            }
                        }
                    }
//如果tmp的左右节点都为空，只需要改变tmp父节点的左右指向=null即可
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点                    
                    if(tmp.left==null&&tmp.right==null){
                        if(flag){
                            buf.left=null;
                            return tmp;
                        }else{
                            buf.right=null;
                            return tmp;
                        }
                    }else if(tmp.left==null&&tmp.right!=null){
//如果tmp只有一个子节点，就把该子节点作为tmp父节点的相应子节点即可
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点
                        if(flag){
                            buf.left=tmp.right;
                            tmp.right=null;
                            return tmp;
                        }else{
                            buf.right=tmp.right;
                            tmp.right=null;
                            return tmp;
                        }
                    }else if(tmp.left!=null&&tmp.right==null){
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点                       
                        if(flag){
                            buf.left=tmp.left;
                            tmp.left=null;
                            return tmp;
                        }else{
                            buf.right=tmp.left;
                            tmp.left=null;
                            return tmp;
                        }
                    }else{
/**
 * 如果tmp的左右节点都不为空，则把tmp的左节点作为tmp父节点的左节点，
 * 把tmp的右节点作为tmp前驱节点。前驱节点是中序遍历时tmp的前遍历。
 * 先找tmp的左节点S，再不断遍历S的右节点，直到S的右节点为空，则S就是tmp的前驱节点。
 */
                        BSTNode S=tmp.left;
                        while(S.right!=null)
                            S=S.right;
                        S.right=tmp.right;
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点
                        if(flag)
                            buf.left=tmp.left;
                        else
                            buf.right=tmp.left;
                        tmp.left=null;
                        tmp.right=null;
                        return tmp;
                    }
                }
            }
            System.err.println("找不到该节点");
            return null;
        }
    }
//建造一棵二叉树
    public void build(int[] on){
        for(int i=0;i<on.length;i++)
            insert(on[i]);
    }
//获取二叉树的深度
    public int depth(BSTNode n){
        if(n==null)
            return 0;
        else
            return depth(n.left)>depth(n.right)?depth(n.left)+1:depth(n.right)+1;
    }
//中序遍历二叉树
    public void printmid(BSTNode n){
        if(n!=null){
            printmid(n.left);
            System.out.print(n.data+" ");
            printmid(n.right);
        }
    }
//前序遍历二叉树
    public void printfro(BSTNode n){
        if(n!=null){
            System.out.print(n.data+" ");
            printfro(n.left);
            printfro(n.right);
        }
    }
//后序遍历二叉树
    public void printbeh(BSTNode n){
        if(n!=null){
            printbeh(n.left);
            printbeh(n.right);
            System.out.print(n.data+" ");
        }
    }
//层次遍历二叉树
//先被访问节点的子节点要早于后被访问节点的子节点被访问，所以用FIFO队列实现    
    public void printlev(BSTNode n){
        if(n!=null){
            ConcurrentLinkedQueue<BSTNode> q=new ConcurrentLinkedQueue<BSTNode>();
            System.out.print(n.data+" ");
            if(n.left!=null)
                q.offer(n.left);
            if(n.right!=null)
                q.offer(n.right);
            while(!q.isEmpty()){
                BSTNode tmp= q.poll();//从对列中取出数据
                System.out.print(tmp.data+" ");
                if(tmp.left!=null)//左节点不为空就入队列
                    q.offer(tmp.left);
                if(tmp.right!=null)//右节点不为空就入队列
                    q.offer(tmp.right);
            }
        }
    }

//判断此二叉树是否平衡
    public boolean isBalance(BSTNode n){
        if(n!=null){
            if(depth(n.left)-depth(n.right)>1||depth(n.right)-depth(n.left)>1)
                return false;
            else
                return isBalance(n.left)&&isBalance(n.right);
        }
        return true;
    }
}
class BSTNode{
    BSTNode left;
    BSTNode right;
    int data;
    BSTNode(BSTNode l,int o,BSTNode r){
        this.left=l;
        this.data=o;
        this.right=r;
    }
    BSTNode(BSTNode l,int o){
        this(l,o,null);
    }
    BSTNode(int o,BSTNode r){
        this(null,o,r);
    }
    BSTNode(int o){
        this(null,o,null);    
    }
}