数据结构——平衡二叉树的判定

《数据结构——平衡二叉树的判定》由会员分享，可在线阅读，更多相关《数据结构——平衡二叉树的判定（15页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计平衡二元树的判定系别专业班级学号姓名指导教师成绩2011 年7月 14 日平衡二元树的判定一、需求分析1. 平衡二叉树(Balanced Binary Tree )又被称为AVL树(区别于AVL算法), 且具有以下性质：它是一棵空树或者它的左右两个子树的高度差的绝对值 不超过1，并且左右两个子树都是一棵平衡二叉树。给定一个二元树的先序 遍历或后序遍历结果，判定其是否为平衡二元树。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据(滤去 输入中非法字符)和运算结果显示在其后。二、概要设计1

2、. ADT DynamicSearchTable数据结构D： D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可 惟一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初试条件：动态查找表DT存在。操作结果：销毁动态查找表DT。SearchDSTable(DT,key);初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表 中的位置，否则为“空”。InsertDSTa

3、ble(&DT,e);初试条件：动态查找表DT存在，e为待插入的数据元素。操作结果：若DT中不存在其关键字等于e. key的数据元素，则插入e到DT。DeleteDSTable(&DT,key);初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT,Visit();初试条件：动态查找表DT存在，Visit()是结点操作的应用函数。操作结果：按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一但Visit()失败，则操作失败。ADT DynamicSearchTable2.

4、 程序模块本程序只有两个模块，调用关系简单本程序只有两个模块，调用关系简单：主程序模块和平衡二叉树的模块。即：Void main（）Do接受命令（根据提示输入终点城市和起点城市的序号）；处理命令；while（“ 命令”=“退出”）；3. 设计原理框图OK!三、详细设计1.根据题目要求和查找的基本特点，其结点类型typedef struct BSTnodeint data;int bf;struct BSTnode *lchild,*rchild;BSTnode,*bstree;#define LH +1#define EH 0#define RH -1/*对平衡二叉树的操作bstree Ins

