.
平衡二叉树操作的演示
1. 需求分析
本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。 具体功能：
（1） 初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂
六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。
（2） 平衡二叉树的显示采用凹入表现形式。 （3） 合并两棵平衡二叉树。
（4） 把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等
于x，另一棵树中的任一关键字都大于x。
如下图：
2．概要设计
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
word 资料
.
具体步骤：
（1） 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的
祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；
（2） 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树
的根结点；
（3） 判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整； （4） 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，
应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
（5） 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点
的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。 流程图
3. 详细设计
二叉树类型定义： typedef int Status; typedef int ElemType; typedef struct BSTNode{
word 资料
.
ElemType data; int bf;
struct BSTNode *lchild ,*rchild; } BSTNode,* BSTree;
Status SearchBST(BSTree T,ElemType e)//查找 void R_Rotate(BSTree &p)//右旋 void L_Rotate(BSTree &p)//左旋
void LeftBalance(BSTree &T)//插入平衡调整 void RightBalance(BSTree &T)//插入平衡调整
Status InsertAVL(BSTree &T,ElemType e,int &taller)//插入 void DELeftBalance(BSTree &T)//删除平衡调整 void DERightBalance(BSTree &T)//删除平衡调整 Status Delete(BSTree &T,int &shorter)//删除操作
Status DeleteAVL(BSTree &T,ElemType e,int &shorter)//删除操作 void merge(BSTree &T1,BSTree &T2)//合并操作
void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2)//分裂操作 void PrintBSTree(BSTree &T,int lev)//凹入表显示
附录
源代码：
#include
word 资料
数据结构平衡二叉树的操作演示
