《实验四 平衡二叉树演示》由会员分享，可在线阅读，更多相关《实验四 平衡二叉树演示（40页珍藏版）》请在金锄头文库上搜索。
1、实验四平衡二叉树演示1. 问题定义及需求分析1.1课题目的和任务问题描述：利用平衡二叉树设计动态查找表。实验要求：设计平衡二叉树的动态演示的模拟程序。1）采用平衡二叉树存储结构。2）完成平衡二叉树的创建、查找、插入和删除的演示操作。3）可以考虑两棵平衡二叉树的合并。1.2数据形式输入数据形式：通过键盘输入数据输入值的范围：树中元素的值为float型，范围为1.2e-38至3.4e+38；树 的名称为char类型数据，可以输入字母，数字和符号，但是长度必须在 20位以内；对菜单进行操作时，输入数据长度必须在200以内，且有效 的输入数据为0至7,其中0为退出程序，1至7为对应菜单的操作选项。 输
2、出数据形式：输出到显示器。1.3程序功能创建平衡二叉树存储结构，通过平衡因子，使二叉排序树达到平衡，提供平衡二叉树的创建、查找和删除，树中元素的查找、插入和 删除等基本功能，可以实现创建多棵平衡二叉树，并且能够进行两棵树 的合并。通过平衡二叉树，能够使树时刻保持平衡，从而提高在树中遍 历数据的速度，具有重要意义。1.4测试数据1创建平衡二叉树2输入创建树的个数t1输入第一个树的名称5输入第一个树中元素的个数5 2 6 8 9/依次输入各个元素t2输入第二个树的名称5输入第二个树中元素的个数3 1 4 10 7/依次输入各个元素5/层次遍历输出第一个树的结构图t1操作树名5/层次遍历输出第二个树
3、的结构图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操作树名（会提示该树不存在，说明删除树成功）退出程序2. 概要设计2.1抽象数据类型需要定义一个树的结构类型，其中包含数据类
4、型，它的左右孩子指针， 以及平衡因子，平衡因子的取值为-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* lc
5、hild,* 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)(/左部平衡化处
6、理 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(
7、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;ca
8、se RH:调整平衡因子;break;)调整平衡因子;R_Rotate(t-rchild);L_Rotate(t);(3) void R_Rotate(AVL& t)/以T为根节点的二叉排序树进行右旋转l=t-lchild;/将t的左孩子给lt-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&
9、 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的左孩子的最右孩子qq=q-rchild;)t-data=q-data;/把 q 的值给 tDeleteTree(t-lc
10、hild,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:asp们二皿ioqs(HH=jq-pnH3j-i)ji:HTH 9SBD瑚。jq?0二皿ioqs?HM=jqv-】：H日。睥。瑚。jq?i二jmoqs?HH=jqV-HTI。睥。) (jq-l)t31TAs(J9；JOLS)JT?0 ujn;gj)(J9；JOLSt9tpjTLDJ-；)99JJL3
11、l3FGi)J!河辜蠢昴由髀土孕/(呻PG。)，!。平妪。jq面传阖盅坏)g叩即1%用据二皿ioqsasp?0 二 Jmoqs(HH=jq-pnH3jrchild,e,shorter)return 0;)if(shorter)switch(t-bf)case LH:if(t-lchild-bf=EH)shorter=0;elseshorter=1;LeftBalance(t);左平衡处理break;case EH:t-bf=LH;shorter=0;break;case RH:t-bf=EH;shorter=1;break;)return 1;)(6) int MergeTree(AVL& t
12、1,AVL& t2)(/将树 t2 合并到 t1 上while(t2!=NULL)/t2 不为空时InsertTree(t1,t2-data,taller);/将 t2 中元素插入 t1DeleteTree(t2,t2-data,shorter);/将插入后的 t2 中元素删除)return 1;)(7) const int PrintTreeStructure(AVL t)利用层次遍历，输出树的形状if(!t)return 0;/树不存在，返回InitQ(q);/建立空队列while(1)/循环输出树中元素i+;/第i个元素num=0;j = 1;while(jlchild);/将左右孩子入
13、队列EnQ(q,t-rchild);if(j=i+1)coutlchild=NULL&t-rchild=NULL)/T为空时进行判断，当平衡树中出现层数不同的空结点时，终止输出 if(!level)首次出现两个孩子都空的结点，将其孩子的层数赋给level level=num+1;)elseEnQ(q,NULL);/若该点为空，则它的孩子也为空，入队列 EnQ(q,NULL);if(level&level+2=num)当遇到空结点，并且它的层数比标记层数大2时，结束输出return 1;)elsecout* ;)/用*代表空if(j=i+1)coutendl;)DeQ(q,t);/出队列/while)4. 调试分析4.1问题分析与解决方法平衡二叉树中最难处理的是平衡问题，如何保证所创建的树是一个平衡 树是关
