2022年平衡二叉树的查找、插入和删除 .pdf

《2022年平衡二叉树的查找、插入和删除 .pdf》由会员分享，可在线阅读，更多相关《2022年平衡二叉树的查找、插入和删除 .pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、平衡二叉树（AVL）查找、插入和删除小组成员：陈静 101070009 陈丹璐101070006 陈娇 101070008 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页2 目录平衡二叉树（AVL）.1查找、插入和删除.1问题描述.2设计说明.3（一）ADT.3（二）算法思想.5（三）数据结构.12（四）程序结构与流程.13 运行平台及开发工具.15 I/O 格式.15 算法复杂度分析.18 源代码.18 小结.37 问题描述利用平衡二叉树实现一个动态查找表。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共

2、38 页 -平衡二叉树的查找、插入和删除第页 共 38 页3（1）实现动态查找表的三种基本功能：查找、插入和删除。（2）初始时，平衡二叉树为空树，操作界面给出创建、查找、插入和删除和退出五种操作供选择。每种操作均要提示输入关键字。创建时，根据提示输入数据，以-1 为输入数据的结束标志，若输入数据重复，则给出已存在相同关键字的提示，并不将其插入到二叉树中。在查找时，如果查找的关键字不存在，则显示不存在查找的关键字，若存在则显示存在要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3 页 共 38 页-3-的关键字，若没有则进行插入并输出二叉树，若有则给出已有相同关键字的提醒。删除时首先检验

3、原二叉树中是否存在要删除的关键字，若有则进行删除后并输出二叉树，若没有则给出不存在要删除的关键字的提醒。（3）平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证对平衡二叉树的操作是否正确。设计说明（一）ADT ADT BalancedBinaryTree 数据对象 D：D 是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。数据关系 R：数据元素同属一个集合。基本操作 P：void R_Rotate(BSTree&p);初始条件：二叉树存在，且关键字插入到以*p 为根的二叉树的左子树的左孩子上；操作结果：对以*p 为根的二叉排序树作右旋

4、处理名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页4 void L_Rotate(BSTree&p);初始条件：二叉树存在，且关键字插入到以*p 为根的二叉树的右子树的右孩子上；操作结果：对以*p 为根的二叉排序树作左旋处理void LeftBalance(BSTree&T);初始条件：二叉树存在，且关键字插入到T 所指节点为根的二叉树的左子树的右孩子上；操作结果：对以指针T 所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree&T);初始条件：二叉树存在，且关键字插入到T 所指节点为根的

5、二叉树的右子树的左孩子上；操作结果：对以指针T 所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree&T,int e,bool&taller);初始条件：T 存在，且 e 与二叉树的原有关键字不同；操作结果：插入结点e 平且平衡化；bool SearchBST(BSTree&T,int key);初始条件：T 存在且元素key 与某关键字相同；操作结果：查找元素key 是否在树中void PrintBST(BSTree T);初始条件：T 存在操作结果：按中序遍历输出二叉树的元素void CreatBST(BSTree&T);初始条件：T 为空操作结果：创建平衡二叉树

6、,(注意:以输入-1 为二叉树建立的结束)void LeftBalance_div(BSTree&p,int&shorter);名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页5 初始条件：T 存在操作结果：删除结点时左平衡旋转处理void RightBalance_div(BSTree&p,int&shorter);初始条件：T 存在操作结果：删除结点时右平衡旋转处理void Delete(BSTree q,BSTree&r,int&shorter);初始条件：T 存在且节点删除成功操作结果：删除结点int Delete

7、AVL(BSTree&p,int x,int&shorter);初始条件：操作结果：平衡二叉树的删除操作 ADT BalancedBinaryTree（二）算法思想1、查找在根指针 T 所指二叉排序树中递归地查找某关键字等于key 的数据元素，若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。如果树T 为空，则查找不成功，返回空指针；当树 T 非空时，如果根指针T 所指数据元素的关键字等于key，则查找成功，返回根指针 T，否则在左子树中继续查找，若还未找到，则继续在右子树中进行查找，直到找到该数据元素或树T 为空为止。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 3

