数据结构与算法设计课程设计-二叉排序树与平衡二叉树(13页).docx

《数据结构与算法设计课程设计-二叉排序树与平衡二叉树(13页).docx》由会员分享，可在线阅读，更多相关《数据结构与算法设计课程设计-二叉排序树与平衡二叉树(13页).docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构与算法设计课程设计-二叉排序树与平衡二叉树D04710043学 号： 201540410126课 程 设 计教 学 院计算机学院课程名称数据结构与算法设计B题 目二叉排序树与平衡二叉排序树专 业计算机科学与技术班 级2015级（1）班姓 名甘全中同组人员指导教师2016年12月26日 目 录一 概述21.1课程设计的目的21.2课程设计的要求2二 总体方案设计32.1二叉排序树的建立32.2二叉排序树的中序遍历42.3二叉排序树中元素的查找42.4二叉排序树中元素的删除52.5二叉排序树的平均查找长度52.6平衡二叉树（AVL）52.7中序输出平衡二叉树72.8在平衡二叉排序树上插入

2、一个新元素82.9在平衡二叉排序树上删除一个元素82.10求平衡二叉树的平均查找长度8三 详细设计9四 程序的调试与运行结果说明12五 课程设计总结13参考文献14一 概述1.1课程设计的目的1理解和掌握该课程中的有关基本概念，程序设计思想和方法。2培养综合运用所学知识独立完成课题的能力。3培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。5. 本课程是数据结构课程的实践环节。主要目的在于加强学生在课程中学习的相关算法和这

3、些方法的具体应用，使学生进一步掌握在C或其他语言中应用这些算法的能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。另外，数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。1.2课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基

4、本操作：以回车(n)为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树T是否为平衡二叉排序树；再用数列L,生成平衡二叉排序树BT:对平衡二叉树作中序遍历输出；当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；当删除元素之后，发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。二 总体方

5、案设计用二叉链表作存储结构实现二叉排序树：（1）以回车(0)为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）求二叉排序树的平均查找长度；（4）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。（5）判断二叉排序树是不是平衡二叉树；（6）以回车(0)为输入结束标志,输入数列L，生成一棵平衡二叉树T；（7）对平衡二叉树T作中序遍历，输出结果；（8）在平衡二叉树中插入新元素，并作中序输出；（9）在平衡二叉树中删除元素，并作中序输出；（10）求平衡二叉树的平均查找长度；2.1二叉排序树的建立

6、 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一

7、棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果b=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为： ASL(n,i)=1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)/

8、n其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出： 当n=2时，ASL(n)data=e;T-leftchild=T-rightchild=NULL;T-bf=EH; /此时平衡因子为0，EH等高。taller=TRUE; /树的深度增加else/树中存在和e有相同关键字的结点则不再插入if(e=T-dat

9、a)taller=FALSE;return NULL;/值小于则继续在树的左子树中搜索if(e data)p=InsertAVL(T-leftchild,e); /插入到左子树且左子树长高if(p)T-leftchild=p;if(taller)switch(T-bf)/检查*T的平衡度case LH:/原本左子树比右子树高，需要做左平衡处理T=LeftBalance(T);taller=FALSE;break;case EH:/原本左、右子树同高，现因左子树争高而使树增高T-bf=LH;taller=TRUE;break;case RH:/原本右子树比左子树高，现在左右子树等高T-bf=EH

10、;taller=FALSE;break;/继续在*T的右子树中搜索elsep=InsertAVL(T-rightchild,e);/插入到右子树且使右子树长高if (p)T-rightchild=p;if(taller)switch(T-bf)/检查*T的平衡度case LH:/原本左子树比右子树高，现在左右子树等高 T-bf=EH;taller=FALSE;break;case EH:/原本左、右子树同高，现因右子树增高而使树增高T-bf=RH;taller=TRUE;break;case RH:/原本右子树比左子树高，需要做右平衡处理T=RightBalance(T);taller=FAL

11、SE;break;return T;四 程序的调试与运行结果说明4.0运行的主菜单为： 如图4-0 主菜单输出所有功能界面 图4-04.1输入数列12、6、9、18、12、25、16生成二叉排序树： 如图4-1 输入数列生成二叉排序树 图4-14.2中序输出生成的二叉排序树： 如图4-2 将生成的二叉排序树中序输出 图4-24.3求二叉排序树的平均查找长度： 如图4-3 求生成的二叉排序树的ASL 图4-34.4判断是不是平衡二叉树： 如图4-4 通过检查平衡因子判断是不是平衡二叉树 图4-44.5删除元素6、9： 如图4-5 查找元素6、9，存在则删除并中序输出 图4-54.6删除元素6、9

12、后判断是不是平衡元素：如图4-6 删除元素6、9后，判断二叉排序树不是平衡二叉排序树 图4-6如图4-7 删除元素6、9后，平均查找长度为 图4-74.7输入数列13、24、37、90、24、53生成平衡二叉树：如图4-8 输入数列建立平衡二叉树 图4-84.8中序输出生成的平衡二叉树： 如图4-9 中序输出生成的平衡二叉树 图4-94.9在平衡二叉树中插入元素100，并中序输出： 如图4-10 在平衡二叉树中插入数据元素中100并中序输出 图4-10 4.10在平衡二叉树中删除元素24，并中序输出： 如图4-11 在平衡二叉树中删除数据元素53并中序输出 图4-114.11求当前平衡二叉树的

13、平均查找长度： 如图4-12 输出此时的平均查找长度ASL,输入0退出系统五 课程设计总结通过一周的课程设计，对计算机的应用，数据结构的作用以及C的使用都有了更深的了解。了解数据结构在今后学习的重要地位，包括在本学期所学习的数据库，也显示出其重要的地位。本次实验中利用的是数据结构中非线性结构树，对树的操作，基本都运用到递归函数，其逻辑性较强，某些功能函数的思想较复杂但其程序代码较简洁。二叉排序树主要运用在查找中，其构造的特殊性决定了其独有的功能。而平衡二叉树则是对二叉排序树的改进，优化其平均查找长度。理论学习和上机实践的各个环节中，通过自主学习和请教老师，我收获了不少。当然也遇到不少的问题，也

14、正是因为这些问题引发的思考给我带来了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。在这段时间里，我遇到过的问题主要就是C语言指针有些混淆，一些用法记不太清楚。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：各头文件的使用，定义变量时出现的问题，递归函数的运用等等。在实际的上机操作过程中，不仅是让我们了解数

15、据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实训可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。参考文献1 谭浩强，C程序设计题解与上机指导（第二版），北京，清华大学出版社，2000，9.2 雏凤，数据结构，大连理工大学出版社，2014,10.3 严蔚敏，吴伟明，数据结构（C语言版）M.北京:清华大学出版社，1997.4苏仕华,数据结构课程设计M.北京：机械工业出版社，2005.5杨晓光，数据结构实例教程M.北京：清华大学出版社，北京交通大学出版社，2008.6严蔚敏，吴伟明，米宁，数据结构习题集，北京：清华大学出版社，2016.4.7王红梅，数据结构（C+版）M.北京：清华大学出版社，2008.附上源代码： -第 1 页编 号：