数据结构平衡二叉树课设报告

课程设计报告课程设计名称：数据结构课程设计 课程设计题目：平衡二叉树的构建算法院（系）;专业班级学号姓名指导教师装订时：此页为任务书目录第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. 独立完成系统的设计，编码和调试；3. 系统利用 C 语言实现；4.按照课程设计规范书写课程设计报告。1.2 总体结构本程序主要分为三个模块：输入模块，平衡化模块和输出模块。输入模块： 按题目要求从键盘输入一个关键字（整数）序列，关键字之间以空格作为分隔符。 平衡化模块:当左右子树高度差大于 1 时，对二叉树进行旋转平衡处理。输出模块 根据输入的关键字序列和平衡旋转处理，将平衡二叉树以树状图的形式输出。第 2 章 详细设计2.1 主模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块。主模块中提供一个可以输入的选择菜单，通过从键盘输入 1 或 2 来实现各项功能 流程图如图 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 输出模块根据输入的关键字序列和平衡旋转处理，将平衡二叉树以树状图的形式输出，流程图如图 2.4 所示：图 2.4第3章调试分析4.1. 遇到的问题：（1）对平衡二叉树的插入的算法设计程序存在很大问题。插入结点后需要对新的 排序树平衡化，改变结点的信息，使之形成一棵新的平衡二叉树。（2）主函数中的实参和子函数中的实参相等，造成调用该子函数时，虽然没有错 误，但其功能不能正确的实现。改变该变量后程序成功实现各种功能。（3）一些逻辑逻辑运算符书写不正确，造成实现的功能不正确或程序死循环。4.2.收获：（1）对平衡二叉树的构建的算法思想有了更清楚的认识，能够对平衡二叉树进行 创建操作，实现动态的输入数据，实时的输出该树结构。（2）对多个程序的调用。（3）对平衡二叉树的平衡旋转处理有了更深刻的理解。第4章使用说明进入运行界面，如图:选择1,如图:输入一个关键字（整数）序列，以空格作为分隔符，如图:选择y,则继续，如图:参考文献1）算法与数据结构 清华大学出版社 严蔚敏 吴伟民 编著（2）C 语言程序设计清华大学出版社 王敬华 林萍 张清国编著附录#include<stdio.h>#include<stdlib.h> #define LH +1 #define EH 0 #define RH -1 #define NULL 0 typedef struct BSTNode int data;int bf;struct BSTNode *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);/插入结点 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 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; lc->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的左子树挂接为*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);对*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);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(e<T->data)继续在*丁的左子树中进行搜索if(!InsertAVL(T->lchild,e,taller)return 0;if(taller)switch(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:要作右平衡处理RightBalance(T);taller=false;break;void PrintBST(BSTree T,int depth)int i;if(T->rchild)PrintBST(T->rchild,depth+1);for(i=1;i<=depth;i+)printf(" ");printf("%dn",T->data);if(T->lchild)PrintBST(T->lchild,depth+1);void main()BSTree T;int cmd,depth;char ch;bool taller=false;T=(BSTree)malloc(sizeof(BSTNode);T=NULL;printf(" *平衡二叉树的操作菜单* n")；printf("printf("1-创建 n");2-退出 n");*J / 11 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* f f -*% 1-1- f 1 1 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 Tx Tx Tx Tx Tx -*% 1 1 1 doprintf("n请选择操作的编号：");scanf("%d",&cmd);getchar();switch(cmd)case 1:CreatBST(T);break;case 2:printf(” 结束!n");break;default:printf("输入错误!n");printf("n 继续吗？ y/n:");scanf("%s",&ch);getchar();printf("n");while(ch='y');printf("n");课程设计总结：通过这次数据结构课程设计，我对平衡一叉树的理解更加深刻，在上机操作 过程中，我遇到很多问题，例如平衡二叉树的平衡旋转处理，二叉树的打印。最 终我通过查阅资料和咨询老师的方法解决了这些问题并成功地运行程序。这次课 程设计不仅让我对函数的调用了解更加清楚，也让我意识到上机实践的重要性， 只有在不断改正自己的错误的过程中吸取经验教训，才能使自己的编程能力得到 提高，这对我未来的工作也会有很大的帮助。与此同时，在这次课程设计中，我也意识到自己C语言基础不够牢固，对 一些基础知识了解不够好，在未来的学习中，我要抓紧时间弥补这方面的不足， 多上机做编程题，这有利于我接下来的学习，也能帮助我以后对计算机方面的专 业知识的理解。指导教师评语：指导教师（签字）：年 月日课程设计成绩