资源描述：
《平衡二叉树的插入与生成》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、#include#includetypedefintKeyType;/*定义关键字类型*/typedefcharInfoType;typedefstructnode/*记录类型*/{KeyTypekey;/*关键字项*/intbf;/*平衡因子*/InfoTypedata;/*其他数据域*/structnode*lchild,*rchild;/*左右孩子指针*/}BSTNode;voidLeftProcess(BSTNode**p,int*taller)/*对以
2、指针p所指结点为根的二叉树作左平衡旋转处理,本算法结束时,指针p指向新的根结点*/{BSTNode*p1,*p2;if((*p)->bf==0)/*原本左、右子树等高,现因左子树增高而使树增高*/{(*p)->bf=1;*taller=1;}elseif((*p)->bf==-1)/*原本右子树比左子树高,现左、右子树等高*/{(*p)->bf=0;*taller=0;}else/*原本左子树比右子树高,需作左子树的平衡处理*/{p1=(*p)->lchild;/*p指向*p的左子树根结点*/if(
3、p1->bf==1)/*新结点插入在*b的左孩子的左子树上,要作LL调整*/{(*p)->lchild=p1->rchild;p1->rchild=*p;(*p)->bf=p1->bf=0;*p=p1;}elseif(p1->bf==-1)/*新结点插入在*b的左孩子的右子树上,要作LR调整*/{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;(*p)->lchild=p2->rchild;p2->rchild=*p;if(p2->bf==0)/*
4、新结点插在*p2处作为叶子结点的情况*/(*p)->bf=p1->bf=0;elseif(p2->bf==1)/*新结点插在*p2的左子树上的情况*/{p1->bf=0;(*p)->bf=-1;}else/*新结点插在*p2的右子树上的情况*/{p1->bf=1;(*p)->bf=0;}*p=p2;(*p)->bf=0;/*仍将p指向新的根结点,并置其bf值为0*/}*taller=0;}}voidRightProcess(BSTNode**p,int*taller)/*对以指针p所指结点为根的二叉
5、树作右平衡旋转处理,本算法结束时,指针p指向新的根结点*/{BSTNode*p1,*p2;if((*p)->bf==0)/*原本左、右子树等高,现因右子树增高而使树增高*/{(*p)->bf=-1;*taller=1;}elseif((*p)->bf==1)/*原本左子树比右子树高,现左、右子树等高*/{(*p)->bf=0;*taller=0;}else/*原本右子树比左子树高,需作右子树的平衡处理*/{p1=(*p)->rchild;/*p指向*p的右子树根结点*/if(p1->bf==-1)/
6、*新结点插入在*b的右孩子的右子树上,要作RR调整*/{(*p)->rchild=p1->lchild;p1->lchild=*p;(*p)->bf=p1->bf=0;*p=p1;}elseif(p1->bf==1)/*新结点插入在*p的右孩子的左子树上,要作RL调整*/{p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;(*p)->rchild=p2->lchild;p2->lchild=*p;if(p2->bf==0)/*新结点插在*p2处作为叶
7、子结点的情况*/(*p)->bf=p1->bf=0;elseif(p2->bf==-1)/*新结点插在*p2的右子树上的情况*/{p1->bf=0;(*p)->bf=1;}else/*新结点插在*p2的左子树上的情况*/{p1->bf=-1;(*p)->bf=0;}*p=p2;(*p)->bf=0;/*仍将p指向新的根结点,并置其bf值为0*/}*taller=0;}}intInsertAVL(BSTNode**b,KeyTypee,int*taller)/*若在平衡的二叉排序树b中不存在和e有相同
8、关键字的结点,则插入一个数据元素为e的新结点,并返回1,否则返回0。若因插入而使二叉排序树失去平衡,则作平衡旋转处理,布尔变量taller反映b长高与否*/{if(*b==NULL)/*原为空树,插入新结点,树“长高”,置taller为1*/{*b=(BSTNode*)malloc(sizeof(BSTNode));(*b)->key=e;(*b)->lchild=(*b)->rchild=NULL;(*b)->bf=0;*taller=1;}else{if(e==(