8、8 页 -平衡二叉树的查找、插入和删除第页 共 38 页6/查找元素 key 是否在树中bool SearchBST(BSTree&T,int key)if(!T)return false;else if(EQ(key,T-data)return true;else if(LT(key,T-data)return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);2、插入（一）若T 为空树，则插入一个数据元素为e 的新节点作为T 的根节点，树长高，树的深度增加1。（二）若待插入的数据元素e 与 T 的根节点的关键字相同，则不

9、进行插入。（三）若待插入的数据元素e 小于根节点的关键字，且在T 的左子树上不存在与e 相等的数据元素，那么将e 插入到 T 的左子树上。下面就插入到左子树之后，就不同的情况进行处理：若之前 T 的根节点的平衡因子为-1，将根节点的平衡因子变为0，T 的深度不变；若之前 T 的根节点的平衡因子为0，就将根节点的平衡因子变为1，T 的深度增加；若之前的T 的根节点的平衡因子为1，那么当其左子树的根节点的平衡因子为1 的时候，需要进行单向右旋处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子改为 0，树的深度不变；当其左子树的根节点的平衡因子为-1的时候，要进行先左后右的双向旋转平衡，并

10、在旋转之后，修改根节点和其左右子树的根节点的平衡因子，树的深度不名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页7 变。（四）若待插入的数据元素e 大于根节点的关键字，且在T 的右子树上不存在与e 相等的数据元素，那么将e 插入到 T 的右子树上。下面就插入到右子树之后，就不同的情况进行处理：若之前 T 的根节点的平衡因子为1，将根节点的平衡因子变为0，T 的深度不变；若之前 T 的根节点的平衡因子为0，就将根节点的平衡因子变为1，T 的深度增加；若之前的T 的根节点的平衡因子为-1，那么当其右子树的根节点的平衡因子为-1

11、 的时候，需要进行单向左旋处理，并且在左旋处理之后，将根节点和其左子树根节点的平衡因子改为 0，树的深度不变；当其右子树的根节点的平衡因子为1 的时候，要进行先右后左的双向旋转平衡，并在旋转之后，修改根节点和其左右子树的根节点的平衡因子，树的深度不变。/插入结点e,若 T 中不存在和e 相同关键字的结点，则插入一个数据元素为e 的新结点，并返回 1，否则返回0 bool InsertAVL(BSTree&T,int e,bool&taller)if(!T)/插入新结点，树长高，置 taller为 true T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-

12、lchild=T-rchild=NULL;T-bf=EH;taller=true;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页8 else if(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 的左子树中且左子树长高 swit

13、ch(T-bf)/检查*T 的平衡度 case LH:/原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller=false;break;case EH:/原本左子树、右子等高，现因左子树增高而使树增高T-bf=LH;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页9 taller=true;break;case RH:/原本右子树比左子树高，现左、右子树等高T-bf=EH;taller=false;break;else/应继续在*T 的右子树中进行搜索 if(!InsertAVL(T-rchild

14、,e,taller)return 0;/未插入if(taller)/已插入到*T 的右子树中且右子树长高 switch(T-bf)/检查*T 的平衡度 case LH:/原本左子树比右子树高，现左、右子树等高T-bf=EH;taller=false;break;case EH:/原本左子树、右子等高，现因右子树增高而使树增高T-bf=RH;taller=true;break;case RH:/原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=false;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 38 页 -平衡二叉树的查找、插入

15、和删除第页 共 38 页10 return 1;/InsertAVL 3、删除元素的删除，有三种情况，分别是：（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。具体实现如下：int DeleteAVL(BSTree&p,int x,int&shorter)int k;BSTree q;if(p=NULL)printf(不存在要删除的关键字!n);return 0;else if(xdata)/在 p 的左子树中进行删除名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 3

16、8 页11 k=DeleteAVL(p-lchild,x,shorter);if(shorter=1)LeftBalance_div(p,shorter);return k;else if(xp-data)/在 p 的右子树中进行删除 k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBalance_div(p,shorter);return k;else q=p;if(p-rchild=NULL)/右子树空则只需重接它的左子树 p=p-lchild;free(q);shorter=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页

17、，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页12 else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild;free(q);shorter=1;else/左右子树均不空 Delete(q,q-lchild,shorter);if(shorter=1)LeftBalance_div(p,shorter);p=q;return 1;（三）数据结构本实验中平衡二叉树采用二叉链表的方式进行存储。定义如下：typedef struct BSTNode int data;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 38 页 -

18、平衡二叉树的查找、插入和删除第页 共 38 页13 int bf;/结点的平衡因子struct BSTNode*lchild,*rchild;/左、右孩子指针BSTNode,*BSTree;（四）程序结构与流程本程序包括四个模块，分别为主函数、AVL 的创建、AVL 的查找函数、AVL 的插入函数、AVL 的删除函数。流程图如下：主函数定义如下：主函数主要是根据输入的数字选择要对平衡二叉树进行的操作，创建、查找、删除或者是插入。void main()int input,search;bool taller=false;int shorter=0;BSTree T,T1,T2;主函数void m

19、ain()AVL 的创建AVL 的查找AVL 的插入AVL 的删除名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页14 T=(BSTree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)printf(1.创建 t2.查找 t3.插入 t4.删除 t5.退出*n);printf(请输入您所需的操作功能:t);scanf(%d,&input);getchar();switch(input)case 1:CreatBST(T);break;case 2:printf(请输入你要查找的关

20、键字);scanf(%d,&search);getchar();if(SearchBST(T,search)printf(该 二 叉 树 中 存 在 关 键 字%d，查 找 成功!n,search);else printf(查找失败!n);break;case 3:printf(请输入你要插入的关键字);scanf(%d,&search);getchar();名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页15 InsertAVL(T,search,taller);PrintBST(T);break;case 4:pri

21、ntf(请输入你要删除的关键字);scanf(%d,&search);getchar();DeleteAVL(T,search,shorter);PrintBST(T);break;case 5:break;default:printf(输入错误，请重新选择。);break;printf(tt按任意键继续.);getchar();运行平台及开发工具该程序在 Windows XP/07上运行良好，使用Microsoft Visual C+6.0开发。I/O 格式输入：该程序要求输入数据为整型数据，并以-1作为输入数据的结束标志，创建过程中若输入相同的数据只会生成一个关键字并给出输入数据相同的提示

22、。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页16 输出：该程序对于对平衡二叉树的输出采用中序遍历的方法。因为中序遍历平衡二叉树的得到的结果肯定为有序的，所以可以据此判断对于平衡二叉树操作的正确性。测试数据：1、创建输入数据：34、45、12、22、34、56、76、11、-45、23、-1；进行平衡二叉树的创建，运行结果如下图：2、查找查找在原有二叉树上已存在的关键字：【查找 23】运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页1

23、7 查找在原有二叉树上不存在的数据：【查找 24】运行结果：3、插入在 1 的基础上进行插入，分两种情况：插入与原二叉树关键字不重复的数据：【插入 99】运行结果如下：插入已存在原二叉树中的数据：【插入 22】运行结果如下：4、删除删除在原有平衡二叉树上已存在的关键字：【删除 22】运行结果如下：删除在原有平衡二叉树上不存在的数据：【删除 98】运行结果如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页18 算法复杂度分析在平衡二叉树上进行查找的过程和二叉排序树相同，因此，在查找的过程中与给定值进行比较的关键字个数不

24、会超过数的深度。因此平衡二叉树查找的时间复杂度主要由树的深度决定。我们首先分析深度为h 的平衡树所具有的最少结点数。假设以 N（h）表示深度为h 的平衡树含有的最少结点数，显然，N（0）=0，N(1)=1，N(2)=2，并且 N(h)=N(h-1)+N（h-2），在通过归纳法可以求出这个N(h)，反之，在知道n 的情况我们也可以推导出h 的最大值，所以最后可以得到在平衡二叉树上查找的时间复杂度是 T(n)=O(2n)。同样的插入和删除的时间复杂度也为O(2n)。源代码#include#include#include#define EQ(a,b)(a)=(b)#define LT(a,b)(a)

25、(b)#define LH+1/左高#define EH 0/等高#define RH-1/右高名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页19#define NULL 0 typedef struct BSTNode int data;int bf;/结点的平衡因子struct BSTNode*lchild,*rchild;/左、右孩子指针BSTNode,*BSTree;void R_Rotate(BSTree&p);/对以*p 为根的二叉排序树作右旋处理void L_Rotate(BSTree&p);/对以*p

26、为根的二叉排序树作左旋处理void LeftBalance(BSTree&T);/对以指针 T 所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree&T);/对以指针 T 所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree&T,int e,bool&taller);/插入结点 e bool SearchBST(BSTree&T,int key);/查找元素 key 是否在树中void PrintBST(BSTree T);/按中序遍历输出二叉树的元素void CreatBST(BSTree&T);/创建平衡二叉树,(注意:以输入-1

27、为二叉树建立的结束)void LeftBalance_div(BSTree&p,int&shorter);/删除结点时左平衡旋转处理void RightBalance_div(BSTree&p,int&shorter);/删除结点时右平衡旋转处理void Delete(BSTree q,BSTree&r,int&shorter);/删除结点int DeleteAVL(BSTree&p,int x,int&shorter);/平衡二叉树的删除操作名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页20 void main()i

28、nt input,search;bool taller=false;int shorter=0;BSTree T,T1,T2;T=(BSTree)malloc(sizeof(BSTNode);T=T1=T2=NULL;while(1)printf(1.创建 t2.查找 t3.插入 t4.删除 t5.退出*n);printf(请输入您所需的操作功能:t);scanf(%d,&input);getchar();switch(input)case 1:CreatBST(T);break;case 2:printf(请输入你要查找的关键字);scanf(%d,&search);getchar();名师

29、资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页21 if(SearchBST(T,search)printf(该 二 叉 树 中 存 在 关 键 字%d，查 找 成功!n,search);else printf(查找失败!n);break;case 3:printf(请输入你要插入的关键字);scanf(%d,&search);getchar();InsertAVL(T,search,taller);PrintBST(T);break;case 4:printf(请输入你要删除的关键字);scanf(%d,&search)

30、;getchar();DeleteAVL(T,search,shorter);PrintBST(T);break;case 5:break;default:printf(输入错误，请重新选择。);break;printf(tt按任意键继续.);getchar();名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页22/对以*p 为根的二叉排序树作右旋处理,LL 型平衡旋转法void R_Rotate(BSTree&p)BSTree lc;lc=p-lchild;/lc指向的*p 左子树根结点p-lchild=lc-rchi

31、ld;/lc的右子树挂接为*p 的左子树lc-rchild=p;p=lc;/p指向新的结点/对以*p 为根的二叉排序树作左旋处理，RR 型平衡旋转法void L_Rotate(BSTree&p)BSTree rc;rc=p-rchild;/rc指向的*p 右子树根结点p-rchild=rc-lchild;/rc的左子树挂接为*p 的右子树rc-lchild=p;p=rc;/p指向新的结点 名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页23/对以指针 T 所指结点为根的二叉树作左平衡旋转处理，LR 型平衡旋转法void

32、LeftBalance(BSTree&T)BSTree lc,rd;lc=T-lchild;/lc指向*T 的左子树根结点switch(lc-bf)/检查*T 的左子树的平衡度，并作相应平衡处理 case LH:/新结点插入在*T 的左孩子的左子树上，要作单右旋处理T-bf=lc-bf=EH;R_Rotate(T);break;case RH:/新结点插入在*T 的左孩子的右子树上，要作双旋处理rd=lc-rchild;/rd指向*T 的左孩子的右子树根switch(rd-bf)/修改*T 及其左孩子的平衡因子 case LH:T-bf=RH;lc-bf=EH;break;case EH:T-

33、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 作右旋平衡处理名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页24 /对以指针 T 所指结点为根的二叉树作右平衡旋转处理，RL 型平衡旋转法void RightBalance(BSTree&T)BSTree rc,ld;rc=T-rchild;/rc指向*T 的右子树根结点switch(rc-bf)/检查

34、*T 的右子树的平衡度，并作相应平衡处理 case RH:/新结点插入在*T 的右孩子的右子树上，要作单左旋处理T-bf=rc-bf=EH;L_Rotate(T);break;case LH:/新结点插入在*T 的右孩子的左子树上，要作双旋处理ld=rc-lchild;/ld指向*T 的右孩子的左子树根switch(ld-bf)/修改*T 及其右孩子的平衡因子 case LH:T-bf=EH;rc-bf=RH;break;case EH:T-bf=rc-bf=EH;break;case RH:T-bf=LH;rc-bf=EH;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 24

35、页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页25 ld-bf=EH;R_Rotate(T-rchild);/对*T 的右子树作左旋平衡处理L_Rotate(T);/对*T 作左旋平衡处理 /插入结点e,若 T 中不存在和e 相同关键字的结点，则插入一个数据元素为e 的新结点，并返回 1，否则返回0 bool InsertAVL(BSTree&T,int e,bool&taller)if(!T)/插入新结点，树长高，置 taller为 true T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-lchild=T-rchild=NULL;

36、T-bf=EH;taller=true;else if(EQ(e,T-data)/树中已存在和有相同关键字的结点则不再插入 名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页26 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 的平衡度

37、case LH:/原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller=false;break;case EH:/原本左子树、右子等高，现因左子树增高而使树增高T-bf=LH;taller=true;break;case RH:/原本右子树比左子树高，现左、右子树等高T-bf=EH;taller=false;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页27 else/应继续在*T 的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller)return

38、0;/未插入if(taller)/已插入到*T 的右子树中且右子树长高 switch(T-bf)/检查*T 的平衡度 case LH:/原本左子树比右子树高，现左、右子树等高T-bf=EH;taller=false;break;case EH:/原本左子树、右子等高，现因右子树增高而使树增高T-bf=RH;taller=true;break;case RH:/原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=false;break;return 1;/InsertAVL 名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 38 页 -平衡二叉树的查

39、找、插入和删除第页 共 38 页28/查找元素 key 是否在树中bool SearchBST(BSTree&T,int key)if(!T)return false;else if(EQ(key,T-data)return true;else if(LT(key,T-data)return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);/中序遍历平衡二叉树void PrintBST(BSTree T)if(T)PrintBST(T-lchild);printf(%d,T-data);PrintBST(T-rchild)

40、;名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页29/创建平衡二叉树，（注意：以输入-1 为二叉树建立的结束）void CreatBST(BSTree&T)int e;bool taller=false;T=NULL;printf(n请输入关键字(以-1 结束建立平衡二叉树):);scanf(%d,&e);getchar();while(e!=-1)InsertAVL(T,e,taller);printf(n请输入关键字(以-1 结束建立平衡二叉树):);scanf(%d,&e);getchar();taller=fa

41、lse;printf(平衡二叉树创建结束,中序遍历平衡二叉树：n);if(T)PrintBST(T);else printf(这是一棵空树.n);名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页30/删除结点时左平衡旋转处理void LeftBalance_div(BSTree&p,int&shorter)BSTree p1,p2;if(p-bf=1)/p结点的左子树高，删除结点后p 的 bf 减 1,树变矮 p-bf=0;shorter=1;else if(p-bf=0)/p结点左、右子树等高，删除结点后p 的 bf

42、减 1,树高不变 p-bf=-1;shorter=0;else/p结点的右子树高 p1=p-rchild;/p1指向 p 的右子树if(p1-bf=0)/p1结点左、右子树等高,删除结点后p 的 bf 为-2,进行左旋处理，树高不变 L_Rotate(p);p1-bf=1;p-bf=-1;shorter=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页31 else if(p1-bf=-1)/p1的右子树高，左旋处理后，树变矮 L_Rotate(p);p1-bf=p-bf=0;shorter=1;else/p1的左子

43、树高,进行双旋处理(先右旋后左旋)，树变矮 p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)p-bf=0;p1-bf=0;else if(p2-bf=-1)p-bf=1;p1-bf=0;else p-bf=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页32 p1-bf=-1;p2-bf=0;p=p2;shorter=1;/删除结点时右平衡旋转处理void RightBalance_div(

44、BSTree&p,int&shorter)BSTree p1,p2;if(p-bf=-1)p-bf=0;shorter=1;else if(p-bf=0)p-bf=1;shorter=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页33 else p1=p-lchild;if(p1-bf=0)R_Rotate(p);p1-bf=-1;p-bf=1;shorter=0;else if(p1-bf=1)R_Rotate(p);p1-bf=p-bf=0;shorter=1;else p2=p1-rchild;p1-rchi

45、ld=p2-lchild;p2-lchild=p1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)p-bf=0;p1-bf=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页34 else if(p2-bf=1)p-bf=-1;p1-bf=0;else p-bf=0;p1-bf=1;p2-bf=0;p=p2;shorter=1;/删除结点void Delete(BSTree q,BSTree&r,int&shorter)if(r-rchild=NULL)q-data=r-data;

46、q=r;名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页35 r=r-lchild;free(q);shorter=1;else Delete(q,r-rchild,shorter);if(shorter=1)RightBalance_div(r,shorter);/平衡二叉树的删除操作int DeleteAVL(BSTree&p,int x,int&shorter)int k;BSTree q;if(p=NULL)printf(不存在要删除的关键字!n);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-

47、第 35 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页36 else if(xdata)/在 p 的左子树中进行删除 k=DeleteAVL(p-lchild,x,shorter);if(shorter=1)LeftBalance_div(p,shorter);return k;else if(xp-data)/在 p 的右子树中进行删除 k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBalance_div(p,shorter);return k;else q=p;if(p-rchild=NULL)/右子树空则只需重接

48、它的左子树 p=p-lchild;free(q);shorter=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 36 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页37 else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild;free(q);shorter=1;else/左右子树均不空 Delete(q,q-lchild,shorter);if(shorter=1)LeftBalance_div(p,shorter);p=q;return 1;小结在完成作业的过程中对于平衡二叉树的定义、创建、查找、插入和删除的算法思想有了更

49、多的了解。由于其中的一些模块的函数在书上是有范例的，因此可以了解书上的算法之后自己理解之后再尝试写出来。同时，在这过程中，可以体会到平衡二叉树在查找上的优势，名师资料总结-精品资料欢迎下载-名师精心整理-第 37 页，共 38 页 -平衡二叉树的查找、插入和删除第页 共 38 页38 但是由于平衡二叉树在插入和删除之后都要进行相应的旋转，所以最初的时候理解起来还是有一些难度，不过经过资料的查阅，这个困难也渐渐被克服。但是有一个遗憾是平衡二叉树的输出函数没能采用树形输出的方式，而是采用中序遍历的方法，不够直观。同时，没有采用图形界面进行更为直观的输出和表示也是遗憾之一。也许这个题目对于三个人一起完成看上去简单了一些，但是在这个过程中我们更好地学会了怎么去学习和合作，对于我们来说也是一次难得的经历。名师资料总结-精品资料欢迎下载-名师精心整理-第 38 页，共 38 页 -