实验四 平衡二叉树演示

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 /操作树名（会提示该树不存在，

4、说明删除树成功）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;/结

5、点的平衡因子 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;

6、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

7、: 调整平衡因子;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;

8、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->

9、;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)/

10、左子树为空将右子树接上，删除该点; 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-

11、>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(e<t->data)/左子树中继续查找 if(!DeleteTree(t->lchild,e,shorter) return 0; if(shorter) switch(t->bf) case LH:t->

12、;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(!DeleteTree(t->rchild,e,shorter) return 0; if(shorter) switch(t->bf) case LH: if(t->lchild->bf=EH) shorter=0; else sh

13、orter=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& t1,AVL& t2)/将树t2合并到t1上 while(t2!=NULL)/t2不为空时 InsertTree(t1,t2->data,taller);/将t2中元素插入t1 DeleteTree(t2,t2->data,shorter);/将插入后的t2中元素删除 return

14、 1;(7) const int PrintTreeStructure(AVL t)/利用层次遍历，输出树的形状 if(!t)return 0;/树不存在，返回 InitQ(q);/建立空队列 while(1)/循环输出树中元素 i+;/第i个元素 num=0; j=1; while(j<=i) num+;/num为记层标志，记录当前T所在层数 j=2*j; if(t!=NULL) cout当前元素; EnQ(q,t->lchild);/将左右孩子入队列 EnQ(q,t->rchild); if(j=i+1) cout<<endl;/换行 if(t->lch

15、ild=NULL&&t->rchild=NULL)/T为空时进行判断，当平衡树中出现层数不同的空结点时，终止输出 if(!level)/首次出现两个孩子都空的结点，将其孩子的层数赋给level level=num+1; else EnQ(q,NULL);/若该点为空，则它的孩子也为空，入队列 EnQ(q,NULL); if(level&&level+2=num)/当遇到空结点，并且它的层数比标记层数大2时，结束输出 return 1; elsecout<<"* "/用*代表空 if(j=i+1) cout<<en

16、dl; DeQ(q,t);/出队列 /while4. 调试分析4.1问题分析与解决方法平衡二叉树中最难处理的是平衡问题，如何保证所创建的树是一个平衡树是关键问题。考虑可以通过递归调用的方式，通过层层递归，来调节各层节点的平衡因子。在调试过程中经常出现平衡因子数值不对的问题，经过仔细检查，发现是某些部分的代码不能适用于全部的可能情形，当一种新情形出现时，就会产生错误。经过不断的调试和改进，对这部分代码添加if判断，来区分各种不同的情形，进行不同的平衡因子调节和平衡化操作，从而解决了这一问题，通过目前测试来看，程序对于各种数据都有很好的稳定性。在直观输出树的结构图和平衡因子的算法调试中，也出现了各

17、种问题，例如没按预想换行，没有按预想结束输出以及过早结束输出等问题，经过不断地改进和尝试，最后采用了标记层数法，即当首次出现一个既没有左孩子也没有右孩子的结点时，将它孩子的层数标记下来，之后，如果出现一个空的结点，而它的层数比标记层数大2时，就可以结束循环，这是利用了平衡二叉树的特性。4.2算法的时空分析（1）平衡化操作时间复杂度：仅需要进行简单的判断，因此为空间复杂度：不需要开辟空间，为（2）删除结点操作时间复杂度：主要时间花费在查找需要删除的结点和找该结点的中序前驱上，因此时间复杂度为空间复杂度：（3）合并树时间复杂度：需要在t2中找到插入位置，时间复杂度为空间复杂度：直接合并到t1上，不

18、另开辟空间（4）层次遍历树时间复杂度：需遍历全树，且进行入队列、出队列操作，大约为空间复杂度：需借助队列和标记，因此需要一定的空间量，不超过4.3算法的改进设想能否在查找删除节点和合并树的操作上进行算法的优化改进，使得查找效率和合并效率更高。4.4经验和体会递归调用对于平衡树的平衡调节具有非常重要的作用，这大大减少了代码量，并且使得代码更加简洁。然而递归调用的过程却是非常复杂不容易理解的，稍不留神就有可能出现错误的调用，由于是层层递归，所以对函数运行情况的跟踪并不容易，十分容易出现错误。因此，为了减少错误，应当在编写前弄清楚整个函数所要实现的功能，并且尽量将代码写的规范，以便于调试的时候进行修

19、改。5. 使用说明本程序有菜单和提示语句，按照操作提示进行操作即可。对菜单进行操作时，输入数据长度必须在200以内，且有效的输入数据为0至7，其中0为退出程序，1至7为对应菜单的操作选项。要求输入数量数据时，必须输入小于32767的正整数。插入结点的数据可以是小数。本程序具有非法输入检测功能，但是请勿输入不合规则的数据，以免出现意想不到的错误。6. 测试结果（截屏）（1） 原树t2的结构图：（2） t2删除结点7后，层次遍历输出树的结构图：（3） 树t1的结构图：（4） 将t2合并到t1后，输出树的结构图：7. 附录7.1个人负责模块的程序代码void LeftBalance(AVL&

20、 t)/左部平衡化处理 AVL l,lr; l=t->lchild; switch(l->bf) /检查T的左子树平衡度，并作相应的平衡处理 case LH:/新节点插入在T的左孩子的左子树上，做单右旋处理 t->bf=l->bf=EH; R_Rotate(t); break; case EH:/deleteAVL需要，insertAVL用不着 t->bf=LH; l->bf=RH; R_Rotate(t); break; case RH:/新插入节点在T的左孩子的右子树上，做双旋处理 lr=l->rchild; switch(lr->bf) c

21、ase LH: t->bf=RH; l->bf=EH; break; case EH: t->bf=l->bf=EH; break; case RH: t->bf=EH; l->bf=LH; break; lr->bf=EH; L_Rotate(t->lchild); R_Rotate(t); void RightBalance(AVL& t)/右部平衡化处理 AVL r,rl; r=t->rchild; switch(r->bf) case RH:/新节点插在T的右孩子的右子树上，要做单左旋处理 t->bf=r->

22、;bf=EH; L_Rotate(t); break; case EH:/deleteAVL需要，insertAVL用不着 t->bf=RH; r->bf=LH; L_Rotate(t); break; case LH:/新节点插在T的右孩子的左子树上，要做双旋处理 rl=r->lchild; switch(rl->bf) case LH: t->bf=EH; r->bf=RH; break; case EH: t->bf=r->bf=EH; break; case RH: t->bf=LH; r->bf=EH; break; rl-

23、>bf=EH; R_Rotate(t->rchild); L_Rotate(t); void R_Rotate(AVL& t)/以T为根节点的二叉排序树进行右旋转 AVL l; l=t->lchild; t->lchild=l->rchild; l->rchild=t; t=l;/p指向新的根节点void L_Rotate(AVL& t)/以T为根节点的二叉排序树进行左旋转 AVL r; r=t->rchild; t->rchild=r->lchild; r->lchild=t; t=r;int DeleteTree(

24、AVL& t,Type e,int& shorter)/平衡二叉树的结点删除 if(t=NULL)/不存在该元素 return 0;/删除失败 else if(e.num=t->data.num)/找到元素结点 AVL q=NULL; if(t->lchild=NULL)/左子树为空 q=t; t=t->rchild; delete q; shorter=1; else if(t->rchild=NULL)/右子树为空 q=t; t=t->lchild; delete q; shorter=1; else/左右子树都存在 q=t->lchil

25、d; while(q->rchild)/找到要删除结点t的左孩子的最右孩子q q=q->rchild; t->data.num=q->data.num;/把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->

26、bf=EH) shorter=0; else shorter=1; RightBalance(t);/右平衡处理 break; else if(e.num<t->data.num)/左子树中继续查找 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)

