广工数据结构课设-平衡二叉树演示(文档尾部含源码下载地址)课案

1、课程设计报告课程名称学院专业班级数据结构课程设计计算机学院计科9班学生姓名苏庆指导教师2015年7月6日一、需求分析程序平衡二叉树的演示是对平衡二叉树的创建、插入、删除、查找、合并、分裂功能的实现，以及用凹入表的形式将其展示给用户。（1）输入的形式是数字，无论对功能的选则还是对数据的录入，都是以数字的形式进行输入，无需使用文件保存数据。输入值得范围在使用过程中会有说明。（2）输出的形式是在Dos界面进行输出，（3）程序所能达到的功能：A. 创建一棵非空平衡二叉树B. 创建一棵空的平衡二叉树C. 向平衡二叉树中添加结点D. 从平衡二叉树中删除结点E. 在平衡二叉树中查找结点F. 以凹入表的形式输

2、出一棵二叉树G. 以括号表示法输出一棵二叉树附加功能：F.合并两棵平衡二叉树H. 分裂一棵平衡二叉树二、概要设计（1）本程序涉及到的数据类型有：链栈，链队列，平衡二叉树，结构体数组（2）主程序是负责对各个功能进行展示，然后根据输入来选择进行相对应的功能，代码如下：intmain()intm;BBSTreeT=NULL;SetColor();InitView();printf("nttt请输入你的选择：")；scanf("%d",&m);getchar();while(l)switch(m)case1:T=item_1();break;case2:

