通过不断迭代，编写<通过中缀表达式，构造表达式树>的代码

今天要练习的算法是通过中缀表达式生成表达式树。中缀、前缀、后缀表达式的概念就不赘述了，学习链接：中缀、前缀、后缀表达式。

参考代码学习链接：表达式树—中缀表达式转换成后缀表达式（一）。

---

 

• 【迭代 ①】：识别单个运算符，进行分割，通过递归的思想构建表达式树。

举例：输入“1+2”，输出。

Java code of phase[1]：

    void Express2BTree(String str){
        root=Express2BTreeProc(str);
    }
    private BTNode Express2BTreeProc(String str){
        BTNode parent=new BTNode();
        boolean isSet[]={false,false};    //【0】:left，【1】:right
        String tmp=new String();        //临时字符串
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch>=48 && ch<=57){            //是数字
                tmp+=ch;
            }
            else if(ch=='+' || ch=='-' || ch=='*' || ch=='/'){
                parent.data=String.valueOf(ch);
                if(! isSet[0]){            //左子树未构造
                    isSet[0]=true;
                    parent.lChild=Express2BTreeProc(tmp);
                    tmp=new String("");    //归零初始化
                }
            }
        }
        if(isSet[0] && (! isSet[1])){//右子树未构造
            isSet[1]=true;
            parent.rChild=Express2BTreeProc(tmp);
            tmp=new String("");    //归零初始化
        }
        if(! isSet[0]) parent.data=tmp;//如果函数处理的全是数字（叶子节点），那么就返回叶子节点
        return parent;
    }

逻辑盲区：

1、启动构造右子树的 if  语句不能嵌套在上方的 if 中，否则不能触发。

2、数字0~9的ascii码是[ 48 , 57 ]，故应写<=、>=。

---

• 【迭代 ②】：判断多个表达式。

举例：输入“1+2+3”，输出：

代码改进：在临时字符串递加段，加入【或】判断条件 isSet[0] ，如果左子树已构造，继续扫描、递加。

---

• 【迭代 ③】：识别优先级。*、/ 的优先级比+、- 的要高。

（在这里我修改了toString打印树函数，填充符由*变为space，避免混淆）

如果代码按原先的方式跑，结果是：

 

但是根据运算符优先级，应该是：

修改两处代码：

1.递归函数中引入 only_Have_Priority 变量：

        boolean only_Have_Priority=false;
        if(( str.indexOf("+")<0 && str.indexOf("-")<0 )  
                            &&
        ( str.indexOf("*")>=0 || str.indexOf("/")>=0 ))
            only_Have_Priority=true;
        //能够找到 * / 、不能找到 + -

2.触发对表达式进行分割的判断语句中引入一个【与】判断条件：

((!only_Have_Priority)&&(ch=='*' || ch=='/'))

完整代码：

Java code of phase[3]：

    void Express2BTree(String str){
        root=Express2BTreeProc(str);
    }
    private BTNode Express2BTreeProc(String str){
        BTNode parent=new BTNode();
        int i;
        boolean isSet[]={false,false};    //【0】:left，【1】:right
    //    boolean havaAddOrSub = ( str.indexOf("+")<0 || str.indexOf("-")<0 ) ? false : true;
        
        boolean only_Have_Priority=false;
        if(( str.indexOf("+")<0 && str.indexOf("-")<0 )  
                            &&
        ( str.indexOf("*")>=0 || str.indexOf("/")>=0 ))
            only_Have_Priority=true;
        //能够找到 * / 、不能找到 + -
        
        String tmp=new String();        //临时字符串
        
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);    //是数字、或者左树已构造  || (havaAddOrSub && (ch=='' || ch=='-') )   
            if( (ch>=48 && ch<=57 ) || isSet[0] || ((!only_Have_Priority)&&(ch=='*' || ch=='/'))   ){
                tmp+=ch;
            }
            else if(ch=='+' || ch=='-' || ch=='*' || ch=='/'){
                parent.data=String.valueOf(ch);
                if(! isSet[0]){            //左子树未构造
                    isSet[0]=true;
                    parent.lChild=Express2BTreeProc(tmp);
                    tmp=new String("");    //归零初始化
                }
            }
        }