5、ertAVL(bstree &T, int e)；/在平衡二叉树中插入结点。int FindAVL(bstree p,int e)；/查找平衡二叉树中是否有结点e。bstree DeleteAVL(bstree &T,int e)/删除平衡平衡二叉树的结点e，并保持平衡二叉树的性质。int Preordertraverse(bstree T)/按先序遍历平衡二叉树。/*平衡二叉树的操作的详细算法bstree InsertAVL(bstree &T, int e)bstree p;/插入新结点，树长高置taller为TRUEif(!T) T=(bstree)malloc(sizeof(BSTno

6、de);T-data=e;T-lchild=T-rchild=NULL;T-bf=EH;taller=TRUE;else 树中存在和e有相同关键字的结点则不再插入if(e=T-data)taller=FALSE;return NULL;值小于则继续在树的左子树中搜索if(e data)/插入到左子树且左子树长高p=InsertAVL( T-lchild,e);if(p)T-lchild=p;if(taller) switch(T-bf) /检查*T的平衡度case LH: /原本左子树比右子树高，需要做左平衡处理T=LeftBalance(T);taller=FALSE;break;case

7、EH: /原本左子树和右子树同高，现因左子树争高而使树增高T-bf=LH;taller=TRUE;break;case RH: /原本右子树比左子树高，现在左右子树等高T-bf=EH;taller=FALSE;break;/switch( T-bf)/if(taller)/if(p)/if(e data)继续在”的右子树中搜索else/插入到右子树且使右子树长高p=InsertAVL( T-rchild,e);if (p)rchild=p;if(taller) switch(T-bf) /检查*T的平衡度case LH: /原本左子树比右子树高，现在左右子树等高T-bf=EH;taller=F

8、ALSE;break;case EH: /原本左子树和右子树同高，现因右子树增高而使树增高T-bf=RH;taller=TRUE;break;case RH: /原本右子树比左子树高，需要做右平衡处理T=RightBalance(T);taller=FALSE;break;/switch( T-bf)/if(taller)/if (P)/if(e T-data)/elsereturn T; int Preordertraverse(bstree T) if(T)printf(- %d %dn,T-data, T-bf);Preordertraverse(T-lchild);Preordertr

9、averse(T-rchild);return 1;int FindAVL(bstree p,int e)if(p=NULL)return NULL;else if(e=p-data) return true;else if(edata)p=p-lchild;return FindAVL(p, e);/左子树上查找else p=p-rchild;return FindAVL( p, e);/右子树上查找bstree DeleteAVL(bstree &T,int e)删除后要保证该二叉树还是平衡的int n,m=0;/标记bstree q;if(!T)return NULL;else if(e

10、=T-data) /直 接删除n=Delete(T,e);m=n;if(m!=0) q=T;DeleteAVL(T,m);q-data=m;else if(edata)/在 左子树上寻找 DeleteAVL(T-lchild,e);if(shorter)switch( T-bf)case LH:T-bf=EH;shorter=true;break;case EH:T-bf=RH;shorter=false;break;case RH:Delete_Rightbalance(T);shorter=true;break;/switch( T-bf)/if(shorter)/if(edata)els

11、e /在右子树上寻找DeleteAVL( T-rchild,e);if(shorter)switch( T-bf)case LH:Delete_Leftbalance(T);shorter=true;break;case EH:T-bf=LH;shorter=false;break;case RH:T-bf=EH;shorter=true;break;/switch(T-bf)/在右子数上寻找完/在左右子上完/删除完return T;2.主程序和其他伪码算法void main()while(e!=0)if(e!=0) InsertAVL(T,e);while(d!=0)if(d!=0) Ins

12、ertAVL(T,d);Preordertraverse(T);c=FindAVL(T,t);if(c=1)printf(”有要查找的节点n);else printf(无要查找的节点n);doDeleteAVL(T,b);Preordertraverse(T);while(b=1);/右旋bstree R_Rotate(bstree &p) bstree lc;lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;return p;/佐旋bstree L_Rotate(bstree &p) bstree rc;rc=p-rchild;p-rchild=

13、rc-lchild;rc-lchild=p;p=rc;return p;/左平衡处理bstree LeftBalance(bstree &T) bstree lc,rd;lc=T-lchild; /lc指向*T的左子树根结点switch(lc-bf) /检查*T的左子树平衡度，并做相应的平衡处理 case LH: /新结点插入在*T的左孩子的左子树上，要做单右旋处理 T-bf=lc-bf=EH;T=R_Rotate(T);break;case RH: /新结点插入在*T的左孩子的右子树上，要做双旋处理 rd=lc-rchild; /rd指向*T的左孩子的右子树根switch(rd-bf) /修

14、改*T及其左孩子的平衡因子case LH:T-bf=RH;lc-bf=EH;break;case EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=LH;break;/switch(rd-bf)rd-bf=EH;T-lchild=L_Rotate(T-lchild); /对*T的左孩子做左旋平衡处理T=R_Rotate(T); 对*T做右旋处理/switch(lc-bf)return T;/右平衡处理bstree RightBalance(bstree &T)bstree rc,ld;rc=T-rchild; /rc指向*T的右子树根结点switch(r

15、c-bf) /检查*T的右子树平衡度，并做相应的平衡处理 case RH: /新结点插入在*T的右孩子的右子树上，要做单右旋处理 T-bf=rc-bf=EH;T=L_Rotate(T);break;case LH: /新结点插入在*T的右孩子的左子树上，要做双旋处理 ld=rc-lchild; /ld指向*T的右孩子的左子树根switch(ld-bf) /修改”及其右孩子的平衡因子case LH:T-bf=EH;rc-bf=RH;break;case EH:T-bf=rc-bf=EH;break;case RH:T-bf=LH;rc-bf=EH;break;/switch(ld-bf) ld-

16、bf=EH;T-rchild=R_Rotate(T-rchild); /对*T的右孩子做右旋平衡处理 T=L_Rotate(T); 对*T做左旋处理 /switch(rc-bf) return T;int Delete(bstree &T,int e)删除结点bstree p,q;e=0;P=T;if(!T-rchild) /右子数为空需要重接它的左子数T=T-lchild;free(p);shorter=true;else if(!T-lchild) /重接它的右子数 T=T-rchild;free(p);shorter=true;else /左右子数均不空q=T-lchild;while(

17、q-rchild!=NULL)转左，然后向右到尽头 q=q-rchild;e=q-data; return e;void Delete_Rightbalance(bstree &T)/删除在左子树上的，相当于插入在右子树bstree rc=T-rchild,ld;switch(rc-bf)case LH:/双旋，先右旋后左旋ld=rc-lchild;rc-lchild=ld-rchild;ld-rchild=rc;T-rchild=rc-lchild;rc-lchild=T;switch(ld-bf) case LH:T-bf=EH;rc-bf=RH;break;case EH:T-bf=rc

18、-bf=EH;break;case RH:T-bf=LH;rc-bf=EH;break;ld-bf=EH;T=rc;shorter=true;break;case EH:/删除在左子树，相当于插入在右子树，左单旋T-rchild=rc-lchild;rc-lchild=T;rc-bf=LH;T-bf=RH;T=rc;shorter=EH;break;case RH:/删除在左子树，相当于插入在右子树，左单旋T-rchild=rc-lchild;rc-lchild=T;rc-bf=T-bf=EH;T=rc;shorter=true;break; void Delete_Leftbalance(b

19、stree &T)/删除右子树上的，相当于插入在左子树上bstree p1,p2;p1= T-lchild;switch(p1-bf) case LH:T-lchild=p1-rchild;/佑旋p1-rchild=T;p1-bf=T-bf=EH;T=p1;shorter=true;break;case EH:T-lchild=p1-rchild;/右 旋p1-rchild=T;p1-bf=RH;T-bf=LH;T=p1;shorter=false;break;case RH:p2=p1-rchild;/右 双旋p1-rchild=p2-lchild;p2-lchild=p1;lchild=p

20、2-rchild;p2-rchild=T;switch(p2-bf)case LH:T-bf=RH;p1-bf=EH;break;case EH:T-bf=EH;p1-bf=EH;break;case RH:T-bf=EH;p1-bf=LH;break;p2-bf=EH;T=p2;shorter=true;break;四、调试分析1. 在开始对平衡二叉树的插入后，再做平衡处理时，特别是在做双向旋转平衡处理后 的更新时，费了一些时间；2. 在做平衡二叉树的删除时，当删除结点左右孩子均在时，开始直接用左子树的最 大数代替，然后直接删除结点，结果导致删除了将要删除的结点及其孩子均删除了， 后来将要删

21、除的结点用左子树的最大树代替后，对左子树的最大结点做好标记，然后 再做对其做删除处理。3. 本程序算法基本简单，没有多大困难，就是在分析做双旋平衡处理的更新时，开 始思路有些混乱，后来就好了。五、用户手册1. 本程序的运行环境为DOS操作系统，执行文件为Balanced Tree.exe。2. 进入演示程序后，按广度遍历输入平衡二叉树，中间以回车键隔开，输入0为结束； 再输入要插入的结点，输入0结束，再输入要查找的结点，最后可以输入要删除的结 点，输入0结束。六、测试结果先按广度遍历创建平衡二叉树（亦可一个一个的插入二叉树的结点）（输入0结束， 然后可插入结点，其会显示插入后的二叉树，输入0，不再插入；输入要查找结点， 输入要删除的结点，其显示如下：七、参考文献1 朱战立编著.数据结构（C语言描述）.北京：高等教育出版社，20042 严蔚敏等编著.数据结构及应用算法教程.北京：清华大学出版社20013 陈本林等编著.数据结构.南京：南京大学出版社，20024 赵致琢著.计算科学导论.北京：科学出版社，2000