今天要练习的算法是通过中缀表达式生成表达式树。中缀、前缀、后缀表达式的概念就不赘述了，学习链接：中缀、前缀、后缀表达式。
参考代码学习链接：表达式树—中缀表达式转换成后缀表达式（一）。
- 【迭代 ①】：识别单个运算符，进行分割，通过递归的思想构建表达式树。
举例：输入“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]+"\n";
}
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变形前\n"+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("变形后\n"+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变形前\n"+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("变形后\n"+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(){}
}程序运行结果：