参考代码#includestdio.h#includemalloc.h#includestdlib.h#includestdbool.h#defineEQ(a,b)((a)(b))#defineLT(a,b)((a)(b))#defineGT(a,b)((a)(b))#defineLH1//左高#defineEH0//等高#defineRH-1//右高typedefstructBiTNode{intdata;intbf;//节点平衡因子structBiTNode*leftChild;structBiTNode*rightChild;}BiTNode,BiTree;//右旋操作voidR_Rotate(BiTree**p){BiTNode*temp(*p)-leftChild;//temp指向p的左子树根节点(*p)-leftChildtemp-rightChild;//temp的右子树挂接为p的左子树temp-rightChild(*p);//p挂接为temp的右子树*ptemp;//p指向新的的根节点}//左旋操作voidL_Rotate(BiTree**p){BiTNode*temp(*p)-rightChild;(*p)-rightChildtemp-leftChild;temp-leftChild(*p);*ptemp;}/* 对以指针t所指结点为根的二叉树作左平衡旋转处理 包含LL旋转和LR旋转两种情况 平衡因子的改变其实很简单自己画图就出来了 */voidLeftBalance(BiTree**T){BiTNode*lcNULL;BiTNode*rdNULL;lc(*T)-leftChild;switch(lc-bf){caseLH://LL旋转(*T)-bfEH;lc-bfEH;R_Rotate(T);break;caseEH://deleteAVL需要insertAVL用不着(*T)-bfLH;lc-bfRH;R_Rotate(T);break;caseRH://LR旋转rdlc-rightChild;switch(rd-bf){caseLH:(*T)-bfRH;lc-bfEH;break;caseEH:(*T)-bfEH;lc-bfEH;break;caseRH:(*T)-bfEH;lc-bfLH;break;}rd-bfEH;L_Rotate((*T)-leftChild);R_Rotate(T);break;}}/* 对以指针t所指结点为根的二叉树作右平衡旋转处理 包含RR旋转和RL旋转两种情况 */voidRightBalance(BiTree**T){BiTNode*rcNULL;BiTNode*ldNULL;rc(*T)-rightChild;switch(rc-bf){caseLH://RL旋转ldrc-leftChild;switch(ld-bf){caseLH:(*T)-bfEH;rc-bfRH;break;caseEH:(*T)-bfEH;rc-bfEH;break;caseRH:(*T)-bfLH;rc-bfEH;break;}ld-bfEH;R_Rotate((*T)-rightChild);L_Rotate(T);break;caseEH://deleteAVL需要insertAVL用不着(*T)-bfRH;rc-bfLH;L_Rotate(T);break;caseRH://RR旋转(*T)-bfEH;rc-bfEH;L_Rotate(T);break;}}/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点则插入一个 数据元素为e的新结点并返回true否则返回false。若因插入而使二叉排序树 失去平衡则作平衡旋转处理布尔变量taller反映T长高与否 */boolInsertAVL(BiTree**T,inte,bool*taller){if(!(*T)){//插入新结点树“长高”置taller为trueprintf(e%d\n,e);(*T)(BiTree*)malloc(sizeof(BiTNode));(*T)-datae;(*T)-leftChild(*T)-rightChildNULL;(*T)-bfEH;*tallertrue;}else{if(EQ(e,(*T)-data))//树中已存在和有相同关键字的结点{*tallerfalse;printf(已存在相同关键字的结点\n);returnfalse;}//则不再插入if(LT(e,(*T)-data))//应继续在*T的左子树中进行搜索{if(!InsertAVL((*T)-leftChild,e,taller))returnfalse;//未插入if(*taller){//已插入到*T的左子树中且左子树“长高”switch((*T)-bf)//检查*T的平衡度{caseLH://原本左子树比右子树高需要作左平衡处理LeftBalance(T);*tallerfalse;break;caseEH://原本左子树、右子等高现因左子树增高而使树增高(*T)-bfLH;*tallertrue;break;caseRH://原本右子树比左子树高现左、右子树等高(*T)-bfEH;*tallerfalse;break;}}}else//应继续在*T的右子树中进行搜索{if(!InsertAVL((*T)-rightChild,e,taller))returnfalse;//未插入if(*taller){//已插入到*T的右子树中且右子树“长高”switch((*T)-bf)//检查*T的平衡度{caseLH://原本左子树比右子树高现左、右子树等高(*T)-bfEH;*tallerfalse;break;caseEH://原本左子树、右子等高现因右子树增高而使树增高(*T)-bfRH;*tallertrue;break;caseRH://原本右子树比左子树高需要作右平衡处理RightBalance(T);*tallerfalse;break;}}}}returntrue;}/* 若在平衡的二叉排序树T中存在和e有相同关键字的结点则删除之 并返回true否则返回false。若因删除而使二叉排序树 失去平衡则作平衡旋转处理布尔变量shorter反映T变矮与否 */booldeleteAVL(BiTree**T,intkey,bool*shorter){if((*T)NULL)//不存在该元素{returnfalse;//删除失败}elseif(EQ(key,(*T)-data))//找到元素结点{BiTNode*qNULL;if((*T)-leftChildNULL)//左子树为空{q(*T);(*T)(*T)-rightChild;free(q);qNULL;*shortertrue;}elseif((*T)-rightChildNULL)//右子树为空{q(*T);(*T)(*T)-leftChild;free(q);qNULL;*shortertrue;}else//左右子树都存在,{q(*T)-leftChild;while(q-rightChild){qq-rightChild;}(*T)-dataq-data;//这部分应该是把q的数据复制给(*T)deleteAVL((*T)-leftChild,q-data,shorter);//在左子树中递归删除前驱结点}}elseif(LT(key,(*T)-data))//左子树中继续查找{if(!deleteAVL((*T)-leftChild,key,shorter)){returnfalse;}if(*shorter){switch((*T)-bf){caseLH:(*T)-bfEH;*shortertrue;break;caseEH:(*T)-bfRH;*shorterfalse;break;caseRH:if((*T)-rightChild-bfEH)//注意这里画图思考一下*shorterfalse;else*shortertrue;RightBalance(T);//右平衡处理break;}}}else//右子树中继续查找{if(!deleteAVL((*T)-rightChild,key,shorter)){returnfalse;}if(*shorter){switch((*T)-bf){caseLH:if((*T)-leftChild-bfEH)//注意这里画图思考一下*shorterfalse;else*shortertrue;LeftBalance(T);//左平衡处理break;caseEH:(*T)-bfLH;*shorterfalse;break;caseRH:(*T)-bfEH;*shortertrue;break;}}}returntrue;}/* *Description: 销毁平衡二叉树 */voiddestroyAVL(BiTree**T){if((*T)){destroyAVL((*T)-leftChild);destroyAVL((*T)-rightChild);free((*T));(*T)NULL;}}/* Description: 在根指针t所指平衡二叉树中递归地查找某关键字等于key的数据元素 若查找成功则返回指向该数据元素结点的指针,否则返回空指针。 根据需要也可以返回一个bool值 */BiTNode*searchAVL(BiTree**T,intkey){if(((*T)NULL)||EQ(key,(*T)-data))return(*T);elseifLT(key,(*T)-data)/* 在左子树中继续查找 */returnsearchAVL((*T)-leftChild,key);elsereturnsearchAVL((*T)-rightChild,key);/* 在右子树中继续查找 */}//按树状打印输出二叉树的元素,m表示结点所在层次voidPrintBST(BiTree**T,intm){if((*T)-rightChild)PrintBST((*T)-rightChild,m1);for(inti1;im;i){printf(\t);//打印 i 个空格以表示出层次}printf(%d\n,(*T)-data);//打印 T 元素,换行if((*T)-leftChild)PrintBST((*T)-leftChild,m1);}intmain(intargc,char*argv[]){BiTree*TNULL;bool taller;inti0;intxx_t[]{1,2,3,5,7,8,10,13,15,17,20,23,30,31,50,60,0,55};for(i0;isizeof(xx_t)/sizeof(int);i){InsertAVL(T,xx_t[i],taller);}PrintBST(T,0);destroyAVL(T);return0;}运行结果参考文章平衡二叉树(AVL)的插入和删除