2022年平衡二叉树 .pdf

平衡二叉树目录摘要,1 一、引言 ,2 二、设计任务与目的 ,2 三、设计方案与实施 ,2 1、总体设计,2基本概念（包括设计到的概念）A.树的概念B.平衡二叉树的概念C.遍历的概念D.动态平衡技术的概念E.最小不平衡子树的概念构造算法插入结点删除结点中序遍历2、详细设计,8A.使用的头文件B.常量定义C.全局变量定义D.数据结构定义E.部分关键函数原型说明3、程序清单,104、程序调试与体会,235、运行结果（截图）,23四、结论,24 五、参考文献,24 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 26 页 - - - - - - - - - 数据结构课程设计- 1 - 摘要树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。树型结构在客观世界中广泛存在。而平衡二叉树因其特性，它在查找时拥有比普通二叉树更高的效率，所以它拥有很广泛的应用。关键词：二叉树，平衡二叉树，查找Abstract The tree structure is defined with the branch relation of layer structure, it is a important nonlinear structure. The tree structure is an extensive existence in the objective world. And because of its characteristic, it owns higher efficiency than general binary tree while in searching, so it is used extensively. Key words:Binary Tree , Balanced Binary Tree, Search 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 26 页 - - - - - - - - - 数据结构课程设计- 2 - 数据结构课程设计- 平衡二叉树的生成设计一、引言平衡二叉树是数据结构中一个非常重要的概念。它对二叉树的优化和提高查询效率有重要的作用，它是动态查找的一个非常重要方法，它在实际生产中有着广泛的应用。二、设计目的与任务通过本课程设计教学所要求达到的目的是：充分理解和掌握二叉树、平衡二叉树的相关概念和知识。掌握平衡二叉树的生成、结点删除、插入等操作过程，并编程实现从键盘上输入一系列数据（整型） ，建立一棵平衡二叉树，任意插入或删除一个结点后仍然要求构成平衡二叉树，并按中序遍历输出这棵平衡二叉树。三、设计方案与实施1、总体设计基本概念（包括设计到的概念）树的概念树（Tree）是 n（n=0 ）个结点的有限集。在任意一棵非空树中：1)有且仅有一个特定的称为根的结点；2)当 n1 时，其余结点可分为m（m0 ）个互不相交的有限集T1，T2.Tm ，其中每一个集合又是一棵树，并且称为根的子树（SubTree ） 。【例】如图1 所示：图 1 图 1 是有 8 个结点的树， 其中 A 是根， 其余结点分成2 个互不相交的子集：T1=B ，D ，T2=C ，E，F，G，H ；T1 和 T2 都是根 A 的子树，且本身也是一棵树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 26 页 - - - - - - - - - 数据结构课程设计- 3 - 平衡二叉树的概念形态匀称的二叉树称为平衡二叉树(Balanced binary tree) ，其严格定义是：若T 是一棵非空二叉树，其左、右子树为TL 和 TR ，令hl 和 hr 分别为左、右子树的深度。当且仅当TL 、 TR 都是平衡二叉树； hl hr 1；时，则T 是平衡二叉树。【例】如图2 所示：（a）平衡二叉树（b）非平衡二叉树图 2 平衡二叉树与非平衡二叉树相应地定义hl hr 为二叉平衡树的平衡因子(balance factor) 。因此，平衡二叉树上所有结点的平衡因子可能是-1 ， 0 ， 1 。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于 1 ，则该树是就平衡二叉树。遍历的概念遍历二叉树指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。由二叉树的递规定义可知，二叉树的3 个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这3 部分，便是遍历了整个二叉树。动态平衡技术的概念Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL 树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 26 页 - - - - - - - - - 数据结构课程设计- 4 - 为了保证二叉排序树的高度为lgn ，从而保证二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn) ， 在往树中插入或删除结点时，要调整树的形态来保持树的平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn) ，从而确保树上的基本操作在最坏情况下的时间均为 O(lgn) 。注意：1)任一结点的左右子树的高度均相同(如满二叉树 )，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn) ，就可看作是平衡的。2)平衡的二叉排序树指满足BST 性质的平衡二叉树。3)AVL 树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n 个结点的AVL 树的高度约为1.44lgn 。而完全平衡的二叉树度高约为lgn，AVL 树是接近最优的。最小不平衡子树的概念以离插入结点最近、且平衡因子绝对值大于1 的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为A ，则调整该子树的规律可归纳为下列四种情况：图 3 平衡调整的4 种基本类型（结点旁的数字是平衡因子）（1） LL 型：新结点X 插在 A 的左孩子的左子树里。调整方法见图3（a） 。图中以B 为轴心，将A 结点从B 的右上方转到B 的右下侧，使A 成为 B 的右孩子。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 26 页 - - - - - - - - - 数据结构课程设计- 5 - （2）RR 型：新结点X 插在 A 的右孩子的右子树里。调整方法见图3(b) 。图中以B 为轴心，将A 结点从B 的左上方转到B 的左下侧，使A 成为 B 的左孩子。（3）LR 型：新结点X 插在A 的左孩子的右子树里。调整方法见图3(c) 。分为两步进行：第一步以X 为轴心，将B 从 X 的左上方转到X 的左下侧，使B 成为X 的左孩子，X 成为 A 的左孩子。第二步跟LL 型一样处理( 应以 X 为轴心) 。（4）RL 型：新结点X 插在 A 的右孩子的左子树里。调整方法见图3(d) 。分为两步进行： 第一步以X 为轴心，将B 从 X 的右上方转到X 的右下侧，使B 成为X 的右孩子，X 成为A 的右孩子。第二步跟 RR 型一样处理( 应以 X 为轴心) 。构造算法我们希望由任何初始序列构成的二叉排序树都是AVL 树。因为 AVL 树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的（其中N 为结点数）。由此，它的平均查找长度也是和logN同数量级的。如何使构成的二叉排序树成为平衡树呢？先看一个具体的例子（常见图 4） 。假设表中关键字序列为（ 13，24，37 ，90，53） 。空树和1 个结点 13 的树显然都是平衡的二叉树。在插入24 之后依是平衡的，只是根结点的平衡因子BF 由 0 变为 1；在继续插入37 之后，由于结点13 的 BF 值由 1 变成 2，由此出现不平衡现象。此时好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由13 改成至 24，扁担的两头就平衡了。由此，可以对树左一个向左逆时针“旋转”的操作，令结点24为根，而结点13 为它的左子树，此时，结点13 和 24 的平衡因子都为0，而且依保持二叉排序树的特性。在继续插入90 和 53 之后，由于结点37 的 BF 值由 1 变成 2，排序树中出现了新的不平衡现象，需要调整。当此时由于结点53 插在结点 90 结点的左子树上，因此不能和上作简单调整。对于以结点 37 为根的子树来说，即要保持二叉排序树的特性，又要平衡，则必须以53 作为根结点，而使37 为它的左子树的根，90 成为它的左子树的根。这好比对树作了两次“旋转”操作先向右顺时针，后向左逆时针（见图4（f）（ h） ） ，使二叉排序树由不平衡转化为平衡。一般情况下，假设由于在二叉排序树上插入结点而失去平衡后进行调整的规律可归纳为最小不平衡子树的概念中提到的 4 中操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 26 页 - - - - - - - - - 数据结构课程设计- 6 - 013-113037013024037-124-21302401324053190-237013-224053-12490533713090037(a)(b)(c)(d)(e)(f)(g)(h)图 4 平衡二叉树的生成过程（a）空树；（b）插入 13； （ c）插入 24； （d）插入 37； （e）向左逆时针右旋转平衡；（f）相继插入 90 和 53； （g）第一次向右顺时针旋转；（h）第二次向左逆时针旋转平衡4 种插入中，（1）和（ 3）对称，（2）和（ 4）对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小到大有序”证明之。当平衡二叉树因插入或者删除结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入或删除之前相同，因而不影响插入或删除路径上所有祖先结点的平衡。插入结点在平衡二叉排序树BBST上插入一个新数据元素e 的递规算法可以描述如下：(1)若 BBST为空树，则插入一个数据元素为e 的新结点作为BBST的根结点，树的深度增加1；(2)若 e 的关键字和BBST的根结点的关键字相等，则不进行插入；(3)若 e 的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e 有相同关键字的结点， 则将 e 插入在 BBST的左子树上， 并且当插入之后的左子树深度增加1 时，分别就下列情况处理之：1.BBST的根结点的平衡因子为1（右子树深度大于左子树深度）：则将根结点的平衡因子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 26 页 - - - - - - - - - 数据结构课程设计- 7 - 更改为 0， BBST的深度不变；2.BBST的根结点的平衡因子为0 （左，右子树深度相等） ：则将根结点的平衡因子更改为1，BBST的深度增加1；3.BBST的根结点的平衡因子为1（左子树深度大于右子树深度）：若 BBST的左子树根结点的平衡因子为1，则需要进行单向右旋平衡处理，并且在右旋处理之后将根结点和右子树根结点的平衡因子更改为0，树的深度不变；若 BBST的左子树根结点的平衡因子为1，这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；(4)若 e 的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e 相同关键字的结点， 则将 e 插入在 BBST的右子树上， 并且当插入之后的右子树深度增加1 时，分别就不同情况处理。删除结点删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树- 找到要删除的结点- 删除一个结点 - 变成二叉树 - 旋转 - 变回平衡二叉树。具体过程将详细设计中的代码。中序遍历右遍历的定义可知，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则1)中序遍历左子树2)访问根结点3)中序遍历右子树如中序遍历图5 的二叉树，结点的访问顺序为：abcdefg图 5 2、详细设计A.使用的头文件#include #include /cout 函数要使用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 26 页 - - - - - - - - - 数据结构课程设计- 8 - #include /setw 函数要使用B.常量定义# define LH 1 /左高# define EH 0 /等高# define RH -1 /右高# define TRUE 1 # define FALSE 0 C.全局变量定义int taller=0; /taller 反映 T 长高与否int shorter=0; /shorter 反映 T 变矮与否D.数据结构定义/根据平衡二叉树特点可以定义平衡二叉树的存储结构/二叉排序树的类型定义typedef struct BSTNode int data; /结点值int bf; /结点的平衡因子struct BSTNode * lchild, * rchild; /分别指向左右孩子的指针BSTNode, *BSTree; /同时声明一个BSTNode 和一个指针类型的*BSTree E.部分关键函数原型说明void MidOrder(BSTree T) / 树的中序遍历的递归算法, 一并输出它的平衡因子和左右结点值，不返回值BSTree R_Rotate(BSTree p) / 对以 p 为根的二叉排序树作右旋处理，处理之p 指向新的树根结点即旋转处理之前的左子树根结点BSTree L_Rotate(BSTree p) / 对以 p 为根的二叉排序树作左旋处理，处理之p 指向新的树根结点即旋转处理之前的右子树根结点BSTree LeftBalance(BSTree T) / 对以指针 T所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree RightBalance(BSTree T) / 对以指针 T所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree InsertAVL(BSTree T, int e) / 向平衡树中插入一个结点，返回插入后的新根结点BSTree LeftBalance1(BSTree p) / 删除结点时对以指针T 所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree RightBalance1(BSTree p) / 删除结点时对以指针T 所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree Delete(BSTree q, BSTree r) / 对结点进行删除处理，本算法结束时指针q 指向新的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 26 页 - - - - - - - - - 数据结构课程设计- 9 - 根结点BSTree DeleteAVL(BSTree p, int e) / 找到要删除的结点, 并调用删除函数对其进行删除，本算法结束时指针p 指向新的根结点BSTree CreatNode(int nodeValue) / 建立关键字值为nodeValue 的新结点，返回根结点3、程序清单#include #include /cout #include /setw # define LH 1 /左高# define EH 0 /等高# define RH -1 /右高# define TRUE 1 # define FALSE 0 int taller=0; /taller 反映 T 长高与否int shorter=0; /shorter 反映 T 变矮与否/二叉排序树的类型定义typedef struct BSTNode int data; /结点值int bf; /结点的平衡因子struct BSTNode * lchild, * rchild; /分别指向左右孩子的指针BSTNode, *BSTree; /同时声明一个BSTNode 和一个指针类型的*BSTree /树的中序遍历的递归算法,一并输出它的平衡因子和左右结点值void MidOrder(BSTree T) /中序遍历的特点是：当二叉树为空，则空操作；否则/1.中序遍历左子树；/2.访问根结点；/3.中序遍历右子树。if(T-lchild) MidOrder(T-lchild); if(T-data) /以适当的形式格式化输出各个结点及其附加信息可以方便用户重构二叉树coutsetw(4)datasetw(6)bf; if (T-lchild ) coutsetw(8)lchild-data; else coutsetw(8)rchild ) coutsetw(8)rchild-data; else coutsetw(8)-; coutrchild) MidOrder(T-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 26 页 - - - - - - - - - 数据结构课程设计- 10 - /树的先序遍历的递归算法,一并输出它的平衡因子和左右结点值void RootOrder(BSTree T) /先序遍历的特点是：当二叉树为空，则空操作；否则/1.访问根结点；/2.先序遍历左子树；/3.先序遍历右子树。if(T-data) coutsetw(4)datasetw(6)bf; if (T-lchild ) coutsetw(8)lchild-data; else coutsetw(8)rchild ) coutsetw(8)rchild-data; else coutsetw(8)-; coutlchild) RootOrder(T-lchild); if(T-rchild) RootOrder(T-rchild); /对以 p 为根的树作右旋处理，处理之p 指向新的树根结点即旋转处理之前的左子树根结点BSTree R_Rotate(BSTree p) BSTNode *lc; /声明 BSTNode* 临时变量lc=p-lchild; /lc 指向的 *p 的左子树根结点p-lchild=lc-rchild; /lc 的右子树挂接为*p 的左子树lc-rchild=p; p=lc; /p 指向新的根结点return p; /返回新的根结点 /对以 p 为根的树作左旋处理，处理之p 指向新的树根结点即旋转处理之前的右子树根结点BSTree L_Rotate(BSTree p) BSTNode *rc; /声明 BSTNode* 临时变量rc=p-rchild; /rc 指向的 *p 的右子树根结点p-rchild=rc-lchild; /rc 的左子树挂接为*p 的右子树rc-lchild=p; p=rc; /p 指向新的根结点return p; /返回新的根结点 /对以指针 T 所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree LeftBalance(BSTree T) BSTNode *lc,*rd; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 26 页 - - - - - - - - - 数据结构课程设计- 11 - lc=T-lchild; /lc 指向 *T 的左子树根结点switch(lc-bf) /检查 *T 的左子树平衡度，并做相应的平衡处理 case LH: /新结点插入在 *T 的左孩子的左子树上，要做单右旋处理T-bf=lc-bf=EH; T=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; T-lchild=L_Rotate(T-lchild); /对*T 的左孩子做左旋平衡处理T=R_Rotate(T); /对*T 做右旋处理 return T; /对以指针 T 所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree RightBalance(BSTree T) BSTree rc,ld; rc=T-rchild; /rc 指向 *T 的右子树根结点switch(rc-bf) /检查 *T 的右子树平衡度，并做相应的平衡处理 case RH: /新结点插入在 *T 的右孩子的右子树上，要做单右旋处理T-bf=rc-bf=EH; T=L_Rotate(T); break; case LH: /新结点插入在 *T 的右孩子的左子树上，要做双旋处理ld=rc-lchild; /ld 指向 *T 的右孩子的左子树根switch(ld-bf) /修改 *T 及其右孩子的平衡因子 case LH: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 26 页 - - - - - - - - - 数据结构课程设计- 12 - T-bf=LH; rc-bf=EH; break; case EH: T-bf=rc-bf=EH; break; case RH: T-bf=EH; rc-bf=RH; break; ld-bf=EH; T-rchild=R_Rotate(T-rchild); /对*T 的右孩子做右旋平衡处理T=L_Rotate(T); /对*T 做左旋处理 return T; /若在平衡的二叉排序树T 中不存在和e 有相同关键字的结点,则插入一个数据元素为e的新结点 ,并返回插入后所建成的平衡二叉排序树,否则返回NULL. 若因插入而使二叉数失去平衡,则作平衡旋转处理 ,布尔变量 taller 反映 T 长高与否BSTree InsertAVL(BSTree T, int e) BSTree p; /插入新结点，树长高置taller 为 TRUE if(!T) T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=TRUE; else /树中存在和e 有相同关键字的结点则不再插入if(e=T-data) taller=FALSE; return NULL; /值小于则继续在树的左子树中搜索if(e data) p=InsertAVL(T-lchild,e); /插入到左子树且左子树长高if(p) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 26 页 - - - - - - - - - 数据结构课程设计- 13 - T-lchild=p; if(taller) switch(T-bf) /检查 *T 的平衡度 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 的右子树中搜索else /插入到右子树且使右子树长高p=InsertAVL(T-rchild,e); if (p) T-rchild=p; if(taller) switch(T-bf) /检查 *T 的平衡度 case LH: /原本左子树比右子树高，现在左右子树等高T-bf=EH; taller=FALSE; break; case EH: /原本左、右子树同高，现因右子树增高而使树增高T-bf=RH; taller=TRUE; break; case RH: /原本右子树比左子树高，需要做右平衡处理T=RightBalance(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 26 页 - - - - - - - - - 数据结构课程设计- 14 - taller=FALSE; break; return T; /删除结点时对以指针p 所指结点为根的树作左平衡旋转处理，本算法结束时指针p 指向新的根结点BSTree LeftBalance1(BSTree p) BSTree p1,p2; /左子树比右子树高if(p-bf=1) p-bf=0; shorter=1; else if(p-bf=0) p-bf=-1; shorter=0; else p1=p-rchild; if(p1-bf=0) p-rchild = p1-lchild; p1-lchild = p; p1-bf = 1; p-bf = -1; p = p1; shorter = 0; else if(p1-bf=-1) p-rchild=p1-lchild; p1-lchild=p; p1-bf=p-bf=0; p=p1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 26 页 - - - - - - - - - 数据结构课程设计- 15 - shorter=1; else 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; p1-bf=-1; p2-bf=0; p=p2; shorter=1; return p; /删除结点时对以指针T 所指结点为根的二叉树作右平衡旋转处理，本算法结束时指针T 指向新的根结点BSTree RightBalance1(BSTree p) BSTree p1,p2; if(p-bf=-1) p-bf=0; shorter=1; else if(p-bf=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 26 页 - - - - - - - - - 数据结构课程设计- 16 - p-bf=1; shorter=0; else p1=p-lchild; if(p1-bf=0) p-lchild = p1-rchild; p1-rchild = p; p1-bf=-1; p-bf=1; p=p1; shorter=0; else if(p1-bf=1) p-lchild=p1-rchild; p1-rchild=p; p1-bf=p-bf=0; p=p1; shorter=1; else p2=p1-rchild; p1-rchild = p2-lchild; p2-lchild = p1; p-lchild = p2-rchild; p2-rchild = 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; p1-bf=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 26 页 - - - - - - - - - 数据结构课程设计- 17 - p2-bf=0; p=p2; shorter=1; return p; /对结点进行删除处理BSTree Delete(BSTree q, BSTree r) if(r-rchild=NULL) /根结点的右子树为空则将左子树提高并标记树变矮了 q-data=r-data; q=r; r=r-lchild; free(q); shorter=1; else /继续递规搜索并删除 r-rchild=Delete(q,r-rchild); return r; /找到要删除的结点,并调用删除函数对其进行删除BSTree DeleteAVL(BSTree p, int e) BSTree q; /抛弃空删除if(p=NULL) return NULL; else if(e data) /欲删除值小于当前结点值则继续在左子树中搜索 p-lchild = DeleteA VL(p-lchild,e); if(shorter=1) p=LeftBalance1(p); return p; else if(e p-data) /欲删除值大于当前结点值则继续在右子树中搜索 p-rchild=DeleteA VL(p-rchild,e); if(shorter=1) p=RightBalance1(p); return p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 26 页 - - - - - - - - - 数据结构课程设计- 18 - else /找到了 q=p; /将 p 存储到临时变量q 里面if(p-rchild=NULL) /如果 p 的右子树为空则将其左子树提高一层 p=p-lchild; free(q); shorter=1; /并标记树变矮了 else /如果 p 的左子树为空则将其右子树提高一层if(p-lchild=NULL) p=p-rchild; free(q); shorter=1; else /将删除后的子树后的得到的新的子树的根结点赋值给q 左子树q-lchild=Delete(q,q-lchild); /如果树高到变矮了则要执行删除后的左平衡处理if(shorter=1) q=LeftBalance1(q); p=q; return p; /建立新结点BSTree CreatNode(int nodeValue) BSTree node; node = (BSTree)malloc(sizeof(BSTree); node-data = nodeValue; node-bf = 0; node-lchild = NULL; node-rchild = NULL; return node; /在屏幕打印菜单函数int PrintMenu() int userChose; cout - endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 26 页 - - - - - - - - - 数据结构课程设计- 19 - cout 1. 创建一棵二叉平衡树 endl; cout 2. 向平衡树插入新结点 endl; cout 3. 从树中删除一个结点 endl; cout 4. 中序遍历输出平衡树 endl; cout 5. 先序遍历输出平衡树 endl; cout n. 选择其它将退出程序 endl; cout - endl; cout userChose; return userChose; /新建二叉树函数BSTree BuildTree(BSTree r) /如果传入根结点不为空，则树已构建过，退出函数if (r != NULL) cout 二叉平衡树已经创建!; return NULL; /根结点为空则开始构建cout 请输入结点值，输入零则结束 nodeValue; while (nodeValue) /插入任何不为0 的整数值 BSTree node = CreatNode(nodeValue); / /如果根为空，则将此结点设置为根结点，否则将此结点作为非根结点插入if (r = NULL) r = node; else r=InsertAVL(r,nodeV alue); cin nodeValue; /获取用户输入的新值 return r; void main() /定义一个空根结点BSTree root=NULL; /在屏幕打印菜单，让用户选择建立、遍历、插入、删除等功能int userChoseMenu; int e; while (userChoseMenu = PrintMenu() /根据用户不同选择作出不同处理switch (userChoseMenu) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 26 页 - - - - - - - - - 数据结构课程设计- 20 - case 1 : cout 你选择了 1，请依次输入新树的值，回车输入下一个，遇0 结束输入。 endl; root = BuildTree(root); break; case 2 : cout 你选择了 2，请输入要插入的结点值！ e; root = InsertAVL(root,e); break; case 3 : cout 你选择了 3，请输入要删除的结点值！ e; root = DeleteAVL(root,e); break; case 4 : cout 你选择了 4，中序遍历输出二叉平衡树。 endl; cout-endl; cout 数据 平衡因子 左子树 右子