实验报告-平衡二叉树

实习报告

一、需求分析、问题描述1利用平衡二叉树实现一个动态查找表实现动态查找表的三种基本功能查找、插入和删除1初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择2每种操作均要提示输入关键字在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中每次插入或者删除一个结点后，应更新平衡二叉树的显示每次操作的关键字都要从文件中读取，并且关键字的集合限定为短3整型数字},关键字浮现的顺序没有限制，允许浮现重复的{1,2,3关键字，并对其进行相应的提示平衡二叉树的显示采用图形界面画出图形

4、系统功能2打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程〃在平衡的二叉树中插入关键字;1Load fromdata fileAppendnew recordUpate special〃在平衡的二叉树中查找关键字；record Delete special record〃显示调整过的平衡二叉树；Quit//删除平衡二叉树中的关键字;〃结束、程序中执行的命令包括:

3、测试数据4平衡二叉树为；插入关键字调整后102345\/\z\17\/{p1-bf=0;；Cp-bf=1/*新结点插在的左子树上的情况*/else p2{p1-bf=-1;；*p-bf=o；*P=p2/*仍将指向新的根结点，并置其平衡因子为*p-bf=O;p07*m=0;以下是对删除算法的设计和实现假设要删除关键字为的结点，如果不在叶子结点2x x；上，则用它左子数中的最大值或者最小值取代如此反复取代,直到删除动作传递到某x个叶子接点删除叶子结点时，若需要进行平衡变换，可采用插入的平衡变换的反变换如左子树变矮对应于右子树长高；int DeleteAVLBSTree*p,KeyType x,int*m{/*在树中删除关键字为的结点*/AVL xintk;BSTNode*q;if*p NULL==return0;else ifx*p-key{k=DeleteAVL*p-lchild,x,taller;iftaller==1LeftProcessl*p taller;5return k;else ifx*p-key{k=DeleteAVL*p-rchild,x,taller;iftaller==1RightProcessl*p taller;5return k;/*找到了关键字为的结点，由指向它else xp7；{q=*P/*被删结点右子树为空*/if*p-rchild==NULL{*p=*p-lchild;freeq;*m=1;/*被删结点左子树为空else if*p-lchild==NULL7{*p=*p-rchild;freeq;*m=1;/*被删结点摆布子树都不为空else V{Delete2q,q-lchild taller;5iftaller==1LeftProcessl q,taller;*p=q;return1;void LeftProcessl BSTree*pjnt*m/*在删除结点时进行左处理*/{BSTNode*p1*p2;5if*p-bf==1/*需做调整*/{*p-bf=O;RR*m=1;else if*p-bf==O{*p-bf=-1;*m=0;else{p1=*p-rchild;ifp1-bf==O{*p-rchild=p1-lchild;p1-lchild=*p;p1-bf=1;*p-bf=-1;；*p=p1*m=0;/*需做调整else ifp1-bf==-1RR7{*p-rchild=p1-lchild;p1-lchild=*p;*p-bf=p1-bf=O;；*P=p1*m=1;/*需做调整else RL7{p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;*p-rchild=p2-lchild;p2-lchild=*p;ifp2-bf==0{*p-bf=O;p1-bf=0;}else ifp2-bf==-1；{*P-bf=1p1-bf=0;else{*p-bf=O;p1-bf=-1;p2-bf=0;；*P=p2*m=1;}void RightProcesslBSTree*p int*m5/*在删除结点时进行右处理7{BSTNode*p1,*p2;if*p-bf==-1{*p-bf=O;*m=-1;else if*p-bf==O■；{*P-bf=1else{p1=*p-lchild;ifp1-bf==O/*需做LL调整7{*p-lchild=p1-rchild;p1-rchild=*p;p1-bf=-1;*p-bf=1;=o；*P=p1*m=0;}/*需做调整*/else ifp1-bf==1LL{*p-lchild=p1-rchild;p1-rchild=*p;*p-bf=p1-bf=0;*p=p1;*m=1;else{p2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p1;*p-lchild=p2-rchild;p2-rchild=*p;ifp2-bf==0{*p-bf=O;p1-bf=0;}else ifp2-bf==1{*p-bf=-1;p1-bf=0;/*需做调整else LR7{*p-bf=O;p1-bf=1;p2-bf=0;；*P=p2*m=1;void Delete2BSTree q,BSTree*r,int*m/*由调用，用于处理被删除结点摆布子树均不为空的情况DeleteAVL V{if*r-rchild==NULL{q-key=*r-key;q=*r;*r=*r-lchild;freeq;*m=1;else{Delete2q,*r-rchild,taller;iftaller==1RightProcessl*r taller;5⑶以下是对二叉树输出的设计，包括以括号的形式输出和以图形的形式输出void DispBSTreeBST reeb/*以括号的形式输出*/ifb!=NULL％{printf”d”,b-key;ifb-lchild!=NULL||b-rchild!=NULL{printfHn;DispBST reeb-lchild;ifb-rchild!=NULL，，printf7;DispBSTreeb-rchild;；printf”void OutputTreeBSTreebjnt fxjntfyjnt prexjntprey/*以图形的形式输出*/{char str

[30];ifbb-x=fx;b-y=fy;sprintfstr n%dn b-key;35setcolorRED;outtextxyfx-2,fy-2,str;setcolor YELLOW;circlefx,fy,15;lineprex,prey fx,fy;5OutputTreeb-lchild fx-50fy+50fx,fy;555OutputTreeb-rchild fx+50fy+50fx,fy;

555、以下是对主函数部份的设计4void mainBSTreeb=NULL;int ikj n;33FILE*fp;int m

[50];；；/*用循环语句控制每次选择*/forfor{〃菜单//printfH\n=================Menu=======================\nn;printfn\n1:Load fromthe file;\nn;printfAn2:Append newrecord;\nH;printf\n3:Upate special record;\nH;printfH\n4:Delete specialrecord;\nH;printfn\n5:Quit;\nH;printfH\n=============================================\nn;printfAn Pleaseinput your choose:j=1-5\n\n j=H;％/*输入选择*/scanf d”,j;switchj/*从文件中读出数据*/case1:iffp=fopen”c:\\TC20\\nana.txtTrb==NULL{printfC\n Cannotopen file,strike any key exit!\nn;getch;exitO;；printfYi Pleaseinput thedatafs number:n=scanfH%dH,n;/*输入需要操作元素的范围即个数*/fori=1;i=n;i++fscanffp H%dH m+i;J JprintfAnYou canchose datafrom thisrange:\nn;printfH\nn;fori=1;i=n;i++printfH%d.%d nJm[i];/*在屏幕上显示出操作的数据*/printfn\nn;5break;printfAn Pleaseinput i:1-%d\n i=n,n;/*输入要插入第几个元素*/scanf%d,i;taller=0;调用插入函数*/lnsertAVLb,m[i],taller;/*break;；printf\n Upate specialrecordare:/*以括号形式显示出平衡二叉树*/DispBSTreeb;printfAn Strikeanykeyyou cansee treein picture!\nn;3getch;{/*以图形的形式显示出平衡二叉树*/int driver=DETECT;int mode;initgraphdriver modeHc:\\tc20n;J5setbkcolorBLUE;OutputTreeb,300,100,300,100;getch;closegraph;printfH\nH;break;printfAn Pleaseinput k:1-%d:\n k=H,n;/*输入要删除第几个元素*/scanf%d,k;/*调用删除函数操作*/DeleteAVLb m[k]taller;35break;/*退出程序*/case2:exitO;、各个函数之间的关系如下图所示:5图各个函数之间的关系图5

四、调试分析、在对插入和删除算法设计的时候，用到了一些函数的调用，但是当时忽略了一些变1量参数的标志“”，在调试时浮现了一些错误，从而使运行的结果不正确，使调试程序费时不少在今后的学习中要重视确定参数的变量和赋值属性的区分和标识、在进行插入和删除操作时，对于每次递归的调用，后面都要写上左处理或者右处理2的操作，比如在中找删除的合适位置，递归调用函数后要写上p-lchild DeleteAVL函数的操作LefeProcess

1、在设计用图形显示出平衡二叉树时，要在的编译器中运行程序，因为惟独3TC

2.0支持画图的功能在以后的学习中要熟悉掌握常用的几种编译器各自的特点，在编TC

2.0写程序时也要考虑到要在哪个编译器中运行、创建一个文本后，在文本中写数据时，数据与数据之间不要用逗号相隔，要用空格4间隔，否则读出的数据不是文本中的数据、算法的时空分析5由于二叉树的存储结构采用的是链式存储，每一个二叉树的结点至少包括三个域1数据域和左、右指针域各种操作的算法时间复杂度基本比较合理例如LeftProcess，、和的实践复杂度都为RightProcess LeftProcesslRightProcessl01DispBSTree和的时间复杂度都为为平衡二叉树中结点的个数OutputTree0n,n对插入算法时间复杂度的分析如下设在插入关键字之前，平衡二叉树2InsertAVL e中已有个关键字，在插入时，要找到插入的合适位置，需要次对函数n en InsertAVL；的递归调用，所以时间复杂度为每次算法结束后，都有对二叉树的左0n InsertAVL；处理或者右处理，时间复杂度为所以整个插入算法的时间复杂度为0n0n对删除算法时间复杂度的分析和插入算法的分析类似，其时间复杂度也3DeleteAVL为0n、本次实习作业采用数据抽象的程序设计方法，将程序划分为四个层次结构主程序6模块、动态查找表单元模块、二叉树单元模块和结点结构模块使得设计思路清晰，实现时调试基本顺利，并且各个模块具有较好的可重用性通过这次实习，我确实得到了一次良好的程序设计训练

五、用户手册、本程序的运行环绕为下饿仿真系统，执行文件为1XP DOSNN.exeo、进入演示程序后即显示文本方式的用户界面2=================Menu=======================；1Load frontthe file；2Append neMpecopd；3Upate specialrecord；4:Delete speciali»eco»d；5QuitPlease inputyour choose=j=l-5J-.图菜单

6、进入“从文件中读数据、“插入元素3IvLoad fromdata file,”2Append new〉”和“删除元素命令后，即提示键入操作元素的范围（即record3Delete specialrecord个数），要插入或者删除第几个元素，结束符为“回车符”、接受其他命令后即执行相应运算和显示相应结果4

六、测试结果、从文件中读出个元素:110=================Menu=======================；1Load fromthe file；2Append newrecord；3Upatespecialrecord；4Deletespecialrecord；5QuitPlease inputyourchoose:j=l-5j=l Pleaseinput thedatas numbern=10You canchose datafrom thisrange:

1.

92.

03.

74.

145.

186.ll

7.

168.

219.10图从文件中读出数据

7、插入关键字之前平衡二叉树为210图插入关键字之前的平衡二叉树插入关键字之后，平衡二叉树为81010图插入关键字之后的平衡二叉树

910、删除关键字之后，平衡二叉树为314图删除关键字之后的平衡二叉树1014图插入关键字之后的平衡二叉树210；删除关键字调整后14图删除关键字后的平衡二叉树314查找关键字11;输出The data is here!

七、附录源程叙文件名清单〃定义平衡二叉树的抽象数据类型dy.h〃在平衡二叉树中插入关键字算法的实现insert.h〃在平衡二叉树中删除关键字算法的实现deleted〃显示平衡二叉树算法的实现disp.h〃主程序nn.c〃存放数据元素的文件nana.txt9图查找关键字后的平衡二叉树311

二、概要设计本次实验目的是为了实现动态查找表的三种基本功能查找、插入和删除动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型动态查找表和二叉树、动态查找表的抽象数据类型定义为1ADT DynamicSearchTable{数据对象是具有相同特性的数据元素的集合各个数据元素均含有类型相D D同，可惟一标识数据元素的关键字数据关系数据元素同属于一个集合R基本操作PlnitDSTableST;操作结果构造一个空的动态查找表DToDestroyDST ableDT;初始条件动态查找表存在DT操作结果销毁动态查找表DToSearch DSTableDT,key;初始条件动态查找表存在，为和关键字类型相同的给丁值DT key操作结果若中存在其关键字等于的数据元素，则函数值为该元素的DT key值或者在表中的位置，否则为“空”InsertDST ableDT,e;初始条件动态查找表存在，为待插入的数据元素DT e；操作结果若中不存在其关键字等于的数据元素，则插入至DT e,key eU DTDeleteDSTableDT,key;初始条件动态查找表存在，为和关键字类型相同的给定值DT key操作结果若中存在其关键字等于的数据元素，则删除之DT key}ADT DynamicSearchTable、二叉树抽象数据类型的定义为2ADT BinaryTree{数据对象是具有相同特性的数据元素的集合D D数据关系R若则称为空的二叉树；D=C,R=C,BinaryTree若，则是如下二元关系DW R={H},H在中存在惟一的称为根的数据元素它在关系下无前驱；1D root,H若则存在且2D—{root}WO,D—{root}={D1,Dr},D1GDr=2;若，则中存在惟一的元素且存在上的关3D1W D1x1,root,x1eH,D1；系若，则中存在惟一的元素且H1eH DrWDr xr,root,xreH,；；存在上的关系Dr HreHH={root,x1,root,xr,H1,Hr}是一棵符合本定义的二叉树，称为根的左子树，4D1,{H1}是符合本定义的二叉树，称为根的右子树Dr,{Hr}基本操作PlnitBiTreeT;；操作结果构造空的二叉树TDestroy BiTreeT;初始条件二叉树存在T操作结果销毁二叉树ToCreateBiT reeT,definition;初始条件给出的定义defidtion T操作结果按让构造二叉树defin ionTBiTreeEmptyT;初始条件二叉树存在T操作结果若为空二叉树，则返回否则T TRUE,FALSEoLeftChildT,e;初始条件二叉树存在，是中某个结点T eT操作结果返回的左孩子若无左孩子，则返回“空”e eRightChildT,e;初始条件二叉树存在，是中某个结点T eT操作结果返回的右孩子若无右孩子，则返回“空”e elnsertAVLT,e taller;5初始条件二叉树存在，为要插入的结点，反映长高与否T etaller T操作结果若在平衡二叉树中不存在和相同关键字的结点，则插入一个数据元素e为的结点，并返回否则返回若因插入而使二叉排序树失去平衡，e1,Oo则旋转处理RightProcessT;初始条件二叉树存在T操作结果对以为根的二叉树做右旋转处理，处理之后指向新的树根结点T TLeftProcessT;初始条件二叉树存在T操作结果对以为根的二叉树做左旋转处理，处理之后指向新的树根结点T T、本程序包括四个模块3主程序模块1void main{敏；；{switch接受命令；处理命令；二叉树单元模块2实现二叉树的抽象数据类型动态查找表单元模块3实现动态查找表的抽象数据类型结点结构模块4实现平衡二叉树的查找、插入和删除操作各模块之间的关系主程序模块动态查找表单元模块二叉树单元模块:结点结构模块图各模块之间的关系4

三、详细设计、元素类型、结点类型和指针类型;1typedef intInfoTypetypedef structnode/*记录类型*/InfoType data;/*其他数据域//〃摆布孩子指针*/Struct nodeIchild,rchild;}BSTNode,*BSTree;status MakeNodeBSTNodep,ElemType e{/*分配由指向的数据元素为、后继为空”的结点,并返回扩若p eTRUE,分配失败,则返回FALSE7p=BSTNode*mallocsizeofBSTNode;if!p returnFALSE;p-data=e;p-next=NULL;return TRUE;void FreeNodeBSTNodep{/*释放所指结点*/p、根据动态查找表的基本操作特点表结构本身是在查找过程中动态产生的，即对于给定2否则插入关键字等于的记录现在此次试验中主要是利用平衡二叉树来实key动态查找表平衡二叉排序树定义为typedef intInfoType/*元素类型*/typedef intKeyType;typedef structnode KeyTypekey;/*关键字项*/int bf;/*平衡因子*/InfoType data;〃其他数据域*/Struct nodeIchild,rchild:〃摆布孩子指针*/值若表中存在其关键字等于的记录，则查找成功返回,key,key}BSTNode,*BSTree;平衡二叉数没有长高不需要调整；，二叉数长高,需要验证int taller;/*taller=0,taller=1是否还是平衡二叉数，如果不是，则需要进行调整.*/平衡二叉树的基本操作定义如下int lnsertAVLBSTNode*b,KeyType e,int*m;〃如果在平衡二叉排序树中不存在有相同关键字的结点，则插入一个数据元素为b ee的新结点，并返回否则返回.如果因插入而使二叉排序树失去平衡，则做平衡处理，1,0指针反应长高与否m bvoid LeftProcessBSTree*p,int*m;〃在插入结点时对以指针所指结点为根的二叉树做左平衡旋转处理pvoid RightProcessBSTree*p,int*m;〃在插入结点时对以指针所指结点为根的二叉树做右平衡旋转处理pint DeleteAVLBSTree*p,KeyType xjnt*m;/〃在以为根的平衡二叉树中删除关键字为的结点，如果因删除而使平衡二叉树失p e去平衡，则做平衡处理，指针反应树长高与否m bvoidLeftProcesslBSTree*p,int*m;〃由函数调用，在删除结点时进行左处理DeleteAVLvoid RightProcesslBSTree*p,int*m;〃由函数调用，在删除结点时进行右处理DeleteAVLvoid Delete2BSTree q,BSTree*r,int*m;〃由调用，用于处理被删除结点都不为空的情况DeleteAVLvoid DrawTreeBSTreeb;〃对以为根的平衡二叉树，以括号的形式显示出来bvoid OutputTreeBST reebjnt fxjntfy,int prexjntprey;〃用图形把平衡二叉树显示出来、本程序实现的是演示平衡二叉树的操作过程，包括插入和删除操作，以下是它们算法的3设计插入数据操作，如果数据存在，输出提示信息，如果不存在，则把此数据插入到入平1衡二叉树中，并做相应的调整，使之还为平衡二叉树以下是对插入操作的设计int lnsertAVLBSTree*b,KeyType e,int*m/*若在平衡的二叉排序树中中不存在和有相同关键字的结点，则插入一个数据元素为b e的新结点，并返回若因插入而使二叉排序树失去平衡，则做平衡旋转处理，的e Ootaller值反应长高与否7/*原为空树，插入新结点，树长高，置{if*b==NULL taller=*m=1*/{*b=BSTNode*mallocsizeofBSTNode;*b-key=e;*b-lchild=*b-rchild=NULL;*b-bf=O;*m=1;else/*树中已存在和有相同关键字的结点，则再也不进{if e==*b-key e行插入*//*置树没有长高，不须进行调整*/{*m=0;taller=*m=0,printfn\n Thedataishere!\n;/*输出提示信息*/return0;/*继续在*的左子树中进行搜索*/ife*b-key b{iflnsertAVL*b-lchild,e,taller==O/*存在和有相同关键字的元素，则不需要插入*/return0;e/*已插入在*的左子树中且左子树长高*/if taller==1bLeftProcess*b,taller;/*已插入在*的右子树中且左子树长高*/else b{iflnsertAVL*b-rchild,e,taller==O/*存在和有相同关键字的元素则不需要插入*/return0;e/*已插入在*的右子树中且右子树长高*/if taller==1bRightProcess*b,taller;return1;voidLeftProcessBSTree*p,int*m/*对以指针所指结点为根的二叉树做左平衡旋转处理，算法结束后，指针指向新的根p p结点*/{BSTNode*p1,*p2;/*原本摆布子树等高，现因左子树增高而使树增高*/if*p-bf==O；{*P-bf=1；*m=1/*新结点插在的右子树上的情况*/p2讦原本右子树比左子树高，现摆布子树等高*/else*p-bf==-1/*{*p-bf=O;/*树没有长高*/*m=0;/*原本左子树比右子树高，需做左子树的平衡处理*/else指向*的左子树根结点*/{p1=*p-lchild;/*p1p/*新结点插入在*的左孩子的右子树上，要做调整*/ifp

1.bf==1p LL的左孩子为的右孩子*/{*p-lchild=p1-rchild;/*p p1的右孩子为p1-rchild=*p;/*p1p*/和的平衡因子都变为0*1*p-bf=p1-bf=0;/*p1P；取代以前的位置*/*P=p1/*p1p}/*如果新结点插在*的左子树根结点的右子树上，需做调整*/else ifp1-bf==-1b LR指向的右子树根结点*//*p2p1{p2=p1-rchild;/*p1的右孩子为p2的左孩子*/p1-rchild=p2-lchild;的左孩子为/*p2p17p2-lchild=p1;的左孩子为的右孩子*//*p p2*p-lchild=p2-rchild;的右孩子为/*p2p*/p2-rchild=*p;/*新结点插在处做叶子结点的情况*/p2ifp2-bf==0*p-bf=p1-bf=0;else/*新结点插在的左子树上的情况*/p2ifp2-bf==1{p1-bf=0;else{p1-bf=1;Cp-bf=O;；*P=p2〃仍将指向新的根结点，并置其平衡因子为*p-bf=O;p0*//*返回值为*在递归调用时，挨次判*m=0;m=taller,InsertAVL断每一个结点的平衡因子是否在之间*/-1,1void RightProcessBSTree*p,int*m/*对以指针所指结点为根的二叉树做左平衡旋转处理，算法结束后，指针p{*p-rchild=p1-lchild;p1-lchild=*p;*p-bf=p1-bf=0;；*p=p1/*新结点插入在*的右孩子的左子树上，要做调整else ifp1-bf==1p RL{p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;*p-rchild=p2-lchild;p2-lchild=*p;/*新结点插在处做叶子结点的情况*/ifp2-bf==0p2*p-bf=p1-bf=0;/*新结点插在的右子树上的情况*/else ifp2-bf==-1p2指向新的根结点*/p{BSTNode*p1,*p2;if*p-bf==O/*原本摆布子树等高，现因右子树增高而使树增高*/{*p-bf=-i;*m=1;/*原本左子树比右子树高，现摆布子树等高*/else if*p-bf==1；{*p-bf=O*m=0;/*原本右子树比左子树高，需做右子树的平衡处理*/else指向*的右子树根结点*//*p1p{p1=*p-rchild;/*如果新结点插在*的左子树根结点的右子树上，需做bif p1-bf==-1调整文/RR。