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

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

1、数据结构课程设计课程名称：平衡二叉树的生成院系：信息工程学院年级专业：10级计科学号：0942151201学生姓名：指导教师：开题时间：2010年12月01日完成时间：2010年12月31日信息工程学院安徽新华学院数据结构课程设计成绩评定表院系：信息工程学院年级专业：学号：姓名：设计题目：成绩评定：摘要本篇论文系计科专业10年末课程设计论文，按照相应要求写作而成。主要讨论的是平衡二叉树的生成问题，借助本程序可以由用户输入数值，并生成平衡二叉树，并可以对数据进行方便的修改和删除添加，任意插入或删除一个结点后仍然要求任然构成平

2、衡二叉树，并按中序遍历输出这棵平衡二叉树。·本论文共由五个章构成，每个内容独立成章，各章下设相应子章节。各个章节逐渐递进，分别是：第一章：需求分析第二章系统设计第三章编码第四章测试第五章维护本论文特点：1.论述清楚，目录详尽，可以方便的查询相应章节，方便使用。2.图文结合，几乎没一个子程序模块都有相应的流程图与之对应，有利于读者理解每个子程序的设计思路。3.模块分化清晰，每个模块独立成节，又彼此联系，深化了C语言模块化编程的特点。4.测试模块配合对应的运行截图，真实可信，对读者理解程序的运行情况起到了很大作用。5.程序清单完

3、整详细，解释详细。目录第一章需求分析···················································11.1功能描述11.2数据词典1第二章系统设计···················································32.1基本概念介绍32.2总体设计82.3插入结点102.4删除结点112.5中序遍历11第三章编码·························································123.1总体编码123.

4、2总流程图153.3以指针T所指结点为根的二叉树作右平衡旋转处理16第四章测试·························································174.1创建二叉树测试174.2插入结点测试194.3删除结点测试204.4中序遍历结点测试214.5先序遍历测试21第五章维护························································225.1维护22第一章需求分析1.1功能描述平衡二叉树是数据结构中一个非常重要的概念。它对二叉

5、树的优化和提高查询效率有重要的作用，它是动态查找的一个非常重要方法，它在实际生产中有着广泛的应用。通过本程序的设计编写所要求达到的目的是：1.充分理解和掌握二叉树、平衡二叉树的相关概念和知识。2.掌握平衡二叉树的生成、结点删除、插入等操作过程。3.并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4.任意插入或删除一个结点后仍然要求构成平衡二叉树。5.按先序和中序遍历输出这棵平衡二叉树。1.2数据字典平衡因子任意结点左子树与右子树深度之差时间复杂度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能

6、知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。BST二叉排序树(BinarySortTree：BST)　　1、二叉排序树的定义　　二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：　　①若它的左子

7、树非空，则左子树上所有结点的值均小于根结点的值；　　②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；　　③左、右子树本身又各是一棵二叉排序树。AVL树AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（logn）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。结点包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。　　在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有

8、元素值的方框表示，一般称之为数据结点，简称结点。　　在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。　　数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点。第二章系统设计