逻辑盲点：

对 only_Have_Priority 进行赋值时，应该是【与】而不是或。想错了。

测试：

输入：1*2+3*4

输出：

输入：1*2+3*4+5*6

输出：

---

• 【迭代 ④】：小括号的优先级应最高

 运行中出现bug。经查是原来的 only_Have_Priority  判断语句的不足。修改之。

加入了堆栈思想的括号判断语句。

Java code of phase[4]：

    void Express2BTree(String str){
        root=Express2BTreeProc(str);
    }
    private BTNode Express2BTreeProc(String str){
        BTNode parent=new BTNode();
        int i;
        boolean isSet[]={false,false};    //【0】:left，【1】:right
    //    boolean havaAddOrSub = ( str.indexOf("+")<0 || str.indexOf("-")<0 ) ? false : true;
        
        boolean only_Have_Priority=false;
        int inBracket=0;        //判断当前字符是否在括号中    
                
        boolean havaMulti=false;
        boolean havaAdd=false;
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch=='(') inBracket++;
            else if(ch==')') inBracket--;
            else if(inBracket==0){            //在括号内
                if(ch=='*' || ch == '/') havaMulti=true;
                else if(ch=='-' || ch == '+') havaAdd=true;
            }
        }
        if((!havaAdd) && (havaMulti)) only_Have_Priority=true;
        //能够找到 * / 、不能找到 + -
        
        inBracket=0;
        
        String tmp=new String();        //临时字符串
        
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);    //是数字、或者左树已构造  
            if(ch=='('){
                if(inBracket>0) tmp+=ch;//括号内的括号
                inBracket++;
            }
            else if(ch==')'){
                inBracket--;
                if(inBracket>0) tmp+=ch;
            }
            else if( (ch>=48 && ch<=57 ) 
                    || isSet[0] 
                    || ((!only_Have_Priority)&&(ch=='*' || ch=='/')) //不存在（只有1*2），也就是1*2+3
                    || inBracket>0  ){
                tmp+=ch;
            }
            else if(ch=='+' || ch=='-' || ch=='*' || ch=='/'){
                parent.data=String.valueOf(ch);
                if(! isSet[0]){            //左子树未构造
                    isSet[0]=true;
                    parent.lChild=Express2BTreeProc(tmp);
                    tmp=new String("");    //归零初始化
                }
            }
        }
        
        if(isSet[0] && (! isSet[1])){//右子树未构造
            isSet[1]=true;
            parent.rChild=Express2BTreeProc(tmp);
            tmp=new String("");    //归零初始化
        }
        if(! isSet[0]) parent.data=tmp;//如果函数处理的全是数字（叶子节点），那么就返回叶子节点
        return parent;
    }

测试输入：((3*4)/(1+2))*((1+1)/(1-2))

测试输出：

测试输入：(1+2)*3

测试输出：

---

【在一次测试中发现异常】：

输入：(1+2)*3-2

输出：

然后改了一个小时bug。我的函数写的还是有问题，反正现在无论怎么输入，只要是一个正常的表达式，都没什么问题了。

修改BUG后代码：

    void Express2BTree(String str){
        root=Express2BTreeProc(str);
    }
    private BTNode Express2BTreeProc(String str){
        int i;
        //首尾括号剥夺
        if(str.length()>1 && str.charAt(0)=='(' && str.charAt(str.length()-1)==')'){
            String tmp=str.substring(1, str.length()-1);
            //是否存在括号内字符？
            boolean haveInnerChar=false;
            int inBracket=0;    
            for(i=0;i<str.length();i++){
                char ch=str.charAt(i);
                if(ch=='(') inBracket++;
                else if(ch==')') inBracket--;
                else if(inBracket==0){            //在括号内
                    haveInnerChar=true;
                }
            }
            if(!haveInnerChar) str=tmp;
        }
        BTNode parent=new BTNode();

        boolean isSet[]={false,false};    //【0】:left，【1】:right
    //    boolean havaAddOrSub = ( str.indexOf("+")<0 || str.indexOf("-")<0 ) ? false : true;
        
        boolean only_Have_Priority=false;
        int inBracket=0;        //判断当前字符是否在括号中    
        
/*        if(( str.indexOf("+")<0 && str.indexOf("-")<0 )  
                            &&
        ( str.indexOf("*")>=0 || str.indexOf("/")>=0 ))
            only_Have_Priority=true;*/
        boolean havaMulti=false;
        boolean havaAdd=false;
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch=='(') inBracket++;
            else if(ch==')') inBracket--;
            else if(inBracket==0){            //在括号内
                if(ch=='*' || ch == '/') havaMulti=true;
                else if(ch=='-' || ch == '+') havaAdd=true;
            }
        }
        if((!havaAdd) && (havaMulti)) only_Have_Priority=true;
        //能够找到 * / 、不能找到 + -
        
        inBracket=0;
        
        String tmp=new String();        //临时字符串
        
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);    //是数字、或者左树已构造  
            if(ch=='('){
                tmp+=ch;//括号内的括号
                inBracket++;
            }
            else if(ch==')'){
                inBracket--;
                tmp+=ch;
            }
            else if( (ch>=48 && ch<=57 ) 
                    || isSet[0] 
                    || ((!only_Have_Priority)&&(ch=='*' || ch=='/')) //不存在（只有1*2），也就是1*2+3
                    || inBracket>0  ){
                tmp+=ch;
            }
            else if(ch=='+' || ch=='-' || ch=='*' || ch=='/'){
                parent.data=String.valueOf(ch);
                if(! isSet[0]){            //左子树未构造
                    isSet[0]=true;
                    parent.lChild=Express2BTreeProc(tmp);
                    tmp=new String("");    //归零初始化
                }
            }
        }
        
        if(isSet[0] && (! isSet[1])){//右子树未构造
            isSet[1]=true;
            parent.rChild=Express2BTreeProc(tmp);
            tmp=new String("");    //归零初始化
        }
        if(! isSet[0]) parent.data=tmp;//如果函数处理的全是数字（叶子节点），那么就返回叶子节点
        return parent;
    }

完整代码：

import java.util.*;

public class demo {
    public static void main(String args[]){

/*        tree.Express2BTree("((3*4)/(1+2))*((1+1)/(1-2))");
        System.out.println(tree);*/
        BTtree tree=new BTtree();
        tree.splitCh=' ';
        Scanner scan;
        int flag=10;
        while(flag>0){
            flag--;
            scan=new Scanner(System.in);//generate input flu
            System.out.print("请输入中缀表达式: ");//input reminder
            String str=new String(scan.nextLine());//assignment
            tree.Express2BTree(str);
            System.out.println("前缀表达式: ");//input reminder
            tree.PreOrderTraversal();
            System.out.println("后缀表达式: ");//input reminder
            tree.PostOrderTraversal();
        }
        scan=new Scanner(System.in);
        scan.close();

    }
}

