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

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

2、平衡二叉树void R_Rotate(BSTree &p);/对以 *p为根的二叉排序树作左旋处理聞創沟燴鐺險爱氇谴净祸測樅。void L_Rotate(BSTree &p);/对以 *p为根的二叉排序树作左旋处理残骛楼諍锩瀨濟溆塹籟婭骒東。void LeftBalance(BSTree &T);/对以指针所指结点为根的二叉树作左平衡旋转处理酽锕极額閉镇桧猪訣锥顧荭钯。void RightBalance(BSTree &T);/对以指针所指结点为根的二叉树作右平衡旋转处理彈贸摄尔霁毙攬砖卤庑诒尔肤。bool InsertAVL(BSTree &T,int e,bool &taller);/插入

3、结点 e 謀荞抟箧飆鐸怼类蒋薔點鉍杂。bool SearchBST(BSTree &T,int key);/查找元素 key 是否在树 T 中 厦礴恳蹒骈時盡继價骚卺癩龔。void LeftBalance_div(BSTree&p,int&shorter);/删除结点时左平衡旋转处理茕桢广鳓鯡选块网羈泪镀齐鈞。void RightBalance_div(BSTree &p,int &shorter);/删除结点时右平衡旋转处理鹅娅尽損鹌惨歷茏鴛賴縈诘聾。void Delete(BSTree q,BSTree&r,int &shorter);/删除结点 籟丛妈羥为贍偾蛏练淨槠挞曉。int Del

4、eteA VL(BSTree &p,int x,int &shorter);/ 平衡二叉树的删除操作 預頌圣鉉儐歲龈讶骅籴買闥龅。void PrintBST(BSTree T,int m);/ 按树状打印输出二叉树的元素渗釤呛俨匀谔鱉调硯錦鋇絨钞。主程序的流程请输入操作的选项编号（1-5）1 / 131-创建平衡二叉树2-查找3-插入4-删除5-结束3.各模块之间的层次调用详细设计主模块退出1.以平衡二叉树的插入和平衡化为例：bool InsertAVL(BSTree &T,int e,bool &taller)显示主输入数平衡化查插删/若存在菜平单衡的二叉排序据树元素 T 中不存在和 e 有

