平衡二叉樹操作的演示

#include<stdio.h>#include<malloc.h>typedefintKeyType;//定義關(guān)鍵字類型typedefstructnode//記錄類型{KeyTypekey;//關(guān)鍵字項(xiàng)intbf;//平衡因子structnode*lchild,*rchild;//左右孩子指針}BSTNode;voidLeftProcess(BSTNode*&p,int&taller){//對以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，//指針p指向新的根結(jié)點(diǎn)BSTNode*p1,*p2;if(p->bf==0)//原本左右子樹等高，現(xiàn)因左子樹增高而使樹增高{p->bf=1;taller=1;}elseif(p->bf==-1)//原本右子樹比左子樹高，現(xiàn)左右子樹等高{p->bf=0;taller=0;}else//原本左子樹比右子樹高，須作左子樹的平衡處理{p1=p->lchild;//p指向*p的左子樹根節(jié)點(diǎn)if(p1->bf==1)//新結(jié)點(diǎn)插入在*p的左孩子的左子樹上，要做LL調(diào)整{p->lchild=p1->rchild;p1->rchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==-1)//新結(jié)點(diǎn)插入在*p的左孩子的右子樹上，要做LR調(diào)整{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0)//新結(jié)點(diǎn)插入在*p2處作為葉子結(jié)點(diǎn)的情況 p->bf=p1->bf=0;elseif(p2->bf==1)//新結(jié)點(diǎn)插在*p2的左子樹上的情況{p1->bf=0;p->bf=-1;}else//新結(jié)點(diǎn)插在*p2的右子樹上的情況{p1->bf=1;p->bf=0;}p=p2;p->bf=0;//仍將p指向新的根結(jié)點(diǎn)，并置其bf值為0}taller=0;}}voidRightProcess(BSTNode*&p,int&taller){//對以指針p所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，//指針p指向新的根結(jié)點(diǎn)BSTNode*p1,*p2;if(p->bf==0)//原本左右子樹等高，現(xiàn)因右子樹增高而使樹增高{p->bf=-1;taller=1;}elseif(p->bf==1)//原本左子樹比右子樹高，現(xiàn)左右子樹等高{p->bf=0;taller=0;}else//原本右子樹比左子樹高，須作右子樹的平衡處理{p1=p->rchild;//p指向*p的右子樹根結(jié)點(diǎn)if(p1->bf==-1)//新結(jié)點(diǎn)插入在*p的右孩子的左子樹上，要做RR調(diào)整{p->rchild=p1->lchild;p1->lchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==1)//新結(jié)點(diǎn)插入在*p的右孩子的左子樹上，要做RL調(diào)整{p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0)//新結(jié)點(diǎn)插在*p2處作為葉子結(jié)點(diǎn)的情況 p->bf=p1->bf=0;elseif(p2->bf==-1)//新結(jié)點(diǎn)插在*p2的右子樹上的情況{p1->bf=0;p->bf=1;{p->lchild=p1->rchild;p1->rchild=p;p1->bf=p->bf=0;p=p1;taller=1;}else//須作LR調(diào)整{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0){p->bf=0;p1->bf=0;}elseif(p2->bf==1){p1->bf=-1;p->bf=0;}else{p1->bf=0;p->bf=1;}p2->bf=0;p=p2;taller=1;}}}voidDelete(BSTNode*q,BSTNode*&r,int&taller){//由DeleteAVL調(diào)用，用于處理被刪結(jié)點(diǎn)左右子樹均不空的情況if(r->rchild==NULL){q->key=r->key;q=r;r=r->lchild;free(q);taller=1;}else{Delete(q,r->rchild,taller);if(taller==1) RightProcess1(r,taller);}}intDeleteAVL(BSTNode*&p,KeyTypex,int&taller){//在AVL樹中刪除關(guān)鍵字為x的結(jié)點(diǎn)intk;BSTNode*q;if(p==NULL) return0;elseif(x<p->key){k=DeleteAVL(p->lchild,x,taller);if(taller==1) LeftProcess1(p,taller);returnk;}elseif(x>p->key){k=DeleteAVL(p->rchild,x,taller);if(taller==1) RightProcess1(p,taller);returnk;}else//找到了關(guān)鍵字為x的結(jié)點(diǎn)，由p指向它{q=p;if(p->rchild==NULL)//被刪結(jié)點(diǎn)右子樹為空{(diào)p=p->lchild;free(q);taller=1;}elseif(p->lchild==NULL)//被刪結(jié)點(diǎn)左子樹為空{(diào)p=p->rchild;free(q);taller=1;}else//被刪結(jié)點(diǎn)左右子樹均不為空{(diào)Delete(q,q->lchild,taller);if(taller==1) LeftProcess1(q,taller);p=q;}return1;}}voidmain(){BSTNode*b=NULL;inti,j,k;KeyTypea[]={4,9,0,1,8,6,3,5,2,7},n=10;printf("創(chuàng)建一棵AVL樹:\n");for(i=0;i<n;i++){printf("第%d步，插入%d元素:",i+1,a[i]);InsertAVL(b,a[i],j);DispBSTree(b);printf("\n");}printf("AVL:");DispBSTree(b);printf("\n");prin