二叉排序树与平衡二叉树的实现课程设计.docx

《二叉排序树与平衡二叉树的实现课程设计.docx》由会员分享，可在线阅读，更多相关《二叉排序树与平衡二叉树的实现课程设计.docx（20页珍藏版）》请在三一办公上搜索。

1、攀枝花学院本科学生课程设计任务书题目二叉排序树与平衡二叉树的实现1、课程设计的目的1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）1)（1）以回车（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）计算二叉排序树T查找成功的平均查找长度，输出结果；（4

2、）输入元素x,查找二叉排序树T,若存在含x的结点，则删该结点，并作中序遍历（执行操作2）；否则输出信息“无x”；（5）用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；（6）计算平衡的二叉排序树BT的平均查找长度，输出结果。3、主要参考文献1 刘大有等，数据结构（C语言版），高等教育出版社2 严蔚敏等，数据结构（C语言版），清华大学出版社3 William Ford， William Topp,Data Structure with C+清华大学出版社4 苏仕华等，数据结构课程设计，机械工业出版社4、课

3、程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分析和结果第5天课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）:接受任务时间：年 月 日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称一叉排序树与平衡一叉树的实现评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学 工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠 道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。台户 能 力 水平 35%04综合运用知识的能力

4、10能运用所学知识和技能去发现与解决实际问题， 能正确处理实验数据，能对课题进行理论分析， 得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并 较好地论述课题的实施方案；有收集、加工各种 信息及获取新知识的能力。06设计（实验）能力，方案 的设计能力5能正确设计实验方案，独立进行装置安装、调试、 操作等实验工作，数据正确、可靠；研究思路清 晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机 进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析 能力（综合分析能力、技 术经济分析能力）10具有较强的数据收集、分析、处理、综合的

5、能力。成果质量45%09插图（或图纸）质量、篇 幅、设计（论文）规范化 程度5符合本专业相关规范或规定要求；规范化符合本 文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分， 结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名：年 月曰摘要及关键字本程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排 序树”。二叉排序树（又称二叉查找树）：（1）若左子树不空，则左子树上所有节点的 值均小于它的根结点的值；（2）若右子树不空，则右子树上所有节点均大于它的 根结点的值；（3）它的左右子

6、树分别为二叉排序树。二叉平衡树：若不是空树，收1）左右子树都是平衡二叉树；（2）左右子树的 深度之差的绝对值不超过1。本次实验是利用二叉排序树和平衡二叉树达到以下目的：（1）以回车（n） 为输入结束标志，输入数列L，生成一棵二叉排序树T； （2）对二叉排序树T作中 序遍历，输出结果；（3）计算二叉排序树T查找成功的平均查找长度，输出结果；（4）输入元素x,查找二叉排序树T,若存在含x的结点，则删该结点，并作中序遍历 （执行操作2）；否则输出信息“无x”；（5）用数列L，生成平衡的二叉排序树BT: 当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即 将它转换成新的平衡的二叉排

7、序树BT； （6）计算平衡的二叉排序树BT的平均查 找长度，输出结果。关键字：数列L,结点,二叉排序树,平衡二叉树目录摘要 31绪论 51.1课程设计的目的 51.2相关知识的阐述 51.2.1 一位数组的存储结构 51.2.2建立二叉排序树 51.2.3中序遍历二叉树 51.2.4平均查找长度 61.2.5平均二叉树（AVL树）61.2.6平衡因子71.2.7平衡二叉树的调整方法 72方案设计82.1模块功能83算法设计 83.1算法流程图84详细设计104.1主程序 104.2定义二叉树结构 114.3建立二叉树114.3.1二叉排序树的查找114.3.2二叉排序树的插入114.4中序遍历

