实验四 平衡二叉树演示1. 问题定义及需求分析1.1课题目的和任务问题描述：利用平衡二叉树设计动态查找表。实验要求：设计平衡二叉树的动态演示的模拟程序。1）采用平衡二叉树存储结构。2）完成平衡二叉树的创建、查找、插入和删除的演示操作。3）可以考虑两棵平衡二叉树的合并。1.2数据形式输入数据形式：通过键盘输入数据输入值的范围：树中元素的值为float型，范围为1.2e-38至3.4e+38；树的名称为char类型数据，可以输入字母，数字和符号，但是长度必须在20位以内；对菜单进行操作时，输入数据长度必须在200以内，且有效的输入数据为0至7，其中0为退出程序，1至7为对应菜单的操作选项。输出数据形式：输出到显示器。1.3程序功能创建平衡二叉树存储结构，通过平衡因子，使二叉排序树达到平衡，提供平衡二叉树的创建、查找和删除，树中元素的查找、插入和删除等基本功能，可以实现创建多棵平衡二叉树，并且能够进行两棵树的合并。通过平衡二叉树，能够使树时刻保持平衡，从而提高在树中遍历数据的速度，具有重要意义。1.4测试数据1 /创建平衡二叉树2 /输入创建树的个数t1 /输入第一个树的名称5 /输入第一个树中元素的个数5 2 6 8 9 /依次输入各个元素t2 /输入第二个树的名称5 /输入第二个树中元素的个数3 1 4 10 7 /依次输入各个元素5 /层次遍历输出第一个树的结构图t1 /操作树名5 /层次遍历输出第二个树的结构图t2 /操作树名3 /插入元素操作t1 /操作树名1 /插入元素个数7 /依次插入元素5 /层次遍历输出树的结构图t1 /操作树名4 /删除元素操作t2 /操作树名1 /删除元素个数7 /依次删除元素5 /层次遍历输出树的结构图t2 /操作树名6 /合并两个树操作t1 t2 /操作树名5 /层次遍历输出树的结构图t1 /操作树名2 /查询元素操作t1 /操作树名5 /需要查询的元素（该元素树中存在）2 /查询元素操作t1 /操作树名11 /需要查询的元素（该元素树中不存在）7 /删除二叉平衡树操作t1 /操作树名2 /查询操作t1 /操作树名（会提示该树不存在，说明删除树成功）0 /退出程序2. 概要设计2.1抽象数据类型需要定义一个树的结构类型，其中包含数据类型，它的左右孩子指针，以及平衡因子，平衡因子的取值为-1,0,1三种，分别对应树的右边高（RH），平衡（EH）和左边高（LH）三种情形，通过平衡因子的判别，来调整树的高度使其达到平衡；另外需要用到双向链表的数据结构，以及队列的数据结构。2.2主程序流程及各模块之间的调用关系3. 详细设计3.1存储结构实现typedef struct Type/数据类型结构 float num;Type;/*平衡树结构声明*/typedef struct AVLTree/二叉平衡树结构体声明 int bf;/结点的平衡因子 struct Type data;/结点数据 struct AVLTree* lchild,* rchild;/左右孩子AVLTree,*AVL;/*队列结构声明*/typedef struct QNode/队列 AVL tree; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;/*双向链表结构声明*/typedef struct LNode/链表 AVL t; char tree_nameNAME_LENGTH; struct LNode* prior,* next;LNode,*Link;3.2负责模块的伪码算法（1）void LeftBalance(AVL& t)/左部平衡化处理 l=t-lchild; switch(l-bf) /检查T的左子树平衡度，并作相应的平衡处理 case LH:/新节点插入在T的左孩子的左子树上，做单右旋处理 调整平衡因子;R_Rotate(t);break; case EH:/deleteAVL需要，insertAVL用不着 调整平衡因子;R_Rotate(t);break; case RH:/新插入节点在T的左孩子的右子树上，做双旋处理 lr=l-rchild; switch(lr-bf) case LH: 调整平衡因子;break; case EH: 调整平衡因子;break; case RH: 调整平衡因子;break; 调整平衡因子; L_Rotate(t-lchild); R_Rotate(t); （2）void RightBalance(AVL& t)/右部平衡化处理 r=t-rchild; switch(r-bf) case RH:/新节点插在T的右孩子的右子树上，要做单左旋处理 调整平衡因子;L_Rotate(t);break; case EH:/deleteAVL需要，insertAVL用不着 调整平衡因子;L_Rotate(t);break; case LH:/新节点插在T的右孩子的左子树上，要做双旋处理 rl=r-lchild; switch(rl-bf) case LH: 调整平衡因子;break; case EH: 调整平衡因子;break; case RH: 调整平衡因子;break; 调整平衡因子; R_Rotate(t-rchild); L_Rotate(t); （3）void R_Rotate(AVL& t)/以T为根节点的二叉排序树进行右旋转 l=t-lchild;/将t的左孩子给l t-lchild=l-rchild;/将l的右孩子给t的左孩子指针 l-rchild=t;/将t变成l的右孩子 t=l;/指向新的节点l（4）void L_Rotate(AVL& t)/以T为根节点的二叉排序树进行左旋转 r=t-rchild; t-rchild=r-lchild; r-lchild=t; t=r;（5）int DeleteTree(AVL& t,Type e,int& shorter)/平衡二叉树的结点删除 if(t=NULL)/不存在该元素 return 0;/删除失败 else if(e=t-data)/找到元素结点 q=NULL; if(t-lchild=NULL)/左子树为空将右子树接上，删除该点; shorter=1; else if(t-rchild=NULL)/右子树为空将左子树接上，删除该点; shorter=1; else/左右子树都存在 q=t-lchild; while(q-rchild)/找到要删除结点t的左孩子的最右孩子q q=q-rchild; t-data=q-data;/把q的值给t DeleteTree(t-lchild,q-data,shorter);/在左子树中递归删除前驱结点。即查找q的值 if(shorter)/如果树变矮了，调节平衡因子 switch(t-bf) case LH:t-bf=EH;shorter=1;break; case EH:t-bf=RH;shorter=0;break; case RH: if(t-rchild-bf=EH) shorter=0; else shorter=1; RightBalance(t);/右平衡处理 break; else if(edata)/左子树中继续查找 if(!DeleteTree(t-lchild,e,shorter) return 0; if(shorter) switch(t-bf) case LH:t-bf=EH;shorter=1;break; case EH:t-bf=RH;shorter=0;break; case RH: if(t-rchild-bf=EH) shorter=0; else