（封面XXXXXXX學(xué)院二叉平衡序樹(shù)課程設(shè)題

目：院（系：專(zhuān)業(yè)班：學(xué)生姓：指導(dǎo)老：時(shí)

間：

年

月

日

1需求分析從一棵空樹(shù)開(kāi)始創(chuàng)建創(chuàng)建過(guò)程中證樹(shù)的有序性時(shí)還要針對(duì)樹(shù)的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹(shù)轉(zhuǎn)換為二叉平衡排序樹(shù)?；疽螅?.創(chuàng)建（插入、調(diào)整、改組）輸出據(jù)結(jié)構(gòu)每個(gè)二叉樹(shù)結(jié)點(diǎn)包含有數(shù)值、平衡因子、指向左孩子和右孩子的指針。結(jié)點(diǎn)：數(shù)值

平衡因子

指向左孩

指向右孩databf

子的指針

子的指針

結(jié)點(diǎn)中標(biāo)注的是平衡因子1

數(shù)值data

平衡因子bf

指向左孩子的指針

指向右孩子的指針左孩子：數(shù)值data

平衡因子bf

指向左孩子的指針

指向右孩子的指針數(shù)值

平衡因子

指向左孩

指向右孩databf

子的指針

子的指針設(shè)計(jì)在一棵二叉樹(shù)上插入一個(gè)結(jié)點(diǎn)時(shí)，可能造成叉樹(shù)失去平衡，這時(shí)就要對(duì)失去平衡的二叉樹(shù)進(jìn)行平衡處理針對(duì)四種況有相應(yīng)的四種調(diào)整方法使插入后的二叉樹(shù)仍然平衡。假設(shè)由于在二叉樹(shù)上插入結(jié)點(diǎn)而失去平衡的最小子樹(shù)根結(jié)點(diǎn)的指針為（即A是插入點(diǎn)最近，且平衡因子絕對(duì)值超過(guò)的祖結(jié)點(diǎn)衡理的方法有下列4種，對(duì)應(yīng)地也就有四種算法：1、LL型調(diào)整：即左旋轉(zhuǎn)操作。于在A的左樹(shù)根結(jié)點(diǎn)的左子樹(shù)上插入結(jié)點(diǎn)A的衡因子由增至2，致使以A為的樹(shù)失去平衡，則需進(jìn)行一次向右順時(shí)針旋轉(zhuǎn)操作。插入過(guò)程中通過(guò)調(diào)用L_rotate函即完成調(diào)整工作。2、RR型調(diào)整：由于在A的子根結(jié)點(diǎn)的右子樹(shù)上插入結(jié)點(diǎn)A的衡因子由-1減-2，致使以A為的子樹(shù)失去平衡需行一次向左逆時(shí)針旋轉(zhuǎn)操作函即可完成此類(lèi)型的調(diào)整操作。插入過(guò)程中如果屬于此種類(lèi)型的調(diào)整，在執(zhí)insertAVL函時(shí)會(huì)調(diào)用此函數(shù)。3、LR型整：由于在A的子根結(jié)點(diǎn)的右子樹(shù)上插入結(jié)點(diǎn)A的平衡因子由1增至2，致使以A為結(jié)點(diǎn)的子樹(shù)失去平衡需行兩次旋先左旋后右旋作Lbalance函數(shù)可完成此操作，修改二叉樹(shù)根結(jié)點(diǎn)及其右孩子的平衡因子，對(duì)二叉樹(shù)根結(jié)點(diǎn)的左子樹(shù)做左旋平衡處理L_rotate函二叉樹(shù)根結(jié)點(diǎn)做右旋處用R_rotate函數(shù)4、RL型調(diào)整：由于在A的子根結(jié)點(diǎn)的左子樹(shù)上插入結(jié)點(diǎn)A的衡因子由-1減-2，致使以A為結(jié)點(diǎn)的子樹(shù)失去平衡需行兩次旋先右旋后左旋作Rbalance2

函數(shù)可完成此種類(lèi)型的操作。修改二叉樹(shù)根結(jié)點(diǎn)及其右孩子的平衡因子，對(duì)二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)做右旋平衡處理，再對(duì)二叉樹(shù)根結(jié)點(diǎn)做左旋平衡處理。如下圖所示：插入過(guò)程中判斷是屬于那種類(lèi)型的調(diào)整。所以insertAVL函數(shù)中需給出判定條件。3

碼#include<stdio.h>#include<stdlib.h>#defineLH+1//左邊高#defineEH0//一樣高#defineRH-1//右邊高typedefstructBSTNode{intdata;intbf;節(jié)點(diǎn)的平衡因子structBSTNode*lchild,*rchild;左右孩子指針}BSTNode,*BSTree;平衡二叉排序樹(shù)結(jié)構(gòu)的定義//以下為使二叉樹(shù)平衡平衡函數(shù)voidR_Rotate(BSTree&p){//對(duì)以p為的二叉排序樹(shù)做右旋處理，處理之后p指向的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)//處理之前的左子樹(shù)的根節(jié)點(diǎn)BSTreelc;lc=p->lchild;//lc指向*p的左子樹(shù)的根節(jié)點(diǎn)p->lchild=lc->rchild;的右子樹(shù)掛接*p的左樹(shù)lc->rchild=p;p=lc;//p指向新的根節(jié)點(diǎn)}voidL_Rotate(BSTree&p){//對(duì)以p為的二叉排序樹(shù)做左旋處理，處理之后p指向的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)//處理之前的右子樹(shù)的根節(jié)點(diǎn)BSTreerc;rc=p->rchild;//rc指向*p的右子樹(shù)的根節(jié)點(diǎn)4

