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

《数据结构课程设计(论文)平衡二叉树的生成.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计(论文)平衡二叉树的生成.doc（46页珍藏版）》请在三一办公上搜索。

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

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

3、一章 需求分析11.1 功能描述11.2 数据词典1第二章 系统设计3 2.1 基本概念介绍3 2.2 总体设计8 2.3 插入结点10 2.4 删除结点11 2.5 中序遍历11第三章 编码123.1 总体编码123.2 总流程图153.3 以指针T所指结点为根的二叉树作右平衡旋转处理16第四章 测试174.1 创建二叉树测试174.2 插入结点测试194.3 删除结点测试204.4 中序遍历结点测试214.5 先序遍历测试21第五章 维护225.1 维护22第一章 需求分析1.1功能描述平衡二叉树是数据结构中一个非常重要的概念。它对二叉树的优化和提高查询效率有重要的作用，它是动态查找的一个

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

5、并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。BST 二叉排序树(Binary Sort Tree：BST) 1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。AVL树AVL树是最先发明的

6、自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。结点 包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。 在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。 在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。 数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储

7、存结点，也可简称结点。第二章 系统设计2.1 基本概念介绍树的概念树（Tree）是n（n=0）个结点的有限集。在任意一棵非空树中：1) 有且仅有一个特定的称为根的结点；2) 当n1时，其余结点可分为m（m0）个互不相交的有限集T1，T2.Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。【例】如图1-1所示：ABCEDFGH图1-1图1是有8个结点的树，其中A是根，其余结点分成2个子集：T1=B，D，T2=C，E，F，G，H；T1和T2都是根A的子树，且本身也是一棵树。平衡二叉树的概念形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ：若 T 是一

8、棵非空二叉树，其左、右子树分别为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当TL 、 TR 都是平衡二叉树； hl hr 1；时，则 T 是平衡二叉树。【例】如图1-2 所示：AAACBCBCBEFDDHG（a）平衡二叉树 （b）非平衡二叉树图1-2 平衡二叉树与非平衡二叉树相应地定义 hl hr 为二叉平衡树的平衡因子 。因此，平衡二叉树上所有结点的平衡因子可能是 -1 ， 0 ， 1 。若一棵二叉树上任一结点的平衡因子的绝对值都不大于 1 ，则该树是就平衡二叉树。遍历的概念遍历二叉树指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

9、动态平衡技术的概念Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。为了保证二叉排序树的高度为lgn，从而保证二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的平衡。使之既保持BST性质不变又保

10、证树的高度在任何情况下均为O(lgn)，从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。注意：1) 任一结点的左右子树的高度均相同，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。2) 平衡的二叉排序树指满足BST性质的平衡二叉树。3) AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。最小不平衡子树的概念以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规

11、律可归纳为下列四种情况：ABXXBA 图1-3（1）LL 型：新结点 X 插在 A 的左孩子的左子树里。调整方法见图1-3。图中以 B 为轴心，将 A 结点从 B 的右上方转到 B 的右下侧，使 A 成为 B 的右孩子。ABXBAX图（2）RR 型：新结点 X 插在 A 的右孩子的右子树里。调整方法见图 。图中以 B 为轴心，将 A 结点从 B 的左上方转到 B 的左下侧，使 A 成为 B 的左孩子。A图（3）LR 型：新结点 X 插在 A 的左孩子的右子树里。调整方法见图 。分为两步进行：第一步以 X 为轴心，将 B 从 X 的左上方转到 X 的左下侧，使 B 成为 X 的左孩子， X 成为

12、 A 的左孩子。第二步跟 LL 型一样处理 ( 应以 X 为轴心 ) 。图（4）RL 型：新结点 X 插在 A 的右孩子的左子树里。调整方法见图。分为两步进行：第一步以 X 为轴心，将 B 从 X 的右上方转到 X 的右下侧，使 B 成为 X 的右孩子， X 成为 A 的右孩子。第二步跟 RR 型一样处理 ( 应以 X 为轴心 ) 。2.2 总体设计我们希望由任何初始序列构成的二叉排序树都是AVL树。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的（其中N为结点数）。由此，它的平均查找长度也是和logN同数量级的。如何使构成的二叉排序树成为平衡树呢

