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

课程设计报告课程名称 数据结构课程设计 学 院 计算机学院 专业班级 计科9班 学 号 学生姓名 指导教师 苏庆 2015 年 7 月 6 日一、 需求分析程序平衡二叉树的演示是对平衡二叉树的创建、插入、删除、查找、合并、分裂功能的实现，以及用凹入表的形式将其展示给用户。（1） 输入的形式是数字，无论对功能的选则还是对数据的录入，都是以数 字的形式进行输入，无需使用文件保存数据。输入值得范围在使用过程 中会有说明。（2） 输出的形式是在Dos界面进行输出，（3） 程序所能达到的功能： A.创建一棵非空平衡二叉树 B.创建一棵空的平衡二叉树 C.向平衡二叉树中添加结点 D.从平衡二叉树中删除结点 E.在平衡二叉树中查找结点 F.以凹入表的形式输出一棵二叉树 G.以括号表示法输出一棵二叉树 附加功能： F.合并两棵平衡二叉树 H.分裂一棵平衡二叉树二、 概要设计（1） 本程序涉及到的数据类型有：链栈，链队列，平衡二叉树， 结构体数组 （2）主程序是负责对各个功能进行展示，然后根据输入来选择进行相对应 的功能，代码如下：int main()int m;BBSTree T = NULL;SetColor();InitView();printf(nttt 请输入你的选择：);scanf(%d,&m);getchar();while(1)switch(m)case 1:T = item_1();break;case 2:item_2(T);break;case 3:item_3(T);break;case 4:item_4(T);break;case 5:item_5(T);break;case 6:item_6();break;case 7:item_7();break;if(m=8)item_8();break;else if(m8|mdata) a = a-next EndB.插入结点begin if(NULL=T) T-data = e T-bf = EH T-lchild = NULL T-rchild = NULL else if(e=T-data) /书中已存在和e相等的结点 return FALSE; else if(edata) if(!InsertAVL(T-lchild, e) return FALSE; if(TRUE=taller) switch(T-bf) case LH: LeftBalance(T); taller = FALSE; break; case EH: T-bf = LH; taller = TRUE; break; case RH: T-bf = EH; taller = FALSE; break; else if(FALSE=InsertAVL(T-rchild, e) return FALSE; if(TRUE=taller) switch(T-bf) case LH: T-bf = EH; taller = FALSE; break; case EH: T-bf = RH; taller = TRUE; break; case RH: RightBalance(T); taller = FALSE; break; return TRUE;EndC.删除操作begin /当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1 static int tag = 0; if(t = NULL) return FALSE; /如果不存在元素，返回失败 else if(e=t-data) BBSTNode *q = NULL; /如果该结点只有一个孩子，则将自子树取代该结点 if(t-lchild = NULL) q = t; t = t-rchild; free(q); shorter = TRUE; else if(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) BBSTree r = t-rchild; if(NULL=r) t-bf = 0; else switch(r-bf) case EH: t-bf=-1;break; default: RightBalance(t);break; else if(edata) /左子树中继续查找 if(!DeleteAVL(t-lchild, e, shorter) return FALSE; /删除完结点之后，调整结点的平衡因子 if(shorter&(tag=0) switch(t-bf) case LH: t-bf = EH; shorter = TRUE; break; case EH: t-bf = RH; shorter = FALSE; break; /如果本来就是右子树较高，删除之后就不平衡，需要做右平衡操作 case RH: RightBalance(t); /右平衡处理 if(t-rchild-bf = EH) shorter = FALSE; else shorter = TRUE; break; else if(et-data) /右子树中继续查找 if(!DeleteAVL(t-rchild, e, shorter) return FALSE; /删除完结点之后，调整结点的平衡因子 if(shorter&(tag=0) switch(t-bf) case LH: LeftBalance(t); /左平衡处理 if(t-lchild-bf = EH) shorter = FALSE; else shorter = TRUE; break; case EH: t-bf = LH; shorter = FALSE; break; case RH: t-bf = EH; shorter = TRUE; break; if(tag=1) int depthLeft = BBSTreeDepth(t-lchild); int depthRight = BBSTreeDepth(t-rchild); t-bf = depthLeft - depthRight; return TRUE; EndD.查找操作Begin if(T=NULL) return NULL; if(e=T-data) return T; else if(eT-data) return SearchAVL(T-rchild, e); else return SearchAVL(T-lchild, e); EndE.合并操作Begin Status taller = TRUE; Array a = NULL; a = GetArrayFromTree(T2); while(a!=NULL) taller = TRUE; InsertAVL(T1, a-data, taller); a = a-next; return T1; EndF.分裂操作 Begin Array a = NULL; Status taller; a = GetArrayFromTree(Tt1); /获取到树转化为的数组 if(Tt1=NULL) return FALSE; else while(a!=NULL) if(a-datadata, taller); a = a-next; else taller = TRUE; InsertAVL(Tt3, a-data, taller); a = a-next; return TRUE; End（3） 关系图A. 建树操作 B.添加结点操作C.删除结点操作D.查找结点操作E.合并操作F.分裂操作四、 调试分析1. 调试过程中所遇到的问题：运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题，但是换了个编译器还是同样的问题，后来我上网查询了有关资料，大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉，一条一条测试，调试过程很漫长，最后才发现是内存泄露和空指针异常，将指针不适用之后指向为NULL，才把问题解决了。2. 经验和体会a) 在做一个比较大的程序过程中，应该学会边编写程序边运行，即当你完成了一个比较小的功能时便对其调试，这样有助于我们高效地完成项目，而且在调试BUG的过程也可以大大减小其难度。b) 必须要有良好的编程习惯。首先编码风格一定要规范，这样不仅有利于读者和编程者对代码的阅读， 更有利于对代码的维护。其次要对代码要细心，比较一些指针的初始化和不需要时指为空，这些都是可以极大减少我们出现BUG的几率。c) 写的程序一定要人性化，现在的应用都讲究与人交互的重要性，其避免不了使用各种炫酷的图形界面，但我们要考虑的是，即便是C语言，没有什么图形界面，我们也一定要考虑人性化的问题。五、 使用说明1. 本程序的可执行文件是：平衡二叉树的演示.exe2. 双击exe文件，进入主界面：3. 然后我们应该先创建一棵非空二叉树或者是空的二叉树，输入1或者2， 按回车键，此处我们输入1，如下：4. 此时，程序提示我们输入树的序列，我们可以以此输入数字，不同数字用 空格隔开，按回车表示输入完成，例如，我们输入10 20 30 40 50 60回车， 得到如下，程序提示我们创建成功，并输出了该平衡二叉树，此时按任意 键返回。5. 返回到了首页，此时我们可以输入3，往此树中添加结点，按回车确认。此时，程序会把平衡二叉树展示出来，然后提示用户输入要删除的元素，假如我们要添加5，输入5，按回车。6. 此时提示添加失败，是因为5重复了，假如我们重新添加，选择功能3，此时添加8，按回车，得到如下：7. 提示添加成功，此时我们再此时删除功能，我们选择功能4，得到如下界面，假如我们要删除4，输入4，按回车：8. 得到界面如下，提示删除成功，我们发现平衡二叉树更新了，每个节点的平衡因子也更新了。9.我们再输入5，测试查找功能。提示输入查找元素，我们输入6。10. 程序便把原来的平衡二叉树和以查找结点为根节点的子树都输出来。 此时我们再运行合并平衡二叉树的功能。选择6，回车。11. 此时系统提示我们输入第一棵树的序列，假如我们输入1 2 3 4 5 然后系统会提示我们输入第二棵树的序列，假如我们输入 7 8 912. 程序会把T1 T2 T3用括号表示法输出13. 此时提示按回车会输出要合并的两棵树和合并后的树的凹入表14. 我们再输入7来此时分裂一棵平衡二叉树的功能15. 此时提示我们输入树的序列，输入完将提示我们输入x的值，即树T将分裂成一棵均是小于等于x的树，和一棵均大于x的树。假如我们测试数据是：T: 1 2 3 4 5 6 7 8 9 10x:5 此时输出的是：16. 最后便是退出功能，选择8，程序提示我们是否退出，输入Y（y）退出程序，输入N（n）返回主界面六、 测试结果测试数据：平衡二叉树T: 1 2 3 4 5 6 7 8 9 10 添加元素：11 删除元素：5 查找元素：8添加11删除8测试数据T1：5 8 4 10 62T2：5 6 20 34 合并两树得到：测试数据T: -20 80 90 1 0 6 8 x :5 分裂平衡二叉树得到：七、 附录源程序文件名清单：dataStruction.cpp /源程序代码AVL_head.h /自定义的头文件平衡二叉树的演示.exe/可执行文件源码下载地址：