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

课程设计报告课程名称数据结构课程设计学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2023年7月6日需求分析程序《平衡二叉树的演示》是对平衡二叉树的创立、插入、删除、查找、合并、分裂功能的实现，以及用凹入表的形式将其展示给用户。输入的形式是数字，无论对功能的选那么还是对数据的录入，都是以数 字的形式进行输入，无需使用文件保存数据。输入值得范围在使用过程 中会有说明。输出的形式是在Dos界面进行输出，程序所能到达的功能：A.创立一棵非空平衡二叉树B.创立一棵空的平衡二叉树C.向平衡二叉树中添加结点D.从平衡二叉树中删除结点E.在平衡二叉树中查找结点F.以凹入表的形式输出一棵二叉树G.以括号表示法输出一棵二叉树附加功能：F.合并两棵平衡二叉树H.分裂一棵平衡二叉树概要设计本程序涉及到的数据类型有：链栈，链队列，平衡二叉树，结构体数组〔2〕主程序是负责对各个功能进行展示，然后根据输入来选择进行相对应 的功能，代码如下：intmain(){ intm; BBSTreeT=NULL; SetColor(); InitView(); printf("\n\t\t\t请输入你的选择："); scanf("%d",&m); getchar(); while(1){ switch(m){ case1: T=item_1(); break; case2: 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>8||m<1){ system("CLS"); InitView(); printf("\n\t\t\t输入错误，请重新输入!!\n"); } printf("\n\t\t\t请输入你的选择："); scanf("%d",&m); getchar(); } return0;}各模块之间的关系三、详细设计数据类型的定义/*存放输入数据的数组结构体*/typedefstructArrayNode{RcdTypedata;ArrayNode*next;}ArrayNode,*Array;/*平衡二叉树结构体*/typedefstructBBSTNode{RcdTypedata;intbf;BBSTNode*lchild,*rchild;}BBSTNode,*BBSTree;/*链队列结构体*/typedefstructLQNode{BBSTreeelem;structLQNode*next;}LQNode,*QueuePtr;/*队列结点结构体*/typedefstruct{QueuePtrfront;QueuePtrrear;}LQueue;/*栈结点结构体*/typedefstructLSNode{BBSTreedata;//数据域structLSNode*next;//指针域}LSNode,*LStack;//结点和链栈类型伪代码：建树操作beginBBSTreeTArrayaa=GetInputToArray();//获取到输入的数组Whilea!=NULL{InsertAVL(T,a->data)a=>a->next}EndB.插入结点beginif(NULL==T){T->data=eT->bf=EHT->lchild=NULLT->rchild=NULL}elseif(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->bf=EH;taller=FALSE;break;}}}else{if(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=1staticinttag=0;if(t==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;}//如果被删结点有两个孩子，那么找到结点的前驱结点，//并将前驱结点的值赋给该结点，然后删除前驱结点else{q=t->lchild;while(q->rchild){q=q->rchild;}t->data=q->data;if(t->lchild->data==q->data){tag=1;}DeleteAVL(t->lchild,q->data,shorter);if(tag==1){BBSTreer=t->rchild;if(NULL==r)t->bf=0;else{switch(r->bf){caseEH:t->bf=-1;break;default:RightBalance(t);break;}}}}}elseif(e<t->data){//左子树中继续查找if(!DeleteAVL(t->lchild,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->data){//右子树中继续查找if(!DeleteAVL(t->rchild,e,shorter)){returnFALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)){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==1){intdepthLeft=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);}else{returnSearchAVL(T->lchild,e);}EndE.合并操作BeginStatustaller=TRUE;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(Tt1);//获取到树转化为的数组if(Tt1==NULL)returnFALSE;else{while(a!=NULL){if(a->data<=x){taller=TRUE;InsertAVL(Tt2,a->data,taller);a=a->next;}else{taller=TRUE;InsertAVL(Tt3,a->data,taller);a=a->next;}}}returnTRUE;End关系图建树操作B.添加结点操作C.删除结点操作D.查找结点操作E.合并操作F.分裂操作调试分析调试过程中所遇到的问题：运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题，但是换了个编译器还是同样的问题，后来我上网查询了有关资料，大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉，一条一条测试，调试过程很漫长，最后才发现是内存泄露和空指针异常，将指针不适用之后指向为NULL，才把问题解决了。经验和体会在做一个比拟大的程序过程中，应该学会边编写程序边运行，即当你完成了一个比拟小的功能时便对其调试，这样有助于我们高效地完成工程，而且在调试BUG的过程也可以大大减小其难度。必须要有良好的编程习惯。首先编码风格一定要标准，这样不仅有利于读者和编程者对代码的阅读，更有利于对代码的维护。其次要对代码要细心，比拟一些指针的初始化和不需要时指为空，这些都是可以极大减少我们出现BUG的几率。写的程序一定要人性化，现在的应用都讲究与人交互的重要性，其防止不了使用各种炫酷的图形界面，但我们要考虑的是，即便是C语言，没有什么图形界面，我们也一定要考虑人性化的问题。使用说明本程序的可执行文件是：平衡二叉树的演示.exe双击exe文件，进入主界面：然后我们应该先创立一棵非空二叉树或者是空的二叉树，输入1或者2， 按回车键，此处我们输入1，如下：此时，程序提示我们输入树的序列，我们可以以此输入数字，不同数字用 空格隔开，按回车表示输入完成，例如，我们输入102030405060回车， 得到如下，程序提示我们创立成功，并输出了该平衡二叉树，此时按任意 键返回。返回到了首页，此时我们可以输入3，往此树中添加结点，按回车确认。此时，程序会把平衡二叉树展示出来，然后提示用户输入要删除的元素