class BTtree{//二叉树类
    class BTNode{//节点类
        String data=new String("0");
        BTNode lChild=null;
        BTNode rChild=null;
        boolean LTag=false;//=0 : 指向左孩子。 =1 : 指向前驱
        boolean RTag=false;//=0 : 指向右孩子。 =1 : 指向后继
        int height=1;        //用于AVL树
        BTNode(){}
        BTNode(String data){this.data=data;}
        BTNode(int num){this.data=Integer.toString(num);};
    }
    void Express2BTree(String str){
        root=Express2BTreeProc(str);
    }
    private BTNode Express2BTreeProc(String str){
        int i;
        //首尾括号剥夺
        if(str.length()>1 && str.charAt(0)=='(' && str.charAt(str.length()-1)==')'){
            String tmp=str.substring(1, str.length()-1);
            //是否存在括号内字符？
            boolean haveInnerChar=false;
            int inBracket=0;    
            for(i=0;i<str.length();i++){
                char ch=str.charAt(i);
                if(ch=='(') inBracket++;
                else if(ch==')') inBracket--;
                else if(inBracket==0){            //在括号内
                    haveInnerChar=true;
                }
            }
            if(!haveInnerChar) str=tmp;
        }
        BTNode parent=new BTNode();

        boolean isSet[]={false,false};    //【0】:left，【1】:right
    //    boolean havaAddOrSub = ( str.indexOf("+")<0 || str.indexOf("-")<0 ) ? false : true;
        
        boolean only_Have_Priority=false;
        int inBracket=0;        //判断当前字符是否在括号中    
        
/*        if(( str.indexOf("+")<0 && str.indexOf("-")<0 )  
                            &&
        ( str.indexOf("*")>=0 || str.indexOf("/")>=0 ))
            only_Have_Priority=true;*/
        boolean havaMulti=false;
        boolean havaAdd=false;
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch=='(') inBracket++;
            else if(ch==')') inBracket--;
            else if(inBracket==0){            //在括号内
                if(ch=='*' || ch == '/') havaMulti=true;
                else if(ch=='-' || ch == '+') havaAdd=true;
            }
        }
        if((!havaAdd) && (havaMulti)) only_Have_Priority=true;
        //能够找到 * / 、不能找到 + -
        
        inBracket=0;
        
        String tmp=new String();        //临时字符串
        
        for(i=0;i<str.length();i++){
            char ch=str.charAt(i);    //是数字、或者左树已构造  
            if(ch=='('){
                tmp+=ch;//括号内的括号
                inBracket++;
            }
            else if(ch==')'){
                inBracket--;
                tmp+=ch;
            }
            else if( (ch>=48 && ch<=57 ) 
                    || isSet[0] 
                    || ((!only_Have_Priority)&&(ch=='*' || ch=='/')) //不存在（只有1*2），也就是1*2+3
                    || inBracket>0  ){
                tmp+=ch;
            }
            else if(ch=='+' || ch=='-' || ch=='*' || ch=='/'){
                parent.data=String.valueOf(ch);
                if(! isSet[0]){            //左子树未构造
                    isSet[0]=true;
                    parent.lChild=Express2BTreeProc(tmp);
                    tmp=new String("");    //归零初始化
                }
            }
        }
        
        if(isSet[0] && (! isSet[1])){//右子树未构造
            isSet[1]=true;
            parent.rChild=Express2BTreeProc(tmp);
            tmp=new String("");    //归零初始化
        }
        if(! isSet[0]) parent.data=tmp;//如果函数处理的全是数字（叶子节点），那么就返回叶子节点
        return parent;
    }
    
    protected BTNode root=new BTNode();
    BTtree(){
    }
    BTtree(int layer){
        //用队列的方式构造n层树
        List<BTNode> queue=new ArrayList<BTNode>();
        int front=0;
        int rear=0;//队尾插入
        queue.add(root);//初始化入队
        rear++;
        int i , k=0 , j;
        for(j=0;j<layer;j++){
            int nowRear=rear;
            for(i=front;i<nowRear;i++){
                //出队，生两个孩子
                BTNode parent=queue.get(front++);
                BTNode lChild=new BTNode();
                lChild.data=Integer.toString(++k);
                BTNode rChild=new BTNode();
                rChild.data=Integer.toString(++k);
                parent.lChild=lChild;
                parent.rChild=rChild;
                queue.add(lChild);
                rear++;
                queue.add(rChild);
                rear++;
            }
        }
    }
    BTtree(String express){//通过中缀表达式进行构造
        //1.对表达式进行括号补全。
        
        
    }
    public String toString(){//重写打印函数
        String padding=new String(" ");
        List<BTNode> queue=new ArrayList<BTNode>();
        List<String[]> PrintList=new ArrayList<String[]>();
        int front=0;
        int rear=0;//队尾插入
        queue.add(root);//初始化入队
        rear++;
        int i , k=0 , j;
        
        String emptySignal=new String("");//空信号
        
        String str[]=new String[1];
        str[0]=root.data;
        PrintList.add(str);//打印数据结构初始化
        int layer=1;//下一层字符串的数目是2^1=2。
        int pos=0;
        
        boolean flag=true;
        ok:
        while(flag){
            pos=0;//pos初始化
            String tmp[]=new String[(int)Math.pow((int)2, (int)(layer++))];//length=2^layer
            flag=false;        //循环标志初始化
            int nowRear=rear;
            int nowFront=front;
            for(i=front;i<nowRear;i++){
                String nowStr=new String();
                BTNode parent=queue.get(front++);
                if(parent==null) break ok;    //跳出两重循环
                if(parent.data.equals(emptySignal)){//如果是空的，派生出两个空孩子
                    for(int t=0;t<2;t++){
                        tmp[pos++]=padding;
                        BTNode empty=new BTNode();
                        empty.data=emptySignal;
                        queue.add(empty);rear++;
                    }
                }else{
                    if(parent.lChild!=null){
                        flag=true;                    //只要这一层存在孩子，就可以继续循环下去。
                        queue.add(parent.lChild);
                        tmp[pos++]=parent.lChild.data;
                        rear++;
                    }else{
                        tmp[pos++]=padding;
                        BTNode empty=new BTNode();
                        empty.data=emptySignal;
                        queue.add(empty);
                        rear++;
                    }
                    if(parent.rChild!=null){
                        flag=true;
                        queue.add(parent.rChild);
                        tmp[pos++]=parent.rChild.data;
                        rear++;
                    }else{
                        tmp[pos++]=padding;
                        BTNode empty=new BTNode();
                        empty.data=emptySignal;
                        queue.add(empty);
                        rear++;
                    }
                }
            }                // end of for
            PrintList.add(tmp);
        }                    // end of while
        /*
        for(i=0;i<PrintList.size();i++){
            for(j=0;j<PrintList.get(i).length;j++) System.out.print(PrintList.get(i)[j]+" ");
            System.out.println();
        }*/
        //后处理
        String[] PrintListLine=new String[PrintList.size()-1];
        for(i=PrintListLine.length-1;i>=0;i--){//循环构造
            //首先进行构造
            String tmp=new String();
            for(j=0;j<PrintList.get(i).length;j++){
                tmp+=PrintList.get(i)[j];
                if(j!=PrintList.get(i).length-1) tmp+=" ";
            }
            PrintListLine[i]=tmp;
        }
        for(i=PrintListLine.length-2;i>=0;i--){//居中操作
            int spaceNum=(PrintListLine[i+1].length()-PrintListLine[i].length())/2;
            String space=new String();
            for(int t=0;t<spaceNum;t++) space+=" ";
            PrintListLine[i]=space+PrintListLine[i]+space;
        }    
        String outStr=new String();
        for(i=0;i<PrintListLine.length;i++){//最后构造一个字符串
            outStr+=PrintListLine[i]+"
";
        }
        return outStr;
    }
    void PreOrderTraversal(){
        PreOrder(root);
        System.out.println();
    }
    char splitCh=',';
    private void PreOrder(BTNode obj){
        if(obj!=null){
            System.out.print(obj.data+splitCh);
            PreOrder(obj.lChild);
            PreOrder(obj.rChild);
        }
    }
    void InOrderTraversal(){
        InOrder(root);
        System.out.println();
    }
    private void InOrder(BTNode obj){    
        if(obj!=null){
            InOrder(obj.lChild);
            System.out.print(obj.data+splitCh);
            InOrder(obj.rChild);
        }
    }
    void PostOrderTraversal(){
        PostOrder(root);
        System.out.println();
    }
    private void PostOrder(BTNode obj){    
        if(obj!=null){
            
            InOrder(obj.lChild);
            InOrder(obj.rChild);
            System.out.print(obj.data+splitCh);
        }
    }
}



