2022年数据结构平衡二叉树的操作演示归纳 .pdf

平衡二叉树操作的演示1. 需求分析本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能：（1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。（2）平衡二叉树的显示采用凹入表现形式。（3）合并两棵平衡二叉树。（4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于 x，另一棵树中的任一关键字都大于x。如下图：2概要设计平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下， 调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 具体步骤：（1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；（2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；（3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是 LL型或 RR型，只需应用扁担原理旋转一次，在旋转过程中， 如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或 RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1 的结点。流程图3. 详细设计二叉树类型定义：typedefint Status; typedefintElemType; typedefstructBSTNode 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - ElemType data; int bf; structBSTNode *lchild ,*rchild; BSTNode,* BSTree; Status SearchBST(BSTreeT,ElemType e)/查找void R_Rotate(BSTree&p)/右旋void L_Rotate(BSTree&p)/左旋void LeftBalance(BSTree&T)/插入平衡调整void RightBalance(BSTree&T)/插入平衡调整Status InsertAVL(BSTree&T,ElemTypee,int&taller)/插入void DELeftBalance(BSTree&T)/删除平衡调整void DERightBalance(BSTree&T)/删除平衡调整Status Delete(BSTree&T,int&shorter)/删除操作Status DeleteAVL(BSTree&T,ElemTypee,int&shorter)/删除操作void merge(BSTree&T1,BSTree &T2)/合并操作void splitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2)/分裂操作void PrintBSTree(BSTree&T,intlev)/凹入表显示附录源代码：#include #include /#define TRUE 1 /#define FALSE 0 /#define OK 1 /#define ERROR 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - #define LH +1 #define EH 0 #define RH -1 / 二叉类型树的类型定义typedefint Status; typedefintElemType; typedefstructBSTNode ElemType data; int bf;/ 结点的平衡因子structBSTNode *lchild ,*rchild;/左、右孩子指针 BSTNode,* BSTree; /* 查找算法*/ Status SearchBST(BSTreeT,ElemType e) if(!T) return 0; / 查找失败 else if(e = T-data ) return 1; / 查找成功 else if (e data) returnSearchBST(T-lchild,e); else returnSearchBST(T-rchild,e); / 右旋voidR_Rotate(BSTree&p) BSTreelc; /处理之前的左子树根结点lc = p-lchild; /lc 指向的 *p 的左子树根结点p-lchild = lc-rchild; /lc的右子树挂接为*P 的左子树lc-rchild = p; p = lc; /p 指向新的根结点 / 左旋voidL_Rotate(BSTree&p) BSTreerc; rc = p-rchild; /rc 指向的 *p 的右子树根结点p-rchild = rc-lchild; /rc的左子树挂接为*p 的右子树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - rc-lchild = p; p = rc; /p 指向新的根结点 / 对以指针T所指结点为根结点的二叉树作左平衡旋转处理，/ 本算法结束时指针T指向新的根结点voidLeftBalance(BSTree&T) BSTreelc,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-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 作右旋平衡处理 / 右平衡旋转处理voidRightBalance(BSTree&T) BSTreerc,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 LH: T-bf=RH; rc-bf=EH; break; case EH: T-bf=rc-bf=EH; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - break; case RH: T-bf = EH; rc-bf=LH; break; ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); / 插入结点Status InsertAVL(BSTree&T,ElemTypee,int&taller)/taller反应 T长高与否if(!T)/ 插入新结点，树长高，置taller 为 true T= (BSTree) malloc (sizeof(BSTNode); T-data = e; T-lchild = T-rchild = NULL; T-bf = EH; taller = 1; else if(e = T-data) taller = 0; return 0; if(e data) if(!InsertAVL(T-lchild,e,taller)/未插入return 0; if(taller)/ 已插入到 *T 的左子树中且左子树长高switch(T-bf)/ 检查 *T 的平衡度，作相应的平衡处理case LH: LeftBalance(T); taller = 0; break; case EH: T-bf = LH; taller = 1; break; case RH: T-bf = EH; taller = 0; break; else if (!InsertAVL(T-rchild,e,taller) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - return 0; if(taller)/ 插入到 *T 的右子树且右子树增高switch(T-bf)/ 检查 *T 的平衡度case LH: T-bf = EH; taller = 0; break; case EH: T-bf = RH; taller = 1; break; case RH: RightBalance(T); taller = 0; break; return 1; void DELeftBalance(BSTree&T)/删除平衡调整BSTreelc,rd; lc=T-lchild; switch(lc-bf) case LH: T-bf = EH; /lc-bf= EH; R_Rotate(T); break; case EH: T-bf = EH; 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: T-bf=lc-bf=EH; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - - - - case RH: T-bf=EH; lc-bf=LH; break; rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); void DERightBalance(BSTree&T) /删除平衡调整 BSTreerc,ld; rc=T-rchild; switch(rc-bf) case RH: T-bf= EH; /rc-bf= EH; L_Rotate(T); break; case EH: T-bf= EH; /rc-bf= EH; L_Rotate(T); break; case LH: ld=rc-lchild; switch(ld-bf) case LH: T-bf=RH; rc-bf=EH; break; case EH: T-bf=rc-bf=EH; break; case RH: T-bf = EH; rc-bf=LH; break; ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - if(s-rchild) SDelete(T,s,s-rchild,shorter); if(shorter) switch(s-bf) case EH: s-bf = LH; shorter = 0; break; case RH: s-bf = EH; shorter = 1; break; case LH: DELeftBalance(s); shorter = 0; break; return; T-data = s-data; if(q != T) q-rchild = s-lchild; else q-lchild = s-lchild; shorter = 1; / 删除结点Status Delete(BSTree&T,int&shorter) BSTree q; if(!T-rchild) q = T; T = T-lchild; free(q); shorter = 1; else if(!T-lchild) q = T; T= T-rchild; free(q); shorter = 1; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - SDelete(T,T,T-lchild,shorter); if(shorter) switch(T-bf) case EH: T-bf = RH; shorter = 0; break; case LH: T-bf = EH; shorter = 1; break; case RH: DERightBalance(T); shorter = 0; break; return 1; Status DeleteAVL(BSTree&T,ElemTypee,int&shorter) int sign = 0; if (!T) return sign; else if(e = T-data) sign = Delete(T,shorter); return sign; else if(e data) sign = DeleteAVL(T-lchild,e,shorter); if(shorter) switch(T-bf) case EH: T-bf = RH; shorter = 0; break; case LH: T-bf = EH; shorter = 1; break; case RH: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - DERightBalance(T); shorter = 0; break; return sign; else sign = DeleteAVL(T-rchild,e,shorter); if(shorter) switch(T-bf) case EH: T-bf = LH; shorter = 0; break; case RH: T-bf = EH; break; case LH: DELeftBalance(T); shorter = 0; break; return sign; / 合并void merge(BSTree&T1,BSTree &T2) int taller = 0; if(!T2) return; merge(T1,T2-lchild); InsertAVL(T1,T2-data,taller); merge(T1,T2-rchild); / 分裂void split(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2) int taller = 0; if(!T) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - return; split(T-lchild,e,T1,T2); if(T-data e) InsertAVL(T2,T-data,taller); else InsertAVL(T1,T-data,taller); split(T-rchild,e,T1,T2); / 分裂voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2) BSTree t1 = NULL,t2 = NULL; split(T,e,t1,t2); T1 = t1; T2 = t2; return; / 构建voidCreatBSTree(BSTree&T) intnum,i,e,taller = 0; printf( 输入结点个数:); scanf(%d,&num); printf( 请顺序输入结点值n); for(i = 0 ;i rchild) PrintBSTree(T-rchild,lev+1); for(i = 0;i data); if(T-lchild) PrintBSTree(T-lchild,lev+1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - void Start(BSTree&T1,BSTree &T2) intcho,taller,e,k; taller = 0; k = 0; while(1) system(cls); printf( 平衡二叉树操作的演示nn); printf(*n); printf( 平衡二叉树显示区n); printf(T1 树n); if(!T1 ) printf(n 当前为空树 n); else PrintBSTree(T1,1); printf(T2 树n); if(!T2 ) printf(n 当前为空树 n); else PrintBSTree(T2,1); printf(n*n); printf(T1 操作： 1.创建2.插入3.查找4.删除10.分裂 n); printf(T2 操作： 5.创建6.插入7.查找8.删除11.分裂 n); printf( 9. 合并T1,T2 0.退出 n); printf(*n); printf( 输入你要进行的操作：); scanf(%d,&cho); switch(cho) case 1: CreatBSTree(T1); break; case 2: printf( 请输入要插入关键字的值); scanf(%d,&e); InsertAVL(T1,e,taller) ; break; case 3: printf( 请输入要查找关键字的值); scanf(%d,&e); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - if(SearchBST(T1,e) printf( 查找成功！ n); else printf( 查找失败！ n); printf( 按任意键返回87); getchar(); getchar(); break; case 4: printf( 请输入要删除关键字的值); scanf(%d,&e); if(DeleteAVL(T1,e,k) printf( 删除成功！ n); else printf( 删除失败！ n); printf( 按任意键返回); getchar(); getchar(); break; case 5: CreatBSTree(T2); break; case 6: printf( 请输入要插入关键字的值); scanf(%d,&e); InsertAVL(T2,e,taller) ; break; case 7: printf( 请输入要查找关键字的值); scanf(%d,&e); if(SearchBST(T2,e) printf( 查找成功！ n); else printf( 查找失败！ n); printf( 按任意键返回); getchar(); getchar(); break; case 8: printf( 请输入要删除关键字的值); scanf(%d,&e); if(DeleteAVL(T2,e,k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - printf( 删除成功！ n); else printf( 删除失败！ n); printf( 按任意键返回); getchar(); getchar(); break; case 9: merge(T1,T2); T2 = NULL; printf( 合并成功，按任意键返回); getchar(); getchar(); break; case 10: printf( 请输入要中间值字的值); scanf(%d,&e); splitBSTree(T1,e,T1,T2) ; printf( 分裂成功，按任意键返回); getchar(); getchar(); break; case 11: printf( 请输入要中间值字的值); scanf(%d,&e); splitBSTree(T2,e,T1,T2) ; printf( 分裂成功，按任意键返回); getchar(); getchar(); break; case 0: system(cls); exit(0); main() BSTree T1 = NULL; BSTree T2 = NULL; Start(T1,T2); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -