计算机科学学院数据结构课程设计报告.DOC

1、计算机科学学院数据结构课程设计报告平衡二叉树操作学生姓名：学 号：班 级：指导老师：报告日期：1. 需求分析1建立平衡二叉树并进行创建、查找、插入、删除等功能。2设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。3测试数据：自选数据2.概要设计1.抽象数据类型定义：typedef struct BSTNode int data; int bf; /节点的平衡因子struct BSTNode *lchild,*rchild; /左右孩子指针BSTNode,*BSTree;void CreatBST(BSTree /创建平衡二叉树void R

2、_Rotate(BSTree /对以*p 为根的二叉排序树作左旋处理void L_Rotate(BSTree /对以*p 为根的二叉排序树作左旋处理void LeftBalance(BSTree /对以指针所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree /对以指针所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree /插入结点 ebool SearchBST(BSTree /查找元素 key 是否在树 T 中void LeftBalance_div(BSTree /删除结点时左平衡旋转处理void RightBalance_div

3、(BSTree /删除结点时右平衡旋转处理void Delete(BSTree q,BSTree /删除结点int DeleteAVL(BSTree /平衡二叉树的删除操作void PrintBST(BSTree T,int m); /按树状打印输出二叉树的元素2. 主程序的流程请输入操作的选项编号（1-5）1-创建平衡二叉树2-查找3-插入4-删除5-结束3.各模块之间的层次调用3. 详细设计1.以平衡二叉树的插入和平衡化为例：bool InsertAVL(BSTree T-data = e;T-lchild = T-rchild =NULL;T-bf = EH; taller = true

4、;elseif(EQ(e,T-data) /树中已存在和有相同关键字的结点 taller = false;printf(“已存在相同关键字的结点n“); return 0; /则不再插入if(LT(e,T-data) /应继续在*T 的左子树中进行搜索if(!InsertAVL(T-lchild,e,taller) return 0;/未插入if(taller) /已插入到*T 的左子树中且左子树“长高”switch(T-bf) /检查*T 的平衡度case LH: /原本左子树比右子树高，需要作左平衡处理LeftBalance(T); taller = false; break;case E

5、H: /原本左子树、右子等高，现因左子树增高而使树增高主模块平衡化输入数据元素显示主菜单查找 插入 删除输出退出T-bf = LH; taller = true; break;case RH: /原本右子树比左子树高，现左、右子树等高T-bf = EH; taller = false; break;/switch(T-bf)/ifelse /应继续在 *T 的右子树中进行搜索if(!InsertAVL(T-rchild,e,taller) return 0;/未插入if(taller) /已插入到*T 的右子树中且右子树“长高”switch(T-bf) /检查*T 的平衡度case LH: /

6、原本左子树比右子树高，现左、右子树等高T-bf = EH; taller = false; break;case EH: /原本左子树、右子等高，现因右子树增高而使树增高T-bf = RH; taller = true; break;case RH: /原本右子树比左子树高，需要作右平衡处理RightBalance(T); taller = false; break;/switch(T-bf)/else/elsereturn 1;/InsertAVL2.说明：执行完输入函数后，会在键盘缓冲区中保存回车键，后面再对字符型量赋值时，会将缓冲区当成数据存入变量中，所以要在某些输入语句后面加getch

7、ar函数。 4.调试分析1. 遇到的问题：（1）对平衡二叉树的删除的算法设计程序存在很大问题。删除节点后需要对新的排序树平衡化，改变节点的信息，使之形成一棵新的平衡二叉树。（2）主函数中的实参和子函数中的实参相等，造成调用该子函数时，虽然没有错误，但其功能不能正确的实现。改变该变量后程序成功实现各种功能。（3）一些逻辑逻辑运算符书写不正确，造成实现的功能不正确或程序死循环。2.收获：（1）对平衡二叉树的构造、插入和删除的算法思想有了更清楚的认识，能够对平衡二叉树进行创建、调平、插入、删除等操作，实现动态的输入数据，实时的输出该树结构.（2）对多个程序的调用5.用户使用说明1.了解程序清单上给出

8、的功能，并根据提示依次进行操作。2.创建二叉树，输入的数据元素为整数，当输入-123 时，停止创建。并显示平衡二叉树的中序凹入树形图。3.查找（输入你要查找的元素） 。4.插入（输入要插入的数据元素，并输出）5.删除（删除指定的元素，并输出）6.结束说明：其中每一个功能实现后都会提示是否继续：选择 y 继续，否则，终止。6.测试结果1.创建平衡二叉树：（中序凹入输出）2.查找查找成功或失败时：3.插入4.删除,结束7.附录源代码：#include#include#define LH +1#define EH 0#define RH -1#define NULL 0typedef struct

9、BSTNode int data;int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;void CreatBST(BSTree void R_Rotate (BSTree void L_Rotate(BSTree void LeftBalance(BSTree void RightBalance(BSTree bool InsertAVL(BSTree bool SearchBST(BSTree void LeftBalance_div(BSTree void RightBalance_div(BSTree void Delete(BST

10、ree q,BSTree int DeleteAVL(BSTree void PrintBST(BSTree T,int depth);void main()BSTree T;int sear,cmd,depth;char ch;int shorter=0;bool taller=false;T=(BSTree)malloc(sizeof(BSTNode);T=NULL;printf(“*平衡二叉树的操作菜单*n“);printf(“ 1-创建n“);printf(“ 2-查找n“);printf(“ 3-插入n“);printf(“ 4-删除n“);printf(“ 5-退出n“);prin

11、tf(“*n“);doprintf(“n 请选择操作的编号：“);scanf(“%d“,getchar();switch(cmd)case 1:CreatBST(T);break;case 2:printf(“请输入您要查找的关键字：“);scanf(“%d“,getchar();if(SearchBST(T,sear) printf(“关键字%d 存在，查找成功!n“,sear);else printf(“查找失败 !n“);break;case 3:printf(“请输入您要插入的关键字：“);scanf(“%d“,getchar;InsertAVL(T,sear,taller);dept

12、h=0;PrintBST(T,depth);break;case 4:depth=0;printf(“请输入你要删除的关键字: “);scanf(“%d“, getchar();DeleteAVL(T,sear,shorter);PrintBST(T,depth); break;case 5:printf(“结束!n“);break;default:printf(“输入错误!n“);if(cmd=5)break;printf(“n 继续吗? y/n: “);scanf(“%s“,getchar();printf(“n“);while(ch=y);printf(“n“);void CreatBS

13、T(BSTree int e;bool taller=false;T = NULL;printf(“n 请输入关键字(以-123 结束建立平衡二叉树):“);scanf(“%d“,getchar();while(e != -123)InsertAVL(T,e,taller);printf(“n 请输入关键字(以-123 结束建立平衡二叉树):“);scanf(“%d“,getchar();taller=false;depth=0;printf(“n*n“);printf(“ 您创建的二叉树为n“);if(T)PrintBST(T,depth);elseprintf(“这是一棵空树!n“);void R_Rotate (BSTree lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;void L_Rotate(BSTree rc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;void LeftBalance(BSTree lc=T-lchild;switch(lc-bf)case LH:T-bf=lc-bf=EH;R_Rotate(T);break;case RH:rd=lc-rchild;switch(rd-bf)case LH:T-bf=RH;lc-bf=EH;break;case EH: