普通的二叉樹可以通過下面代碼創(chuàng)造出來:

//遞歸定義法
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;
    }
    //添加節(jié)點(diǎn)
    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調(diào)整
    private Bitree adjustLL(){
        Bitree root=l;   //this指的是源根節(jié)點(diǎn)
        l=root.r;
        root.r=this;
        return root;
    }
    //RR調(diào)整
    private Bitree adjustRR(){
        Bitree root=r;
        r=root.l;
        root.l=this;
        return root;
    }
    //LR調(diào)整
    private Bitree adjustLR(){
        l=l.adjustRR();
        return adjustLL();
    }
    //RL調(diào)整
    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);
    }
}