13、？先看一个具体的例子（常见图4）。假设表中关键字序列为（10，24，30，88，53）。空树和1个结点10的树显然都是平衡的二叉树。在插入24之后依是平衡的，只是根结点的平衡因子BF由0变为1；在继续插入30之后，由于结点10的BF值由1变成2，由此出现不平衡现象。此时好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由10改成至24，扁担的两头就平衡了。由此，可以对树左一个向左逆时针“旋转”的操作，令结点24为根，而结点10为它的左子树，此时，结点10和24的平衡因子都为0，而且依保持二叉排序树的特性。在继续插入88和53之后，由于结点30的BF值由1变成2，排序树中出现了新的不平衡现象

14、，需要调整。当此时由于结点53插在结点88结点的左子树上，因此不能和上作简单调整。对于以结点30为根的子树来说，即要保持二叉排序树的特性，又要平衡，则必须以53作为根结点，而使37为它的左子树的根，88成为它的左子树的根。这好比对树作了两次“旋转”操作先向右顺时针，后向左逆时针（见图2-7（f）（h），使二叉排序树由不平衡转化为平衡。一般情况下，假设由于在二叉排序树上插入结点而失去平衡后进行调整的规律可归纳为最小不平衡子树的概念中提到的4中操作。图2-7 平衡二叉树的生成过程（a）空树；（b）插入10；（c）插入24；（d）插入37；（e）向左逆时针右旋转平衡；（f）相继插入90和53；（g）

15、第一次向右顺时针旋转；（h）第二次向左逆时针旋转平衡4种插入中，（1）和（3）对称，（2）和（4）对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小到大有序”证明之。当平衡二叉树因插入或者删除结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入或删除之前相同，因而不影响插入或删除路径上所有祖先结点的平衡。2.3 插入结点在平衡二叉排序树BBST上插入一个新数据元素e的递规算法可以描述如下：(1) 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增加1；(2) 若e的关键字和BBST的根结点的关

16、键字相等，则不进行插入；(3) 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况处理之：1. BBST的根结点的平衡因子为1（右子树深度大于左子树深度）：则将根结点的平衡因子更改为0，BBST的深度不变；2. BBST的根结点的平衡因子为0（左，右子树深度相等）：则将根结点的平衡因子更改为1，BBST的深度增加1；3. BBST的根结点的平衡因子为1（左子树深度大于右子树深度）：若BBST的左子树根结点的平衡因子为1，则需要进行单向右旋平衡处理，并且在右旋处理之后将

17、根结点和右子树根结点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为1，这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；(4) 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理。2.4 删除结点删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树-找到要删除的结点-删除一个结点-变成二叉树-旋转-变回平衡二叉树。具体过程将详细设计中的代码。2.5 中序遍历右遍历的定义可知

18、，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则1) 中序遍历左子树2) 访问根结点3) 中序遍历右子树如中序遍历图2-8的二叉树，结点的访问顺序为：abcdefg图2-8第三章 编码3.1 总体编码A. 使用的头文件#include #include B. 常量定义# define LH 1/*左高*/# define EH 0/*等高*/# define RH -1/*右高*/# define TRUE 1# define FALSE 0C. 全局变量定义int taller=0;/*taller反映T长高与否*/int shorter=0;/*shorter反映T变矮与

19、否*/D. 数据结构定义/*根据平衡二叉树特点可以定义平衡二叉树的存储结构*/*二叉排序树的类型定义*/typedef struct BSTNode int data;/*结点值*/int bf;/*结点的平衡因子*/struct BSTNode * lchild, * rchild;/*分别指向左右孩子的指针*/BSTNode, *BSTree;/*同时声明一个BSTNode和一个指针类型的*BSTree*/E. 部分关键函数原型说明void MidOrder(BSTree T)/*树的中序遍历的递归算法,一并输出它的平衡因子和左右结点值，不返回值*/BSTree R_Rotate(BSTr

20、ee p)/*对以p为根的二叉排序树作右旋处理，处理之p指向新的树根结点即旋转处理之前的左子树根结点*/BSTree L_Rotate(BSTree p) /*对以p为根的二叉排序树作左旋处理，处理之p指向新的树根结点即旋转处理之前的右子树根结点*/BSTree LeftBalance(BSTree T)/*对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree RightBalance(BSTree T)/*对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree InsertAVL(BSTree T, int

21、 e)/*向平衡树中插入一个结点，返回插入后的新根结点*/BSTree LeftBalance1(BSTree p)/*删除结点时对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree RightBalance1(BSTree p) /*删除结点时对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree Delete(BSTree q, BSTree r) /*对结点进行删除处理，本算法结束时指针q指向新的根结点*/BSTree DeleteAVL(BSTree p, int e) /*找到要删除的结点,并调用删

22、除函数对其进行删除，本算法结束时指针p指向新的根结点*/BSTree CreatNode(int nodeValue) /*建立关键字值为nodeValue的新结点，返回根结点*/3.2 总流程图开始输入e eBuildTreeDeleteAVLMidOrderRootOrderexitBreak结束e=n,n=(1,2,3,4,5)e=1e=5e=2e=4e=3InsertAVL进入功能选择界面，用户按照提示输入相应选择项数值，选择后程序根据用户的输入调用相应函数3.3 以指针T所指结点为根的二叉树作右平衡旋转处理T-bf=rc-bf=EHL_Rotate开始rc=T-rchildrc-bf