//线索二叉树
class BThrTree extends BTtree{
    BThrTree(BTtree obj){//由父类构造而来
        //首先拷贝根节点
        BTNode tmp=new BTNode();
        tmp.data=obj.root.data;
        copy(root,obj.root);
    }
    void copy(BTNode node1,BTNode node2){
        if(node2.lChild!=null){//左树递归
            BTNode l=new BTNode();
            l.data=node2.lChild.data;//拷贝左树    
            node1.lChild=l;//左树赋值            
            copy(node1.lChild,node2.lChild);
        }
        if(node2.rChild!=null){//右树递归
            BTNode r=new BTNode();
            r.data=node2.rChild.data;//拷贝右树
            node1.rChild=r;//右树赋值
            copy(node1.rChild,node2.rChild);
        }    
    }
    public void InThreadingFabric(){//中序线索化构造
        BTNode now=root;
        InThreading(now); 
        pre.RTag=true;//【最后一个后继为null】
        pre.rChild=null;
    }
    private BTNode pre=null;//前驱指针
    private void InThreading(BTNode node){//中序线索化递归
        if(node!=null){//保证节点非空
            InThreading(node.lChild);//左子树线索化
            if(node.lChild==null){//如果左子树不存在
                node.LTag=true;//线索化
                node.lChild=pre;//前驱    【第一个前驱为null】
            }
            if(pre!=null && pre.rChild==null){//后继
                pre.RTag=true;
                pre.rChild=node;
            }
            pre=node;//保持pre指向node的前驱。
            InThreading(node.rChild);//左子树线索化
        }
    }
    void InOrderTraversal_Thr(){//线索化遍历
        BTNode now=root;
        //遍历前驱
        while(now.lChild!=null){//要么有左子树。
            now=now.lChild;
        }
        while(now!=null){//要么有左子树。
            System.out.print(now.data+",");
            if(now.RTag){now=now.rChild;}//如果是后继，就继续后继。
            else{
                now=now.rChild;//如果不是，则令右子树的最左节点为后继
                while(!now.LTag) now=now.lChild;
            }
        }
        System.out.println();
    }
}


class SearchBST extends BTtree{//二叉查找树
    SearchBST(int[] nums){//由二维数组构造
        root.data=String.valueOf(nums[0]);//构造根节点
        for(int i=1;i<nums.length;i++){//对其他元素进行构造
            BTNode node=new BTNode();
            node.data=String.valueOf(nums[i]);//构造叶子节点
            BTNode parent=root;
            int nodeV=nums[i];
            while(parent!=null){
                int parentV=Integer.valueOf(parent.data).intValue();//当前根节点的值
                if(nodeV<parentV){//左叶子
                    if(parent.lChild==null){//当前根节点的左叶子非空
                        parent.lChild=node;//挂入节点
                        break;                //如果这里没有加【break】，就会死循环。待解决☆☆☆
                    }
                    parent=parent.lChild;//如果这里空了，跳出循环
                }else{
                    if(parent.rChild==null){
                        parent.rChild=node;//挂入节点
                        break;                //☆☆☆
                    }
                    parent=parent.rChild;//如果这里空了，跳出循环                    
                }
            }
        }
    }
    SearchBST(){}
}

class AVLTree extends BTtree{    //平衡二叉树
    AVLTree(int[] nums){//由二维数组构造
        root.data=String.valueOf(nums[0]);
        for(int i=1;i<nums.length;i++) AVLinsert(root,null,true,String.valueOf(nums[i]));
    }
    BTNode LLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
        /*
         * 根节点的左孩子  为新的根节点。
         * 老根节点成为新根节点的右孩子
         * 根节点的左孩子  的右子树作为 老根节点的左子树
        */ 
        BTNode pre=node;
        node=node.lChild;//根节点的左孩子  为新的根节点。
        //从此之后node就是【根节点的左孩子】
        pre.lChild=node.rChild;//根节点的左孩子(node)  的右子树作为 老根节点(pre)的左子树
        node.rChild=pre;
        //pre: 老根节点
        pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
        node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
        return node;//返回根节点
    }
    
    BTNode RRRotate(BTNode node){//左子树.高度-右子树.高度==-2 【向左旋转】
        /*
         * 根节点的左孩子  为新的根节点。
         * 老根节点成为新根节点的右孩子
         * 根节点的左孩子  的右子树作为 老根节点的左子树
         */    
        BTNode pre=node;
        node=node.rChild;//根节点的右孩子  为新的根节点。
        //从此之后node就是【根节点的左孩子】
        pre.rChild=node.lChild;//根节点的左孩子(node)  的右子树作为 老根节点(pre)的左子树
        node.lChild=pre;
        //pre: 老根节点
        pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
        node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
        return node;
    }
    
    BTNode LRRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
        node.lChild=RRRotate(node.lChild);
        node=LLRotate(node);
        return node;
    }
    
    BTNode RLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
        node.rChild=LLRotate(node.rChild);
        node=RRRotate(node);
        return node;
    }
    //                  当前节点           父节点               
    void AVLinsert(BTNode node,BTNode parent,boolean isLeft,String data){
        int dataV=Integer.valueOf(data).intValue();
        int nodeV=0;
        if(node!=null) nodeV=Integer.valueOf(node.data).intValue();
        if(node==null){
            BTNode newNode=new BTNode();
            newNode.data=data;
            if(isLeft) parent.lChild=newNode;
            else        parent.rChild=newNode;
        }
        
        else if(dataV<nodeV){//向左插入
            AVLinsert(node.lChild,node,true,data);
            node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
            
            System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
            System.out.println("node="+node.data);
            
            if(getHeight(node.lChild)-getHeight(node.rChild)==2){
                System.out.println("L变形前
"+this);
                if(getHeight(node.lChild.lChild)>getHeight(node.lChild.rChild)){
                    System.out.println("LL");
                    boolean flag=false;
                    if(root.data.equals(node.data)) flag=true;
                    if(!flag){
                        if(isLeft) parent.lChild=LLRotate(node);
                        else parent.rChild=LLRotate(node);
                    }else node=LLRotate(node);
                    if(flag) root=node;
                }else{
                    System.out.println("LR");
                    boolean flag=false;
                    if(root.data.equals(node.data)) flag=true;
                    if(!flag){
                        if(isLeft) parent.lChild=LRRotate(node);
                        else parent.rChild=LRRotate(node);
                    }else node=LRRotate(node);
                    if(flag) root=node;
                }
                System.out.println("变形后
"+this);
            }
            System.out.println(this);
            
        }else{
            AVLinsert(node.rChild,node,false,data);
            node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
            
            System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
            System.out.println("node="+node.data);
            
            if(getHeight(node.lChild)-getHeight(node.rChild)==-2){
                System.out.println("R变形前
"+this);
                if(getHeight(node.rChild.lChild)>getHeight(node.rChild.rChild)){
                    System.out.println("RL");
                    boolean flag=false;
                    if(root.data.equals(node.data)) flag=true;
                    if(!flag){
                        if(isLeft) parent.lChild=RLRotate(node);
                        else parent.rChild=RLRotate(node);
                    }else node=RLRotate(node);
                    if(flag) root=node;
                }else{
                    System.out.println("RR");
                    boolean flag=false;
                    if(root.data.equals(node.data)) flag=true;
                    if(!flag){
                        if(isLeft) parent.lChild=RRRotate(node);
                        else parent.rChild=RRRotate(node);
                    }else node=RRRotate(node);
                    if(flag) root=node;
                }
                System.out.println("变形后
"+this);
            }
            System.out.println(this);
        }
    }
    
    int getHeight(BTNode node){
        if(node!=null){
            return node.height;
        }else{
            return 0;
        }
    }
    void test(){
        root=new BTNode(0);
        BTNode node[]=new BTNode[3];
        for(int i=0;i<3;i++) node[i]=new BTNode(i+1);
        root.lChild=node[0];
        root.lChild.rChild=node[1];
        root.lChild.lChild=node[2];
        System.out.println(this);
        root=LRRotate(root);
        System.out.println(this);
        System.out.println(root.height);
        System.out.println(root.lChild.height);
        System.out.println(root.rChild.height);
    }
    AVLTree(){}
}

程序运行结果：