p->rchild=rc->lchild;的左子樹(shù)掛接*p的右樹(shù)rc->lchild=p;p=rc;//p指向新的根節(jié)點(diǎn)}voidLeftBalance(BSTree&T){//對(duì)已T為的二叉排序樹(shù)做左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針指向//新的根節(jié)點(diǎn)BSTreelc,rd;lc=T->lchild;//lc指*T的左樹(shù)樹(shù)根節(jié)點(diǎn)switch(lc->bf)//查T(mén)的左樹(shù)的平衡度，并左相應(yīng)的平衡處理{caseLH:T->bf=lc->bf=EH;新節(jié)點(diǎn)插入*的左子的左子樹(shù)上，要作右旋處理R_Rotate(T);break;caseRH:新節(jié)點(diǎn)插入*T的左孩子的右子樹(shù)上，要作雙旋處理rd=lc->rchild;//rd向T的左子的右子樹(shù)樹(shù)根switch(rd->bf)修改T及其孩子的平衡因子{caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=RH;break;}rd->bf=EH;L_Rotate(T->lchild);對(duì)*T的左樹(shù)作左旋平衡處理R_Rotate(T);對(duì)T作旋平衡處理}5

}voidRightBalance(BSTree&T){//對(duì)已T為的二叉排序樹(shù)做右平衡旋轉(zhuǎn)處理BSTreelc,rd;lc=T->rchild;//lc指向T的子樹(shù)樹(shù)根節(jié)點(diǎn)switch(lc->bf)檢*T的右樹(shù)的平衡度，并左相應(yīng)的平衡處理{caseRH:T->bf=lc->bf=EH;新節(jié)點(diǎn)插入*T的左子的右子樹(shù)上，要作左旋處理L_Rotate(T);break;caseLH:新節(jié)點(diǎn)插入*T的左子的右子樹(shù)上，要作雙旋處理rd=lc->lchild;指向的右子的左子樹(shù)樹(shù)根switch(rd->bf)修*及其孩子的平衡因子{caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);//對(duì)*T的右子樹(shù)作左旋平衡處理L_Rotate(T);對(duì)T作左旋平衡處理}}//以下為插入函數(shù)intInsertAVL(BSTree&T,intkey,bool&taller){6

//若在平衡二叉排序樹(shù)中不存在與關(guān)鍵字key相等的結(jié)點(diǎn)，則將關(guān)鍵字插入樹(shù)中//布爾變量taller表示樹(shù)是否"高"if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;葉子結(jié)點(diǎn)其平衡因子肯定為T(mén)->lchild=T->rchild=NULL;taller=1;樹(shù)高了}else{if(key==T->data){//如果樹(shù)中已存放此關(guān)鍵字則不插入taller=0;return0;}if(key<T->data){//關(guān)鍵字小于根結(jié)點(diǎn)則插入其左樹(shù)中if(!InsertAVL(T->lchild,key,taller))return0;if(taller){如樹(shù)長(zhǎng)高了，判斷是否平衡switch(T->bf){caseLH:LeftBalance(T);不平衡時(shí)調(diào)用左平衡函數(shù)，使左子樹(shù)平衡taller=0;break;caseEH:T->bf=LH;taller=1;7

break;caseRH:T->bf=EH;taller=0;break;}}}else{//插入右子樹(shù)中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH:T->bf=EH;taller=0;break;caseEH:T->bf=RH;taller=1;break;caseRH:RightBalance(T);taller=0;break;}}}}return1;}voidVistTree(BSTree&T){//遍歷函數(shù)中打印輸出結(jié)點(diǎn)的函數(shù)8

if(T!=NULL)printf("%d",T->data);}voidPreOrderTraverse(BSTree&T){//遞歸實(shí)現(xiàn)先序遍歷if(T!=NULL)VistTree(T);if(T->lchild)PreOrderTraverse(T->lchild);if(T->rchild)PreOrderTraverse(T->rchild);}voidInOrderTraverse(BSTree&T){////遞歸實(shí)現(xiàn)中序遍歷if(T!=NULL){InOrderTraverse(T->lchild);中序遍歷左子*/VistTree(T);訪(fǎng)結(jié)*InOrderTraverse(T->rchild);中序遍歷右子*/}}voidPostorder(BSTree&T)/*LRN序遍歷/{if(T!=NULL){Postorder(T->lchild);后序遍歷左子*/Postorder(T->rchild);后序遍歷右子*/9

VistTree(T);訪(fǎng)結(jié)*}}//以下為主函數(shù)intmain(){BSTreeT;booltaller=0;inti,x;T=NULL;printf("-------------二平排序樹(shù)的創(chuàng)------------\n");請(qǐng)入10個(gè)異數(shù)建立二叉排序樹(shù)，在建立排序樹(shù)的過(guò)程中，二叉樹(shù)將自動(dòng)得到平\n");for(x=1;x<11;x++){scanf("%d",&i);if(InsertAVL(T,i,taller))輸數(shù)據(jù)成功！\n");else輸數(shù)據(jù)失??！\n");}printf("\n先序遍歷序列如下\n");PreOrderTraverse(T);printf("\n中序遍歷序列如下\n");InOrderTraverse(T);printf("\n后序遍歷序列如下\n");Postorder(T);10

printf("\n根結(jié)點(diǎn)平衡因子為%d",T->bf);printf("\n");system("pause");}5測(cè)試數(shù)據(jù)和測(cè)試結(jié)果6心得體會(huì)本次我們的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)設(shè)計(jì)題目是二叉平衡樹(shù)的排序樹(shù)的構(gòu)建動(dòng)查找表的知識(shí)。題目本身有一定難度，因此我們前期做了大量的準(zhǔn)備工作。首先我根據(jù)課上老師教的內(nèi)對(duì)于構(gòu)建平衡樹(shù)時(shí)的四種旋轉(zhuǎn)情況進(jìn)