5、相同关键字找的节点，则插入入一个数据元除素为 e /的新结点，并返回 1，否者返回 0。若因插入而使二叉排序树失去平衡，则作平衡旋转理，/布尔变量 taller 反映 T 长高与否。if(!T)/ 插入新结点，树 “长高 ”，置 taller输出 为 trueT = (BSTree)malloc(sizeof(BSTNode);T-data = e;T-lchild = T-rchild =NULL;T-bf = EH; taller = true;elseif(EQ(e,T-data)/ 树中已存在和有相同关键字的结点铙誅卧泻噦圣骋贶頂廡缝勵罴。 taller = false;printf(

6、 已存在相同关键字的结点 n); return 0; / 则不再插入 擁締凤袜备訊顎轮烂蔷報赢无。if(LT(e,T-data)/ 应继续在 *T 的左子树中进行搜索贓熱俣阃歲匱阊邺镓騷鯛汉鼉。if(!InsertA VL(T-lchild,e,taller) return 0;/ 未插入if(taller)/ 已插入到 *T 的左子树中且左子树坛摶乡“长高 ”囂忏蒌鍥铃氈淚跻馱釣。switch(T-bf)/ 检查 *T 的平衡度case LH:/ 原本左子树比右子树高，需要作左平衡处理LeftBalance(T); taller = false; break;case EH:/ 原本左子树、

7、右子等高，现因左子树增高而使树增高T-bf = LH; taller = true; break;case RH:/ 原本右子树比左子树高，现左、右子树等高2 / 13T-bf = EH; taller = false; break;/switch(T-bf)/ifelse/应继续在 *T的右子树中进行搜索蜡變黲癟報伥铉锚鈰赘籜葦繯。if(!InsertA VL(T-rchild,e,taller) return 0;/未插入if(taller)/ 已插入到買鲷鴯*T 的右子树中且右子树 “长高 ”譖昙膚遙闫撷凄届嬌擻。switch(T-bf)/ 检查 *T的平衡度case LH:/ 原本左子

8、树比右子树高，现左、右子树等高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.说明：执行完输入函数后，会在键盘缓冲区中保存回车键，后面再对字符型量赋值时，会将缓冲区当成数据存入变量中，所以要在某些输入语句后面加getchar函数

9、。4.调试分析1.遇到的问题：（1）对平衡二叉树的删除的算法设计程序存在很大问题。删除节点后需要对新的排序树平衡化，改变节点的信息，使之形成一棵新的平衡二叉树。 綾镝鯛駕櫬鹕踪韦辚糴飙钪麦。（2）主函数中的实参和子函数中的实参相等，造成调用该子函数时，虽然没有错误，但其功能不能正确的实现。改变该变量后程序成功实现各种功能。驅踬髏彦浃绥譎饴憂锦諑琼针。（ 3）一些逻辑逻辑运算符书写不正确，造成实现的功能不正确或程序死循环。2.收获：（1）对平衡二叉树的构造、插入和删除的算法思想有了更清楚的认识，能够对平衡二叉树进行创建、调平、插入、删除等操作，实现动态的输入数据，实时的输出该树结构.猫虿驢绘燈鮒

10、诛髅貺庑献鵬缩。（2）对多个程序的调用5.用户使用说明1.了解程序清单上给出的功能，并根据提示依次进行操作。2.创建二叉树，输入的数据元素为整数，当输入-123 时，停止创建。并显示平衡二叉树的中3 / 13序凹入树形图。3.查找（输入你要查找的元素）。4.插入（输入要插入的数据元素，并输出）5.删除（删除指定的元素，并输出）6.结束说明：其中每一个功能实现后都会提示是否继续：选择y 继续，否则，终止。6.测试结果1.创建平衡二叉树： （中序凹入输出）2.查找查找成功或失败时：3.插入4.删除 ,结束4 / 137.附录源代码：#include#include#define LH +1#def

11、ine EH 0#define RH -1#define NULL 0typedef struct BSTNode int data;int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;void CreatBST(BSTree &T);void R_Rotate (BSTree &p);void L_Rotate(BSTree &p);void LeftBalance(BSTree &T);void RightBalance(BSTree &T);bool InsertAVL(BSTree &T,int e,bool &taller);b

12、ool SearchBST(BSTree &T,int key);void LeftBalance_div(BSTree &p,int &shorter);void RightBalance_div(BSTree &p,int &shorter);void Delete(BSTree q,BSTree&r,int &shorter);int DeleteA VL(BSTree &p,int x,int &shorter);void PrintBST(BSTree T,int depth);void main()5 / 13BSTree T;int sear,cmd,depth;char ch;

13、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);printf(*n);構氽頑黉碩饨荠龈话骛門戲鷯。doprintf(n 请选择操作的编号：);scanf(%d,&cmd);getchar();switch(cmd)case 1:CreatBST(T);break;case

14、 2:printf( 请输入您要查找的关键字：);scanf(%d,&sear);getchar();if(SearchBST(T,sear) printf( 关键字 %d 存在，查找成功 !n,sear); 輒峄陽檉簖疖網儂號泶蛴镧釃。else printf( 查找失败 !n);break;case 3:printf( 请输入您要插入的关键字：);scanf(%d,&sear);getchar;InsertAVL(T,sear,taller);depth=0;PrintBST(T,depth);break;case 4:depth=0;printf( 请输入你要删除的关键字: );scanf

15、(%d,&sear); getchar();DeleteAVL(T,sear,shorter);PrintBST(T,depth);6 / 13break;case 5:printf( 结束 !n);break;default:printf( 输入错误 !n);if(cmd=5)break;printf(n 继续吗 ? y/n: );scanf(%s,&ch);getchar();printf(n);while(ch=y);printf(n);void CreatBST(BSTree &T)int depth;int e;bool taller=false;T = NULL;printf(n

16、请输入关键字(以 -123 结束建立平衡二叉树):);scanf(%d,&e);getchar();while(e != -123)InsertAVL(T,e,taller);printf(n 请输入关键字(以 -123 结束建立平衡二叉树):);scanf(%d,&e);getchar();taller=false;depth=0;printf(n*n);尧侧閆繭絳 闕绚勵蜆贅瀝纰縭。printf(您创建的二叉树为n);if(T)PrintBST(T,depth);elseprintf( 这是一棵空树!n);void R_Rotate (BSTree &p)/对以 *p 为根的二叉排序树作右旋处理7 / 13BSTree lc;lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;void L_Rotate(BSTree &p)/对以 *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