8、 124.5平均查找长度 124.6删除节点 124.7判断平衡二叉树135调试分析145.1时间复杂度的分析145.2运行结果 145.3结果分析 156课程设计总结16参考文献 171绪论1.1课程设计的目的（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结 构、存储结构和操作实现算法，以及它们在程序中的使用方法。（2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软 件设计的能力。（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设 计的基本能力。1.2相关知识的阐述1.2.1 一维数组的存储结构建立二插排序树，首先用一个一维数组记录下读入的

9、数据，然后再用边查找边 插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0”补 齐。1.2.2建立二叉排序树二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成 的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行 插入。新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时 查找路径上访问的最后一个结点的左孩子或右孩子结点。插入算法：首先执行查找算法，找出被插结点的父亲结点；判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点 插入；若二叉树为空，则首先单独生成根结点。注意：新插入的结点总是叶子结点。1.2.3中序遍历二叉树中序遍历二叉树算法

10、的框架是：若二叉树为空，则空操作；否则（1）中序遍历左子树（L）；访问根结点（V）；中序遍历右子树（R）。中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i, 最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。 1.2.4平均查找长度计算二叉排序树的平均查找长度时，采用类似中序遍历的递归方式，用s记录 总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得 到总查找长度，。平均查找长度就等于s/i(i为树中结点的总个数)。假设在含有n(n=1)个关键字的序列中，i个关键字小于第一个关键字， n-i-1个关键字大于第一个关键字，则由

11、此构造而得的二叉排序树在n个记录的查 找概率相等的情况下，其平均查找长度为：ASL(n,i)=1+i*(P(i)+1) + (n-i-1)(P(n-i-1)+1)/n其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左 子树中每个关键字时所用比较次数的平均值，P(n-i-1)+1为查找右子树中每个 关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即 任一个关键字在序列中将是第1个，或第2个，或第n个的概率相同，则可对 上式从i等于0至n-1取平均值。最终会推导出：当 n=2 时，ASL(n)=2(1 + 1/n)ln(n)由此可见，在随机的情况下，

12、二叉排序树的平均查找长度和log (n)是等数 量级的。另外，含有n个结点的二叉排序树其判定树不是惟一的。对于含有同样一组结 点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能 不同。而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关： 在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生 成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和 单链表上的顺序查找相同，亦是(n+1)/2。 在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得 到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度 大约是lg

13、n。 插入、删除和查找算法的时间复杂度均为O(lgn)。1.2.5平衡二叉树(AVL树) 平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高 度大致相同。 任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全 平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。 平衡的二叉排序树指满足BST性质的平衡二叉树。 AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最 坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树高度约 为lgn，AVL树是最接近最优的。1.2.6平衡因子二叉树上任一结点的左子树深度减去右子树

14、的深度称为该结点的平衡因 子，易知平衡二叉树中所有结点的因子只可能为0，-1和1。平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0， 在平衡因子绝对值为2时，二叉排序树会出现四种不同的情况的树形，因此这时 需要分别单独讨论来降低平衡因子。1.2.7平衡二叉树的调整方法平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时， 首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出 其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平 衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子 树。具体步骤如下：(1) 每当插入一个新结点，从该结点开

15、始向上计算各结点的平衡因子，即计 算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对 值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；(2) 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；(3) 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型 的调整；(4) 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如 果出现冲突，应用旋转优先原则调整冲突；如果是 LR型或LR型，则需应 用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入 结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现

16、冲突，应用旋转优先原则调整冲突；(5) 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破 坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大 于1的结点。2方案设计2.1模块功能1. 建立二叉树：要求以回车(n)为输入结束标志，输入数列L,生成一棵 二叉排序树T。2. 中序遍历并输出结果：要求将第一步建立的二叉树进行中序遍历，并将结 果输出。3. 平均查找长度并输出：要求计算二叉排序树T查找成功的平均查找长度, 输出结果。4. 删除节点：要求输入元素x,查找二叉排序树T,若存在含x的结点，则删该 结点,并作中序遍历(执行操作2)；否则输出信息“无x”。5. 生成平衡

