《数据结构平衡二叉树课设报告》由会员分享，可在线阅读，更多相关《数据结构平衡二叉树课设报告（24页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告课程设计名称：数据结构课程设计 课程设计题目：平衡二叉树的构建算法院（系）;专业班级学号姓名指导教师装订时：此页为任务书目录第1章 概要设计 71.1题目的内容与要求 71.2总体结构 7第2章 详细设计 82.1主模块 82.2输入模块 92.3平衡化模块 92.4输出模块 11第3章 调试分析 124.1. 遇到的问题： 124.2.收获： 12第4章 使用说明 13参考文献 15附录 15第 1 章 概要设计1.1 题目的内容与要求内容：从键盘输入一个关键字（整数）序列，关键字之间以空格作为 分隔符，然后根据这个序列构建一个平衡二叉树。要求:1. 要求利用二叉链表作为平衡二叉
2、树的存储结构；2. 独立完成系统的设计，编码和调试；3. 系统利用 C 语言实现；4.按照课程设计规范书写课程设计报告。1.2 总体结构本程序主要分为三个模块：输入模块，平衡化模块和输出模块。输入模块： 按题目要求从键盘输入一个关键字（整数）序列，关键字之间以空格作为分隔符。 平衡化模块:当左右子树高度差大于 1 时，对二叉树进行旋转平衡处理。输出模块 根据输入的关键字序列和平衡旋转处理，将平衡二叉树以树状图的形式输出。第 2 章 详细设计2.1 主模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块。主模块中提供一个可以输入的选择菜单，通过从键盘输入 1 或 2 来实现各项功
3、能 流程图如图 2.1 所示：2.2 输入模块从键盘输入一个关键字（整数）序列，关键字之间以空格作为分隔符，流 程图如图 2.2 所示。图 2.22.3 平衡化模块当二叉树的左右子树高度差大于 1 时，应该对二叉树进行相应的旋转平衡处理，以维持二叉树平衡，以右平衡旋转处理为例。流程图如图 2.3 所示：hildrc-bfHld-bf开始bf=LHT-bf=EH rc-bf=RHR_RotateL RotateT-bf=LH rc-bf=EHld=rc-lchildT-bf=rc-bf=EHT-bf=rc-bf=Ereturn TL_Rotateld-bf=EHrc=T-rc图 2.32.4 输
4、出模块根据输入的关键字序列和平衡旋转处理，将平衡二叉树以树状图的形式输出，流程图如图 2.4 所示：图 2.4第3章调试分析4.1. 遇到的问题：（1）对平衡二叉树的插入的算法设计程序存在很大问题。插入结点后需要对新的 排序树平衡化，改变结点的信息，使之形成一棵新的平衡二叉树。（2）主函数中的实参和子函数中的实参相等，造成调用该子函数时，虽然没有错 误，但其功能不能正确的实现。改变该变量后程序成功实现各种功能。（3）一些逻辑逻辑运算符书写不正确，造成实现的功能不正确或程序死循环。4.2.收获：（1）对平衡二叉树的构建的算法思想有了更清楚的认识，能够对平衡二叉树进行 创建操作，实现动态的输入数据
5、，实时的输出该树结构。（2）对多个程序的调用。（3）对平衡二叉树的平衡旋转处理有了更深刻的理解。第4章使用说明进入运行界面，如图:选择1,如图:输入一个关键字（整数）序列，以空格作为分隔符，如图:选择y,则继续，如图:参考文献1）算法与数据结构 清华大学出版社 严蔚敏 吴伟民 编著（2）C 语言程序设计清华大学出版社 王敬华 林萍 张清国编著附录#include#include #define LH +1 #define EH 0 #define RH -1 #define NULL 0 typedef struct BSTNode int data;int bf;struct BSTNode
6、 *lchild,*rchild;BSTNode,*BSTree;void CreatBST(BSTree &T);/创建平衡二叉树void R_Rotate (BSTree &p);对以*p为根的二叉排序树作右旋处理void L_Rotate(BSTree &p);对以*p为根的二叉排序树作左旋处理void LeftBalance(BSTree &T);对以指针T所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T);对以指针T所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree &T,int e,bool &taller);/
7、插入结点 evoid PrintBST(BSTree T,int depth); /按树状打印输出二叉树的元素void CreatBST(BSTree &T)int depth;int e;bool taller=false;T = NULL;printf(n请输入关键字(以0结束建立平衡二叉树):”)；scanf(%d,&e);getchar()；while(e !=0)InsertAVL(T,e,taller)；scanf(%d,&e)；getchar()；taller=false；depth=0；*J / f f f f -*% 1-1- f 1 1 -*% Tx Tx Tx Tx Tx
8、 Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx -*% 1 11 printf(”您创建的二叉树为5);if(T)PrintBST(T,depth);elseprintf(这是一棵空树!n);void R_Rotate (BSTree &p)对以*p为根的二叉排序树作右旋处理BSTree lc;lc=p-lchild; p-lchild=lc-rchild; l
9、c-rchild=p;p=lc;void L_Rotate (BSTree &p)BSTree rc;rc=p-rchild; p-rchild=rc-lchild;rc-lchild=p;p=rc;void LeftBalance(BSTree &T) 平衡旋转处理BSTree lc,rd;lc=T-lchild;switch(lc-bf)衡处理case LH:要作单右旋处理T-bf=lc-bf=EH;R_Rotate(T);break;lc指向的*p的左子树结点lc的右子树挂接为*p的左子树/p 指向新的根结点对以*p为根的二叉排序树作左旋处理rc指向的*p的右子树根结点rc的左子树挂接为
10、*p的右子树/p 指向新的根结点对以指针T所指结点为根的二叉树作左lc指向*丁的左子树根结点检查*T的左子树的平衡度，并作相应平新结点插入到*T的左孩子的左子树上，新结点插入到*T的左孩子的右子树上，case RH:要作双旋处理rd=lc-rchild;switch(rd-bf)修改*T及其左孩子的平衡因子case LH:T-bf=RH;lc-bf=EH;break;case EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;L_Rotate(T-lchild);对*T的左子树作左旋平衡处理R_Rotate(T);对*
11、T作右旋平衡处理void RightBalance(BSTree &T)对以指针T所指结点为根的二叉树作右平衡旋转处理BSTree rc,ld;rc=T-rchild;switch(rc-bf)case RH:T-bf=rc-bf=EH;L_Rotate(T);break;case LH:ld=rc-lchild;switch(ld-bf)case RH:T-bf=LH;rc-bf=EH;break;case EH:T-bf=rc-bf=EH;break;case LH:T-bf=EH;rc-bf=RH;break;ld-bf=EH;R_Rotate(T-rchild);L_Rotate(T)
12、;bool InsertAVL(BSTree &T,int e,bool &taller) /插入结点 eif(!T)T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;elseif(e=T-data)/树中已存在有相同关键字的结点taller=false;printf(”已存在相同关键字的结点!n);return 0;if(edata)继续在*丁的左子树中进行搜索if(!InsertAVL(T-lchild,e,taller)return 0;if(taller)switch
13、(T-bf)case LH:左平衡处理/未插入检查*T的平衡度/原本左子树比右子树高，需要作LeftBalance(T);taller=false;break;/原本左子树、右子 等高， 现因左case EH:子树增高而使树增高T-bf=LH;taller=true;break;/原本右子树比左子树高，现左、case RH:右子树等高T-bf=EH;taller=false;break;继续在*T的右子树中搜索elseif(!InsertAVL(T-rchild,e,taller)return 0;if(taller)检查*T的平衡度/原本左子树比右子树高，现左、switch(T-bf)case LH:右子树等高T-bf=EH;taller=false;break;/原本左子树、右子等高，现因/原本右子树比左子树高，需case EH:右子树增高而使树增高T-bf=RH;taller=true;break;case RH:要作右