27、shorter=0; else shorter=1; RightBalance(t);/右平衡处理 break; else/右子树中继续查找 if(!DeleteTree(t->rchild,e,shorter) return 0; if(shorter) switch(t->bf) case LH: if(t->lchild->bf=EH) shorter=0; else shorter=1; LeftBalance(t); /左平衡处理 break; case EH: t->bf=LH; shorter=0; break; case RH: t->bf=

28、EH; shorter=1; break; return 1;int MergeTree(AVL& t1,AVL& t2)/将树t2合并到t1上 while(t2!=NULL) int taller,shorter; InsertTree(t1,t2->data,taller); DeleteTree(t2,t2->data,shorter); return 1;#include"H.h"const int PrintTreeStructure(AVL t)/利用层次遍历，输出树的形状 if(!t)return 0; int i=0,level=

29、0,j,num; LinkQ q; InitQ(q); while(1) i+; num=0; j=1; while(j<=i) num+;/num为记层标志，记录当前T所在层数 j=2*j; if(t!=NULL) cout<<t->data.num<<"("<<t->bf<<") " EnQ(q,t->lchild); EnQ(q,t->rchild); if(j=i+1) cout<<endl; if(t->lchild=NULL&&t-

30、>rchild=NULL)/T为空时进行判断，当平衡树中出现层数不同的空结点时，终止输出 if(!level)/首次出现两个孩子都空的结点，将其孩子的层数赋给level level=num+1; else EnQ(q,NULL);/若该点为空，则它的孩子也为空，入队列 EnQ(q,NULL); if(level&&level+2=num) return 1; elsecout<<"* "/用*代表空 if(j=i+1) cout<<endl; DeQ(q,t); /while7.2程序全部代码/*H.h文件*/#ifndef H

31、_H_INCLUDED#define H_H_INCLUDED#include<stdlib.h>#include<string.h>#include<stdio.h>#include<iostream>using namespace std;#define NAME_LENGTH 20#define LH 1 /树的左部比右部高1#define EH 0 /树的左右一般高#define RH -1 /树的右部比左部高1typedef struct Type/数据类型结构 float num;Type;/*平衡树结构声明*/typedef str

32、uct 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

33、LNode* prior,* next;LNode,*Link;/*双向链表操作函数声明*/int InitL(Link& );int InsertL(Link& ,AVL& ,char* );int DeleteL(Link& );const int SearchL(Link ,char* ,Link& );/*菜单*/void Menu();/*队列操作函数声明*/int InitQ(LinkQ& );int EnQ(LinkQ& ,AVL );int DeQ(LinkQ& ,AVL& );/*平衡树操作函数声明*/v

34、oid R_Rotate(AVL& );void L_Rotate(AVL& );void LeftBalance(AVL& );void RightBalance(AVL& );int InsertTree(AVL& ,Type ,int& );int MergeTree(AVL& ,AVL& );const int SearchTree(AVL ,Type ,AVL& );const int PrintTreeStructure(AVL );int DeleteTree(AVL& ,Type ,int&

35、 );int DestroyTree(AVL& );#endif / H_H_INCLUDED/*main.cpp文件*/#include"H.h"int main() Menu(); return 1;/*MENU.cpp*/#include"H.h"void Menu() char i10*NAME_LENGTH,a; int j; for(j=0;j<10*NAME_LENGTH;j+)ij='0' Link l; InitL(l);/创建包含一个空头结点的链表 while(1) system("cls&qu

36、ot;); cout<<" 平衡二叉树（AVL树）的演示"<<endl<<endl; cout<<" 1.创建二叉平衡树"<<endl; cout<<" 2.在树中查找元素"<<endl; cout<<" 3.在树中插入元素"<<endl; cout<<" 4.在树中删除元素"<<endl; cout<<" 5.输出二叉平衡树结构示意图&quo