3、item_2(T);break;case3:item_3(T);break;case4:item_4(T);break;case5:item_5(T);break;case6:item_6();break;case7:item_7();break;if(m=8)item_8();break;elseif(m>8llmvl)system("CLS");InitView();printf("nttt输入错误，请重新输入!n");printf("nttt请输入你的选择：“)；scanf("%d",&m);getcha

4、r();return0;(3) 各模块之间的关系主程序模块创建非空树创建空树添力口结点删除结点查找结点合并平衡二叉树分裂平衡二叉树退出三、详细设计(1)数据类型的定义/*存放输入数据的数组结构体*/typedefstructArrayNodeRcdTypedata;ArrayNode*next;ArrayNode,*Array;/*平衡二叉树结构体*/typedefstructBBSTNodeRcdTypedata;intbf;BBSTNode*lchild,*rchild;BBSTNode,*BBSTree;/*链队列结构体*/typedefstructLQNodeBBSTreeelem;s

5、tructLQNode*next;LQNode,*QueuePtr;/*队列结点结构体*/typedefstructQueuePtrfront;QueuePtrrear;LQueue;/*栈结点结构体*/typedefstructLSNodeBBSTreedata;数据域structLSNode*next;指针域LSNode,*LStack;结点和链栈类型(2)伪代码：A. 建树操作beginBBSTreeTArrayaa=GetInputToArray();获取到输入的数组Whilea!=NULLInsertAVL(T,a->data)a=>a->nextEndB. 插入结

6、点beginif(NULL=T)T->data=eT->bf=EHT->lchild=NULLT->rchild=NULLelseif(e=T->data)书中已存在和e相等的结点returnFALSE;elseif(e<T->data)if(!InsertAVL(T->lchild,e)returnFALSE;if(TRUE=taller)switch(T->bf)caseLH:LeftBalance(T);taller=FALSE;break;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T-&

7、gt;bf=EH;taller=FALSE;break;elseif(FALSE=InsertAVL(T->rchild,e)returnFALSE;if(TRUE=taller)switch(T->bf)caseLH:T->bf=EH;taller=FALSE;break;caseEH:T->bf=RH;taller=TRUE;break;caseRH:RightBalance(T);taller=FALSE;break;returnTRUE;EndC.删除操作begin当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=lstaticinttag=0;if(t=

8、NULL)returnFALSE;如果不存在元素，返回失败elseif(e=t->data)BBSTNode*q=NULL;如果该结点只有一个孩子，则将自子树取代该结点if(t->lchild=NULL)q=t;t=t->rchild;free(q);shorter=TRUE;elseif(t->rchild=NULL)q=t;t=t->lchild;free(q);shorter=TRUE;如果被删结点有两个孩子，则找到结点的前驱结点,并将前驱结点的值赋给该结点，然后删除前驱结点elseq=t->lchild;while(q->rchild)q=q-

9、>rchild;t->data=q->data;if(t->lchild->data=q->data)tag=1;DeleteAVL(t->lchild,q->data,shorter);if(tag=l)BBSTreer=t->rchild;if(NULL=r)t->bf=0;elseswitch(r->bf)caseEH:t->bf=-1;break;default:RightBalance(t);break;elseif(evt->data)左子树中继续查找if(!DeleteAVL(t->lchild,

10、e,shorter)”returnFALSE;删除完结点之后，调整结点的平衡因子if(shorter&&(tag=0)switch(t->bf)caseLH:t->bf=EH;shorter=TRUE;break;caseEH:t->bf=RH;shorter=FALSE;break;如果本来就是右子树较高，删除之后就不平衡,需要做右平衡操作caseRH:RightBalance(t);右平衡处理if(t->rchild->bf=EH)shorter=FALSE;elseshorter=TRUE;break;elseif(e>t->da

11、ta)/右子树中继续查找if(!DeleteAVL(t->rchild,e,shorter)returnFALSE;删除完结点之后，调整结点的平衡因子if(shorter&&(tag=O)switch(t->bf)caseLH:LeftBalance(t);左平衡处理if(t->lchild->bf=EH)shorter=FALSE;elseshorter=TRUE;break;caseEH:t->bf=LH;shorter=FALSE;break;caseRH:t->bf=EH;shorter=TRUE;break;if(tag=l)int

12、depthLeft=BBSTreeDepth(t->lchild);intdepthRight=BBSTreeDepth(t->rchild);t->bf=depthLeft-depthRight;returnTRUE;EndD. 查找操作Beginif(T=NULL)returnNULL;if(e=T->data)returnT;elseif(e>T->data)returnSearchAVL(T->rchild,e);elsereturnSearchAVL(T->lchild,e);EndE. 合并操作BeginStatustaller=TR

13、UE;Arraya=NULL;a=GetArrayFromTree(T2);while(a!=NULL)taller=TRUE;InsertAVL(T1,a->data,taller);a=a->next;returnT1;EndF. 分裂操作BeginArraya=NULL;Statustaller;a=GetArrayFromTree(Ttl);获取到树转化为的数组if(Tt1=NULL)returnFALSE;elsewhile(a!=NULL)if(a->datav=x)taller=TRUE;InsertAVL(Tt2,a->data,taller);a=a-

14、>next;elsetaller=TRUE;InsertAVL(Tt3,a->data,taller);a=a->next;returnTRUE;End(3)关系图A.建树操作结束B.添加结点操作D.查找结点操作F.分裂操作四、调试分析1. 调试过程中所遇到的问题：运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题，但是换了个编译器还是同样的问题，后来我上网查询了有关资料，大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉，一条一条测试，调试过程很漫长，最后才发现是内存泄露和空指针异常，将指针不适用之后指向为NULL，才把问题解决了。2. 经验和体会a）

15、在做一个比较大的程序过程中，应该学会边编写程序边运行，即当你完成了一个比较小的功能时便对其调试，这样有助于我们高效地完成项目，而且在调试BUG的过程也可以大大减小其难度。b）必须要有良好的编程习惯。首先编码风格一定要规范，这样不仅有利于读者和编程者对代码的阅读，更有利于对代码的维护。其次要对代码要细心，比较一些指针的初始化和不需要时指为空，这些都是可以极大减少我们出现BUG的几率。c）写的程序一定要人性化，现在的应用都讲究与人交互的重要性，其避免不了使用各种炫酷的图形界面，但我们要考虑的是，即便是C语言，没有什么图形界面，我们也一定要考虑人性化的问题。五、使用说明1本程序的可执行文件是：平衡二

16、叉树的演示.exe2.双击exe文件，进入主界面：欢迎来到平衝二叉树的演示界面12345678叉叉-空的芽工叉叉-平平醫点点占小棵颗一一结结结两一建建加塡开龍添嚳一合八虽厦囲锵加;删魂疇鬥系绩自动创建一棵空树!说明：1本程序平衡二戈4. 功能六七写功能二;.三兰四，五无关联并相互独立?请输入你的选择:3然后我们应该先创建一棵非空二叉树或者是空的二叉树，输入1或者2,按回车键，此处我们输入1，如下:欢迎来到平衡二叉树的演示界面叉X-空的斐工囂点点点棵颗一一结结结两一建建加舅幵審添嚳一合八敏叉叉-平平脱明：本程序平衡二瑯寸的元素均为数字，输入时请输.鬥系绩自动创建一棵空树!请输入你的选择：1请输入

17、生成树的数字序列（按,回车键，结束:4.此时，程序提示我们输入树的序列，我们可以以此输入数字，不同数字用空格隔开，按回车表示输入完成，例如，我们输入102030405060回车,得到如下，程序提示我们创建成功，并输出了该平衡二叉树，此时按任意键返回。5. 返回到了首页，此时我们可以输入3,往此树中添加结点，按回车确认。此时，程序会把平衡二叉树展示出来，然后提示用户输入要删除的元素,假如我们要添加5,输入5,按回车。欢迎来到平衡二叉树的演示界面叉叉叉叉-空的i娄工平平囂占苦告心棵颗一一结结结两一建建加壕开審哩一喰112345678兑明：;功能六七写功能二;三01工任认按，回车键，厦囲莆加;册|除

18、,查找坯,四，五无关联，并柚互独釘口'莎鬥卷绒自动创建一棵空树!请输入你的选择：3添加失败！请输入你的选择:6. 此时提示添加失败，是因为5重复了，假如我们重新添加，选择功能3,此时添加&按回车，得到如下：7. 提示添加成功，此时我们再此时删除功能，我们选择功能4,得到如下界面，假如我们要删除4,输入4,按回车：8. 得到界面如下，提示删除成功，我们发现平衡二叉树更新了，每个节点的平衡因子也更新了。9.我们再输入5,测试查找功能。提示输入查找元素，我们输入6。10.程序便把原来的平衡二叉树和以查找结点为根节点的子树都输出来。此时我们再运行合并平衡二叉树的功能。选择6,回车。欢迎

19、来到平衡二叉树的演示界面叉叉叉叉-空的鲁垂工平平囂占苦苦心棵颗一一结结结两一建建加第幵列茁書貢1L12345678:本程序平衡二瓒1熾元素均为数字礬4|矍喀五无关联并相互独立?鬥系綴自动创建一棵空树!请输入你的选择：6请输入树T1的数字序列（按，回车键，结束:11.此时系统提示我们输入第一棵树的序列，假如我们输入12345然后系统会提示我们输入第二棵树的序列，假如我们输入789请输入树T1的数字序列（按回车键,结束片123456请输入树臨的数字序列（按，回车键,结束兀789-12.程序会把T1T2T3用括号表示法输出13.此时提示按回车会输出要合并的两棵树和合并后的树的凹入表平衡二叉树T1为:

20、9<bf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-1>3<bf：0>2<bf：0>l<bf：0>平衡二叉亦2另:9<bf：0>8<bf：0>7<bf：0>合并后的平衡二叉树T3为:9<bf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-1>3<bf：0>2<bf：0>l<bf：0>14

21、. 我们再输入7来此时分裂一棵平衡二叉树的功能欢迎来到平衡二叉树的演示界面一.：一：叉叉-空的斐工一.：一V叉叉-平平囂占苦苦小棵颗一一结结结两一建建加壕幵審添嚳合爲12345678貝动创建棵空刪2-W3.若煜能六卡曲選进昌：轆霾请输入你的选择：？请输入树的数字序列（按,回车键，结束:15. 此时提示我们输入树的序列，输入完将提示我们输入x的值，即树T将分裂成一棵均是小于等于x的树，和一棵均大于x的树。假如我们测试数据是：T:12345678910x:5此时输出的是:按回车键查看T1,T2,T3的凹入表.分割前的平衝二叉树Ti为：4£2灯，3”8£6£5,?”95

22、”10分割前的平衝二叉树T1：10<b£：B>9<bf：-1>8<bf：8>7<bf：8>6<bf：0>5<b£：B>4<bf：-1>3<bf：0>2<bf：B>l<bf：0>分割后小于等于5的平衡二叉树T2为：4<2<1,3>,8<6<5,7>,9<#,10>>>环軌鬲石萼召鬲祈三反祐二5<bf：0>4<bf：0>3<bf：0>2<bf：-1>l&

23、lt;bf：0>分割后大于5的平衝二叉树T3为：4<2<1,3>,8<6<5,7>,9<#,10>>>环軌肩央召鬲祈三反祐二10<bf：0>9<bf：-1>8<bf：0>7<bf：0>6<bf：-1>16. 最后便是退出功能，选择&程序提示我们是否退出,输入Y(y)退出程序，输入N(n)返回主界面*欢迎来到平衡二叉树的演示界面*叉叉-空的垂工叉叉囂占小点占小棵颗一一结结结两一建建加舅幵審添嚳亠口鼠12345678二XXXX二XXXXXXX二XXX二XXX二XXX二XXXX二XXXXXXX二XXX二XXX二XXX二XXXX二XXXXXXX二XXX二XXX二XXXk聽期幣勰备異轟卷統自动创建一棵空树!说明：本程序壬衡专2.3. _4. 功能天：七写功能二;'二三阿五无关联并相互独立?请输入你