数学与计算机学院计算机系数据构造程序设计报告平衡二叉树同学姓名：*学好：1004681028班级：计算机系 102 指导教师：* 报告日期：2021/6/2622名目1. 平衡二叉树31.1 平衡二叉树的定义31.2 平衡二叉树的构造31.3 平衡二叉树查找的分析32. 程序功能33. 程序构造类型34. 程序函数45. 算法思想55.1 推断二叉树的旋转方法55.2 平衡旋转处理55.3 在平衡二叉树中插入元素55.4 在平衡二叉树中删除元素55.5 输出平衡二叉树树形55.6 销毁平衡二叉树56. 程序设计总结97. 完毕语108. 附录：程序清单101. 平衡二叉树1.1 平衡二叉树的定义平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称 AVL树。它或者是一颗空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树 和右子树的深度之差确实定值不超过 1。假设将二叉树上结点的平衡因子 BF(Balanced Factor) 定义为该结点的左子树的深度减去它的右子树的深度，那么平衡二叉树上全部结点的平衡因 子之可能是-1、0 和 1。只要二叉树上有一个结点的平衡因子确实定值大于 1，那么该二叉树就是不平衡的。1.2 平衡二叉树的构造构造一颗平衡二叉树的过程就是将一颗空树从根结点起，逐步插入或删除结点并不断对此树进展平衡化。在构造平衡二叉树的过程中有插入和删除两大操作。在树中进展插入和删除操作都可使树失去平衡，然而要让二叉排序树由不平衡转化为平衡，操作就是对二叉树进展旋转，旋转的过程将在算法思想中具体介绍。1.3 平衡二叉树查找的分析在平衡二叉树上进展查找的过程和二叉排序树一样，因此，在查找过程中和给定值进展比较的关键字个数不超过树的深度。因此，在平衡二叉树上进展查找的时间简单度为O(log n).2. 程序功能请选择:本程序的功能就是将二叉排序树转变为平衡二叉树，其操作有:创立二叉树、插入数据、删除数据、输出、销毁二叉树和退出。1创建二叉树2插入数据3删除数据4输出5销毁二叉树0退出3. 程序构造类型在本程序中主要用到两个构造类型：构造体和队列。二叉树是链式存储构造，故用构造体来定义其构造。队列是用作输出二叉树的树形层序输出。4. 程序函数4.1 main()函数：（1） 函数原形：void main()（2） 功能：显示总菜单，调用子函数4.2 Create()函数:（1） 函数原形：void Create(BSTree &T)（2） 功能：实现二叉树的创立4.3 Insert()函数:（1） 函数原形：void Insert(BSTree &T)（2） 功能：实现在二叉树中插入数据4.4 InsertAVL()函数:（1） 函数原形：int InsertAVL(BSTree &T,int e,int &taller)（2） 功能：插入结点，并将二叉树平衡化4.5 DeleteMenu()函数:（1） 函数原形：void DeleteMenu(BSTree &T)（2） 功能：实现在二叉树中删除数据4.6 DeleteAVL()函数:（1） 函数原形：int DeleteAVL(BSTree &T,int e,int &shorter)（2） 功能：删除结点，并将二叉树平衡化4.7 Delete()函数:（1） 函数原形：int Delete(BSTree &p)（2） 功能：实现删除结点4.8 Search()函数:（1） 函数原形：void Search(BSTree &T,int e,int key)（2） 功能：在树中查找和关键字相等的结点4.9 R_Rotate()函数:（1） 函数原形：void R_Rotate(BSTree &p)（2） 功能：对以*p 为根结点的子树进展右旋平衡处理4.10 L_Rotate()函数:（1） 函数原形：void L_Rotate(BSTree &p)（2） 功能：对以*p 为根结点的子树进展左旋平衡处理4.11 RightBalance()函数:（1） 函数原形：int RightBalance(BSTree &T)（2） 功能：对以指针T 所指结点为根的二叉树作右平衡旋转处理4.12 LeftBalance()函数:（1） 函数原形：int LeftBalance(BSTree &T)（2） 功能：对以指针T 所指结点为根的二叉树作左平衡旋转处理4.13 Output()函数:（1） 函数原形：void Output(BSTree T)（2） 功能：将二叉树按中序和层序输出4.14 Inordertraverse()函数:（1） 函数原形：void Inordertraverse(BSTree T)（2） 功能：将二叉树按中序输出4.15 Depth()函数:（1） 函数原形：void Depth(BSTree p,int n,int &num)（2） 功能：求二叉树的深度4.16 Levelordertraverse()函数:（1） 函数原形：int Levelordertraverse(Stack &Q)（2） 功能：将二叉树按层序输出4.17 Initstack()函数:（1） 函数原形：int Initstack(Stack &Q)（2） 功能：构造一个空队列4.18 Push()函数:（1） 函数原形：int Push(Stack &Q,BSTree e)（2） 功能：插入元素 e 为新的队尾元素4.19 Pop()函数:（1） 函数原形：int Pop(Stack &Q,BSTree &q)（2） 功能：删除对头元素4.20 Destroy()函数:（1） 函数原形：void Destroy(BSTree &T)（2） 功能：将队列销毁5. 算法思想5.1 推断二叉树的旋转方法在一颗平衡二叉树中插入或删除一个结点后，假设二叉树失去平衡，那么需将二叉树进展 平衡化处理，简而言之，就是对不平衡的二叉树进展旋转处理。假设在二叉排序树中插入 或删除结点而失去平衡的最小子树根结点的指针为T(即 T 是离插入或删除结点最近，且平衡因子确定值超过 1 的祖先结点)，指针p 指向结点T 的左子树的根结点，指针q 指向结点T 的右子树的根结点，那么推断方法如下：(1) 假设结点 T 的平衡因子为 2，结点 p 的平衡因子为 1，那么需对结点 T 进展单向右旋平衡处理；(2) 假设结点 T 的平衡因子为-2，结点 p 的平衡因子为-1，那么需对结点 T 进展单向左旋平衡处理；(3) 假设结点 T 的平衡因子为 2，结点 p 的平衡因子为-1，那么需先对结点 p 进展单向左旋平衡处理，再对结点 T 进展单向右旋平衡处理，将这两步简称为对结点 T 进展双向旋转(先左后右) 平衡处理；(4) 假设结点 T 的平衡因子为-2，结点p 的平衡因子为 1，那么需先对结点p 进展单向右旋平衡处理，再对结点 T 进展单向左旋平衡处理，将这两步简称为对结点 T 进展双向旋转(先右后左) 平衡处理；5.2 平衡旋转处理假设由于在二叉排序树上插入或删除结点而失去平衡的最小子树根结点的指针为 T即 T 为里插入结点最近，且平衡因子确定值超过 1 的祖先结点，那么失去平衡后进展平衡处理有如下 4 种状况：(1) 单向右旋平衡处理：假设指针p 指向以*T 为根的左子树的根结点，将*p 的右子树作为*T 的左子树，再将以*T 为根的树作为*p 的右子树，如图a所示。图(a)(2) 单向左旋平衡处理：假设指针 p 指向以*T 为根的右子树的根结点，将*p 的左子树作为*T 的右子树，再将以*T 为根的树作为*p 的左子树，如图b所示。 图(b)图(c)(3) 双向旋转先左后右平衡处理：假设p 指向以*T 为根的左子树的根结点，q 以*p 为根的右子树的根结点，那么先将以*p 为根结点的树进展单向左旋，再将以*q 为根结点的树进展单向右旋，如图c所示。(4) 双向旋转先右后左平衡处理：假设 p 指向以*T 为根的右子树的根结点，q 以*p 为根的左子树的根结点，那么先将以*p 为根结点的树进展单向右旋，再将以*q 为根结点的树进展单向左旋，如图d所示。图(d)5.3 在平衡二叉树 BBST 中插入元素在平衡的二叉排序树上插入一个新的数据元素e：(1) 假设 BBST 为空树，那么插入一个数据元素 e 的新结点作为BBST 的根结点， 树的深度增 1；(2) 假设 e 的关键字和 BBST 的根结点的关键字相等，那么不进展插入；(3) 假设 e 的关键字小于 BBST 的根结点的关键字，而且在 BBST 的左子树中不存在和e 有一样关键字的结点，那么将e 插入在 BBST 的左子树上，并且当插入之后的左子树深度增加+1时，分别就以下不同状况处理：BBST 的根结点的平衡因子为-1右子树的深度大于左子树的深度：那么将根结点的平衡因子更改为 0，BBST 的深度不变；BBST 的根结点的平衡因子为 0,左、右子树的深度相等：那么将根结点的平衡因子更改为 1，BBST 的深度增 1；BBST 的根结点的平衡因子为 1左子树的深度大于右子树的深度：假设 BBST 的左子树的平衡因子为 1，那么需进展单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为 0，树的深度不变；假设 BBST 的左子树根结点的平衡因子为-1， 那么需进展先向左、后先向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其 左、右子树根结点的平衡因子，树的深度不变；(4) 假设 e 的关键字大于 BBST 的根结点的关键字，而且 BBST 的右子树不存在和e 有一样关键字的结点，那么将e 插入在 BBST 的右子树上，并且当插入之后的右子树深度增加+1 时，分别就不同状况处理：BBST 的根结点的平衡因子为 1左子树的深度大于右子树的深度：那么将根结点的平衡因子更改为 0，BBST 的深度不变；BBST 的根结点的平衡因子为 0,左、右子树的深度相等：那么将根结点的平衡因子更改为-1，BBST 的深度增 1；BBST 的根结点的平衡因子为-1右子树的深度大于左子树的深度：假设 BBST 的左子树的平衡因子为-1，那么需进展单向左旋平衡处理，并且在左旋处理之后，将根结点和其