DS课程设计报告--平衡二叉树

《DS课程设计报告--平衡二叉树》由会员分享，可在线阅读，更多相关《DS课程设计报告--平衡二叉树（17页珍藏版）》请在毕设资料网上搜索。

1、 1 一题目与要求一题目与要求 1.1.问题提出问题提出 编写已个平衡二叉树， 主要是对插入一个元素导致树不平衡的情况进处平衡化处 理以及相关的处理。 2.2.本系统涉及的知识点本系统涉及的知识点 队列的插入，删除，二叉树的建立于销毁，平衡树的平衡化，以及 C 语言中基 础应用于结构等。 3.3.功能要求功能要求 (1).通过不断插入的方式创建一棵平衡二叉树，包括输入结点的关键字和相关 信息。 (2)按要求输出创建的平衡二叉树结点，包括 顺序（中序）输出和按层次输出。 (3)插入新增的结点，若结点不存在则插入平衡二叉树，并进行相关调整。 (4)销毁二叉树。 (5)退出 二二功能设计功能设计 1

2、.1.数据结构的定义数据结构的定义 typedef struct ElemType KeyType Key; /键值类型 char info20; ElemType; Typedef struct BSTNode ElemType data； int bf ; /结点的平衡因子 struct BSTNode *lchild，*rchild；/左右孩子指针 BSTNode，*BSTree； 2.2.模块图模块图 1.主程序的流程 2 请输入操作的选项编号（1-5） 1-创建平衡二叉树 2-查找 3-插入 4-删除 5-结束 2.各模块之间的层次调用 三三. .程序代码设计程序代码设计 1.1.调

3、平二叉树调平二叉树 if(插入元素与当前根元素相等) printf(“已存在相同关键字的结点n“); if(插入元素小于当前根元素) if(插入新结点不成功) return 0; if(插入成功) switch(查看根的平衡因子) case +1: 进行左平衡处理; 检查*T的左子树的平衡度，并作相应平衡处理 case +1: 令根及其左孩子的平衡因子为0; 做右平衡处理; 主模块 平衡化 输入数据 元素 显示主菜 单 查找 插入 删除 输出 退 出 3 BTree lc; lc指向的结点左子树根结点; rc的右子树挂接为结点的左子树; lc的右孩子为原结点; 原结点指向新的结点lc; bre

4、ak; case -1: rd指向*T的左孩子的右子树根 switch(查看右孩子平衡因子) case +1: 根的平衡因子为-1; 根左孩子的平衡因子为0; break; case 0: 令根和根左孩子的平衡因子为0; break; case -1: 根平衡因子为0; 根左孩子平衡因子为1; break; 根右孩子的平衡因子为0; 对*T的左子树作左旋平衡处理; 对*T作右旋平衡处理; break; case 0: 令根的平衡因子为+1; break; case -1: 令根的平衡因子为-1; break; 2.输出：输出： （1）中序输出 采用递归算法对二叉树进行遍历。 if（结点不为空）

5、 If(遍历左孩子成功） If（遍历结点成功） If（遍历右孩子成功） 返回 真 返回假 4 else（结点为空） 返回假 (2)按层次输出 根据队列先进先出的特点，先将第一层结点进队 a，对其出出队并输出，同 时将其不为空的孩子指针入另一队列 b， 当 a 为空时， 队 b 进行出对并输出处理， 将结点的不为空的左右孩子入队 a， 直到 b 为空如此直到两队均为 空。 根节点入队； While（a，b 不同时为空） If（i 为奇数） While（a 队不空） a 中结点出队并输出； If（左孩子不空） 左孩子入队 b； If(有孩子不空） 右孩子入队 b； If（i 为偶数） While（b 队不空） b 中结点出队并输出； If（左孩子不空） 左孩子入队 a； If(有孩子不空） 右孩子入队 a； I+;/ 同时记录树的深度 3 3. .销毁二叉树销毁二叉树 销毁二叉树的算法根据递归遍历而来，算法大体相识。 If(根节点不空） If（左子树不空） 销毁左子树； 5 If（右子树不空） 销毁右子树； 销毁相对根节点； 根节点赋空；/留下来以便再次创建二叉树时使用 4.4.退出退出 退出时询问是否确认退出，确认则退出，否则返回到主菜单 四四调试分析调试分析 1.遇到的问题： 1）对平衡二叉树的删除的算法设计程序