二叉树基础

普通的二叉树可以通过下面代码创造出来:

//递归定义法
class Bitree{
    private int v;//乘客
    private Bitree l;
    private Bitree r;

    public Bitree(int x){
        v=x;
    }
    public void add(Bitree the){
        if(the.v<v){
            if(l==null){
                l=the;
            }else{
                l.add(the);
            }
        }else{
            if(r==null){
                r=the;
            }else{
                r.add(the);
            }
        }
    }
    public void before_trav(){
        System.out.println(v);
        if(l!=null){
            l.before_trav();
        }
        if(r!=null){
            r.before_trav();
        }
    }
    //中序遍历
    public void mid_trav(){
        if(l!=null){
            l.mid_trav();
        }
        System.out.println(v);
        if(r!=null){
            r.mid_trav();
        }
    }
    //后序遍历
    public void after_trav(){
        if(l!=null){
            l.after_trav();
        }
        if(r!=null){
            r.after_trav();
        }
        System.out.println(v);
    }
}

只不过二叉树有畸形的可能，这时候我们需要平衡二叉树
代码如下：

class Bitree{
    private int v;//乘客
    private Bitree l;
    private Bitree r;
    private int balance=0; //平衡因子
    public Bitree(int x){
        v=x;
    }
    //添加节点
    public void add(Bitree the){
        Bitree root=this;
        if(the.v<v){
            if(l==null){
                l=the;
            }else{
                l.add(the);
            }
        }else{
            if(r==null){
                r=the;
            }else{
                r.add(the);
            }
        }
        //平衡二叉树
        calu_balance();
        if(balance>1){
            if(l.getBalance()>0)
                root=adjustLL();
            else
                root=adjustLR();
        }
        if(balance>-1){
            if(l.getBalance()<0)
                root=adjustRR();
            else
                root=adjustRL();
        }
    }
    public int getBalance(){
        return balance;
    }
    //LL调整
    private Bitree adjustLL(){
        Bitree root=l;   //this指的是源根节点
        l=root.r;
        root.r=this;
        return root;
    }
    //RR调整
    private Bitree adjustRR(){
        Bitree root=r;
        r=root.l;
        root.l=this;
        return root;
    }
    //LR调整
    private Bitree adjustLR(){
        l=l.adjustRR();
        return adjustLL();
    }
    //RL调整
    private Bitree adjustRL(){
        r=r.adjustLL();
        return adjustRR();
    }
    //获取二叉树高度
    public int getHeight(){
        int h=1;
        int h1=(l==null?0:l.getHeight());
        int h2=(r==null?0:r.getHeight());
        return h+Math.max(h1,h2);
    }
    //获取二叉树宽度
    public int getWidth(){
        int w=(""+v).length();
        if(l!=null)
            w+=l.getWidth();
        if(r!=null)
            w+=r.getWidth();
        return w;
    }
    public void calu_balance(){
        int lh=(l==null?0:l.getHeight());
        int rh=(r==null?0:r.getHeight());
        balance=lh-rh;
    }
    //前序遍历
    public void before_trav(){
        System.out.println(v);
        if(l!=null){
            l.before_trav();
        }
        if(r!=null){
            r.before_trav();
        }
    }
    //中序遍历
    public void mid_trav(){
        if(l!=null){
            l.mid_trav();
        }
        System.out.println(v);
        if(r!=null){
            r.mid_trav();
        }
    }
    //后序遍历
    public void after_trav(){
        if(l!=null){
            l.after_trav();
        }
        if(r!=null){
            r.after_trav();
        }
        System.out.println(v);
    }
}