23、ld=rc-lchildld-bfbf=LHT-bf=LHrc-bf=EHT-bf=rc-bf=EHT-bf=EHrc-bf=RHld-bf=EHR_RotateL_Rotatereturn T bf=RHbf=RHbf=EH其他旋转类推第四章 测试4.1 创建平衡二叉树测试第一步：选择1，如图4-1第二步：输入序列（10，24，30，88，53）创建一刻二叉平衡树，以0为结尾，如图4-2图4-1图4-2第三步：为查看创建结果，我们选择5，先序输出二叉树，如图4-3图4-34.2 插入结点测试第一步：选择2，插入一个新结点，其值为7，插入后选择5，第二步：先序输出该树：4.3 删除结点测试第一

24、步：选择3删除一个结点，这里删除结点7第二步：先序输出该树：4.4 中序遍历二叉树第一步：输入4，中序遍历二叉树：4.5先序遍历二叉树第一步：输入5，先序遍历二叉树：第五章 维护通过平衡二叉树的生成程序的设计，我们很好的理解了平衡二叉树的生成和各项操作的相关知识，同时还较好的掌握了动态查找相关概念。4、程序调试与体会平衡二叉树的生成是数据结构中一个重要的存储结构。由于本程序的输入较多，所以输入数据时必须小心细致。本程序比较复杂，需要使用结构体并使用了指针。必须将程序分解为多个子程序以降低编写难度。适当使用全局常量可以控制有效控制内存溢出。由于程序较大，调试不容易易找出程序中的隐藏错误，测试时候

25、没有发现错误，隐藏的难以发现。编写过程中发现很多困难，都是查找参考书查找解决方法，在后来程序运行过程中应多结合相应参考书，查找问题，便于后期维护。附录：【1】本论文写作期间参考了大量书籍资料，由于时间限制和水平的限制，难免有错误和不尽如人意的地方，希望老师指正，帮助我水平的提高，特此感谢【2】参考书目1 数据结构 黄刘生 高等教育出版社2 C语言程序设计 谭浩强（第二版） 清华大学出版社 3 C primer plus（第四版）中文版 人民邮电出版社 【3】程序清单：#include #include # define LH 1/*左高*/# define EH 0/*等高*/# define

26、 RH -1/*右高*/# define TRUE 1# define FALSE 0int taller=0;/*taller反映T长高与否*/int shorter=0;/*shorter反映T变矮与否*/*二叉排序树的类型定义*/typedef struct BSTNode int data;/*结点值*/int bf;/*结点的平衡因子*/struct BSTNode * lchild, * rchild;/*分别指向左右孩子的指针*/BSTNode, *BSTree;/*同时声明一个BSTNode和一个指针类型的*BSTree*/*树的中序遍历的递归算法,一并输出它的平衡因子和左右结

27、点值*/void MidOrder(BSTree T) /*中序遍历的特点是：当二叉树为空，则空操作；否则*/*1.中序遍历左子树；*/*2.访问根结点；*/*3.中序遍历右子树。*/if(T-lchild) MidOrder(T-lchild); if(T-data) /*以适当的形式格式化输出各个结点及其附加信息可以方便用户重构二叉树*/printf( %d %d,T-data,T-bf);if (T-lchild ) printf( %d,T-lchild-data); else printf( -);if (T-rchild ) printf( %d,T-rchild-data); e

28、lse printf( -);printf(n);if(T-rchild) MidOrder(T-rchild); /*树的先序遍历的递归算法,一并输出它的平衡因子和左右结点值*/void RootOrder(BSTree T) /*先序遍历的特点是：当二叉树为空，则空操作；否则*/*1.访问根结点；*/*2.先序遍历左子树；*/*3.先序遍历右子树。*/if(T-data) printf( %d %d,T-data,T-bf);if (T-lchild ) printf( %d,T-lchild-data); else printf( -);if (T-rchild ) printf( %d

29、,T-rchild-data); else printf( -);printf(n);if(T-lchild) RootOrder(T-lchild); if(T-rchild) RootOrder(T-rchild); /*对以p为根的树作右旋处理，处理之p指向新的树根结点即旋转处理之前的左子树根结点*/BSTree R_Rotate(BSTree p)BSTNode *lc;/*声明BSTNode* 临时变量*/lc=p-lchild;/*lc指向的*p的左子树根结点*/p-lchild=lc-rchild;/*lc的右子树挂接为*p的左子树*/lc-rchild=p;p=lc;/*p指向

30、新的根结点*/return p;/*返回新的根结点*/*对以p为根的树作左旋处理，处理之p指向新的树根结点即旋转处理之前的右子树根结点*/BSTree L_Rotate(BSTree p) BSTNode *rc;/*声明BSTNode* 临时变量*/rc=p-rchild;/*rc指向的*p的右子树根结点*/p-rchild=rc-lchild;/*rc的左子树挂接为*p的右子树*/rc-lchild=p;p=rc;/*p指向新的根结点*/return p;/*返回新的根结点*/*对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree LeftBal

31、ance(BSTree T) BSTNode *lc,*rd;lc=T-lchild;/*lc指向*T的左子树根结点*/switch(lc-bf)/*检查*T的左子树平衡度，并做相应的平衡处理*/case LH:/*新结点插入在*T的左孩子的左子树上，要做单右旋处理*/T-bf=lc-bf=EH;T=R_Rotate(T);break;case RH:/*新结点插入在*T的左孩子的右子树上，要做双旋处理*/rd=lc-rchild;/*rd指向*T的左孩子的右子树根*/switch(rd-bf)/*修改*T及其左孩子的平衡因子*/case LH:T-bf=RH;lc-bf=EH;break;c

32、ase EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;T-lchild=L_Rotate(T-lchild);/*对*T的左孩子做左旋平衡处理*/T=R_Rotate(T);/*对*T做右旋处理*/return T;/*对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根结点*/BSTree RightBalance(BSTree T) BSTree rc,ld;rc=T-rchild;/*rc指向*T的右子树根结点*/switch(rc-bf)/*检查*T的右子树平衡度，并做相应的平衡处理

33、*/case RH:/*新结点插入在*T的右孩子的右子树上，要做单右旋处理*/T-bf=rc-bf=EH;T=L_Rotate(T);break;case LH:/*新结点插入在*T的右孩子的左子树上，要做双旋处理*/ld=rc-lchild;/*ld指向*T的右孩子的左子树根*/switch(ld-bf)/*修改*T及其右孩子的平衡因子*/case LH:T-bf=LH;rc-bf=EH;break;case EH:T-bf=rc-bf=EH;break;case RH:T-bf=EH;rc-bf=RH;break;ld-bf=EH;T-rchild=R_Rotate(T-rchild);/

34、*对*T的右孩子做右旋平衡处理*/T=L_Rotate(T);/*对*T做左旋处理*/return T;/*若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个数据元素为e的新结点,并返回插入后所建成的平衡二叉排序树,否则返回NULL.若因插入而使二叉数失去平衡,则作平衡旋转处理,布尔变量taller反映T长高与否*/BSTree InsertAVL(BSTree T, int e) BSTree p;/*插入新结点，树长高置taller为TRUE*/if(!T)T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-lchild=T-rchild=

35、NULL;T-bf=EH;taller=TRUE;else/*树中存在和e有相同关键字的结点则不再插入*/if(e=T-data)taller=FALSE;return NULL;/*值小于则继续在树的左子树中搜索*/if(e data)p=InsertAVL(T-lchild,e); /*插入到左子树且左子树长高*/if(p)T-lchild=p;if(taller)switch(T-bf)/*检查*T的平衡度*/case LH:/*原本左子树比右子树高，需要做左平衡处理*/T=LeftBalance(T);taller=FALSE;break;case EH:/*原本左、右子树同高，现因左

36、子树争高而使树增高*/T-bf=LH;taller=TRUE;break;case RH:/*原本右子树比左子树高，现在左右子树等高*/T-bf=EH;taller=FALSE;break;/*继续在*T的右子树中搜索*/else/*插入到右子树且使右子树长高*/p=InsertAVL(T-rchild,e);if (p)T-rchild=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:/*原本右子树比左子树高