37、t;<<endl; cout<<" 6.合并两个二叉平衡树"<<endl; cout<<" 7.删除二叉平衡树"<<endl<<endl; cout<<"请输入操作序号（输入0退出程序）：" cin.getline(i,10*NAME_LENGTH,'n'); if(strlen(i)!=1)continue; else a=i0; if(a='0') break; switch(a) case '1':

38、 system("cls"); cout<<"请输入需要创建的平衡树个数:" int j,k; cin>>k; for(j=0;j<k;j+) cout<<"请输入第"<<j+1<<"棵平衡树的树名(小于20个字符)：" char nameNAME_LENGTH; cin>>name; cout<<"请输入元素个数:"<<endl; int m,n; cin>>n; cout<

39、<"请依次输入元素:"<<endl; Type e; AVL t=NULL; for(m=0;m<n;m+) cin>>e.num; int taller=0;/增高标识，1为增高，0为不增高 InsertTree(t,e,taller);/生成树结点 InsertL(l,t,name);/将该平衡树命名，并接入链表 cout<<"创建成功！"<<endl; system("pause"); system("cls"); break; case '

40、2': system("cls"); cout<<"请输入你想要访问的树名："<<endl; char nameNAME_LENGTH; cin>>name; Link s; if(!SearchL(l,name,s) cout<<"未找到该名字的平衡树！"<<endl; system("pause"); system("cls"); break; /未找到该平衡树，返回菜单 cout<<"请输入你要查找的

41、数"<<endl; Type m; AVL p; cin>>m.num; if(SearchTree(s->t,m,p) cout<<m.num<<" 在树中存在."<<endl; elsecout<<"该树中不存在这个数！"<<endl; system("pause"); system("cls"); break; case '3': system("cls"); cout<<"请输入你想要访问的树名："<<endl; char nameNAME_LENGTH; cin>>name; Link s; if(!SearchL(l,name,s) cout<<"未找到该名字的平衡树！"<<endl; system("pause"); system