17、二叉树：要求用数列L，生成平衡的二叉排序树BT:当插入新元 素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成 新的平衡的二叉排序树BT；6. 平均查找长度：计算平衡的二叉排序树BT的平均查找长度，输出结果。3算法设计3.1算法流程图建立二叉树流程图:主程序流程图:中序遍历流程图：F、开始*调用遍历函数。利用递归算 法，输出中序遍历结果遍历结束删除节点流程图:4详细设计4.1主程序void main()node T=NULL;int num;int s=0,j=0,i=0;int ch=0;node p=NULL;printf(-请输入一组数字并输入0为结束符:)；dosc

18、anf(%d,&num);if(!num) printf(你成功完成了输入!n);else insertBST(&T,num);while(num);printf(nn-操作菜单-n);printf(n 0: 退出);printf(n 1:中序遍历)；printf(n 2:平均查找长度)；printf(n 3:删除);printf(n 4:判断是否是平衡二叉树)；while(ch=ch)printf(n选择操作并继续:)；scanf(%d,&ch);switch(ch)case 0: exit(0); /*0退出 */case 1: printf(中序遍历结果是:n);inorderTrave

19、rse(&T);break;case 2:s=0;j=0;i=0;calculateASL(&T,&s,&j,i);printf( ASL=%d/%d,s,j); break;case 3: printf(请输入你想删除的数字:，scanf(%d,&num);if(searchBST(T,num,NULL,&p)T=Delete(T,num);printf(你已成功删除该数字!n);inorderTraverse(&T);else printf(没有你想要删除的节点d!,num);break;case 4:i=0;balanceBST(T,&i);if(i=0) printf(OK!这是平衡二

20、叉树!)；else printf( NO!);break;default: printf(你的输入有误!请重新输入!n);break;4.2定义二叉树结构#includetypedef struct Tnodeint data;struct Tnode *lchild,*rchild;*node,BSTnode;4.3建立二叉树4.3.1二叉排序树的查找searchBST(node t,int key,node f,node *p)/*在根指针t所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 成功，则指针p指向该数据元素节点，并返回(1)，否则指针p指向查找路径上访 问的最后一

21、个节点并返回(0)，指针f指向七的双亲，其初始调用值为NULL*/ if(!t) *p=f;return (0);/* 查找不成功 */else if(key=t-data) *p=t;return (1); /* 查找成功*/else if(keydata) searchBST(t-lchild,key,t,p); /* 在左子树中继续查找 */else searchBST(t-rchild,key,t,p); /* 在右子树中继续查找 */4.3.2二叉排序树的插入insertBST(node *t,int key)/*当二叉排序树t中不存在关键字等于key的数据元素时，插入key并返回(

22、1)， 否则返回(0)*/node p=NULL,s=NULL;if(!searchBST(*t,key,NULL,&p) /*查找不成功 */ s=(node)malloc(sizeof(BSTnode);s-data=key;s-lchild=s-rchild=NULL;if(!p) *t=s;/*被插入节点*s为新的根节点*/else if(keydata)p-lchild=s; /*被插节点*、为左孩子*/else p-rchild=s; /*被插节点*、为右孩子*/return (1);else return (0); /*树中已有关键字相同的节点，不再插入*/4.4中序遍历inor

23、derTraverse(node *t) /* 中序遍历*/ if(*t)if(inorderTraverse(&(*t)-lchild) printf(%d ,(*t)-data);if(inorderTraverse(&(*t)-rchild); else return(1);4.5平均查找长度calculateASL(node *t,int *s,int *j,int i) /* 计算平均查找长度 */if(*t) i+; *s=*s+i;if(calculateASL(&(*t)-lchild,s,j,i) (*j)+;if(calculateASL(&(*t)-rchild,s,j,

24、i)i-; return(1); else return(1);4.6删除节点node Delete(node t,int key) /*若二叉排序树t中存在关键字等于key的数据元素时，则删除该数据元素节点 */node p=t,q=NULL,s,f;while(p!=NULL) if(p-data=key) break;q=p;if(p-datakey) p=p-lchild;else p=p-rchild;if(p=NULL) return t;if(p-lchild=NULL) if(q=NULL) t=p-rchild;else if(q-lchild=p) q-lchild=p-r

25、child;else q-rchild=p-rchild;free(p);else f=p;s=p-lchild;while(s-rchild) f=s;s=s-rchild; if(f=p) f-lchild=s-lchild;else f-rchild=s-lchild;p-data=s-data;free (s); return t;4.7判断平衡二叉树int balanceBST(node t,int *i) /* 判断平衡二叉树 */ int dep1,dep2;if(!t) return(0);else dep1=balanceBST(t-lchild,i);dep2=balanc

26、eBST(t-rchild,i);if(dep1-dep2)1|(dep1-dep2)dep2) return(dep1+1);else return(dep2+1); 5调试分析5.1时间复杂度的分析为了保证二叉排序树的高度为lgn,从而保证然二叉排序树上实现的插入、 删除和查找等基本操作的时间复杂度为O(lgn)。5.2运行结果图5.1. 1调试界面在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料 和同学的帮助下，发现程序未对数组初始化。添加数组初始化代码：s=(node)malloc(sizeof(BSTnode)输入一组数列，以结0结束：应C:Documents a

27、nd Settings睫dmini此namr、皇面委曲蜻帽课程设计Debug1请瑜入一缉数字并输入自为结束符” 7 M 9 5 0谖成功完成了 At 一操作菜单一一中序遍用幸均查技长度，胴除-k晰是否是平衡二叉树 选择操作并继续：职退出1234图5.2.2运行界面一中序遍历:中序遍居结果是:2 5 7 9 11选择操作并继续:图5.2.3运行界面计算平均查找长度选择操作并继续空fiSL=13/5选择操作并继续；图5.2.4运行界面三删除已有结点:卷勰牒产”2 5 7 9图5.2.5运行界面四删除失败:彳大你想删除的数谷押 胃你想蚩剧除的节点28!图5.2.6运行界面五判断是否是平衡二叉树：选择

28、操作并继续再图5.2.7运行界面六5.3结果分析通过运行程序和严密的求证，运行结果无误，不过对于转换平衡二叉树和平 衡二叉树平均查找长度未能实现，同时也无法实现图像显示。6课程设计总结在这一周的课程设计中，其实对我来说还是收获颇多。这不光提高了我的程 序设计能力，更为我的就业增加了筹码。对我们来说，独立完成这样课程设计是 比较困难，其中包括模块的组成分析和模块功能的实现。最后我不得不从网上下 载源程序，借助课本，困难地将几个模块串起来。最后终于完成了自己的课程设 计。这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写 程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理

29、解的模糊不 清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构， 而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错 误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时 我也发现两者在很多函数上是互通的，只需稍作修改即可移植。另外程序的不足之处是不能实现对0这个数字的存储，可以通过改变数字的 存储结构方式来实现，如使用二叉链表来作为数据的存储结构，即可实现该功能。 还有就是可能自己学的还不够，对于最后两个要求未能完成，不得不说这是自己 学艺不精。现在觉得以前我对数据结构的认识是那么的肤浅，因此我下定决心寒假一 定好好的把数据结构复习一遍。而且本次课程设计不光增强了我程序调试的能 力，还有在面对一个较大的程序要冷静，不要浮躁，先分析模块要实现的功能， 再把模块划分，最后到一个一个得模块实现，并且要不断地练习，这样，一个大 的程序对我来说将不成问题。参考文献1 刘大有等，数据结构（C语言版），高等教育出版社2 严蔚敏等，数据结构（C语言版），清华大学出版社3 William Ford, William Topp,Data Structure with C+清华大学出版社4 苏仕华等，数据结构课程设计，机械工业出版社