数据结构课程设计--平衡二叉树的生成

《数据结构课程设计--平衡二叉树的生成》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计课程名称:《数据结构》课程代码:题目:平衡二叉树的生成年级/专业/班:04级计算机科学与技术专业计算机本科三班学生姓名:王伟学号:04356320指导教师:羊四清开题时间:2007年6月10日完成时间:2007年6月22日-26-数据结构课程设计目录摘要………………………………………………………………………………………………1一、引言…………………………………………………………………………………………2二、设计任务与目的……………………………………………………………………………2三、设计方案与实施……………………………………………………………………………21、总体设计…

2、………………………………………………………………………………2l基本概念（包括设计到的概念）A.树的概念B.平衡二叉树的概念C.遍历的概念D.动态平衡技术的概念E.最小不平衡子树的概念l构造算法l插入结点l删除结点l中序遍历2、详细设计…………………………………………………………………………………8A.使用的头文件B.常量定义C.全局变量定义D.数据结构定义E.部分关键函数原型说明3、程序清单…………………………………………………………………………………104、程序调试与体会…………………………………………………………………………235、运行结果（截图）…………………………………………

3、……………………………23四、结论………………………………………………………………………………………24五、参考文献…………………………………………………………………………………24-26-数据结构课程设计摘要树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。树型结构在客观世界中广泛存在。而平衡二叉树因其特性，它在查找时拥有比普通二叉树更高的效率，所以它拥有很广泛的应用。关键词：二叉树，平衡二叉树，查找AbstractThetreestructureisdefinedwiththebranchrelationoflayerstructure,itisaimportantno

4、nlinearstructure.Thetreestructureisanextensiveexistenceintheobjectiveworld.Andbecauseofitscharacteristic,itownshigherefficiencythangeneralbinarytreewhileinsearching,soitisusedextensively.Keywords:BinaryTree,BalancedBinaryTree,Search-26-数据结构课程设计《数据结构》课程设计--平衡二叉树的生成设计一、引言平衡二叉树是数据结构中一个非常重要的概念。它对二叉树

5、的优化和提高查询效率有重要的作用，它是动态查找的一个非常重要方法，它在实际生产中有着广泛的应用。二、设计目的与任务通过本课程设计教学所要求达到的目的是：充分理解和掌握二叉树、平衡二叉树的相关概念和知识。掌握平衡二叉树的生成、结点删除、插入等操作过程，并编程实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树，任意插入或删除一个结点后仍然要求构成平衡二叉树，并按中序遍历输出这棵平衡二叉树。三、设计方案与实施1、总体设计l基本概念（包括设计到的概念）树的概念树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：1)有且仅有一个特定的称为根的结点；2)当n>1时，其余结点可分为

6、m（m>0）个互不相交的有限集T1，T2......Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。【例】如图1所示：图1图1是有8个结点的树，其中A是根，其余结点分成2个互不相交的子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子树，且本身也是一棵树。-26-数据结构课程设计平衡二叉树的概念形态匀称的二叉树称为平衡二叉树(Balancedbinarytree)，其严格定义是：　　若T是一棵非空二叉树，其左、右子树为TL和TR，令hl和hr分别为左、右子树的深度。当且仅当　　　①TL、TR都是平衡二叉树；　　　②｜hl－hr｜≤1；时，则T

7、是平衡二叉树。【例】如图2所示：（a）平衡二叉树（b）非平衡二叉树图2平衡二叉树与非平衡二叉树相应地定义hl－hr为二叉平衡树的平衡因子(balancefactor)。因此，平衡二叉树上所有结点的平衡因子可能是-1，0，1。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于1，则该树是就平衡二叉树。遍历的概念遍历二叉树指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。由二叉树的递规定义可知，二叉树的3个基本单