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

数据结构课程设计 平衡二元树的判定 系 别专 业班级学号 姓 名 指导教师成 绩2011 年 7 月 14 日平衡二元树的判定一、 需求分析1. 平衡二叉树（Balanced Binary Tree）又被称为AVL树（区别于AVL算法），且具有以下性质：它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。给定一个二元树的先序遍历或后序遍历结果，判定其是否为平衡二元树。 2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中非法字符）和运算结果显示在其后。二、 概要设计1. ADT DynamicSearchTable 数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(&DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初试条件：动态查找表DT存在。 操作结果: 销毁动态查找表DT。 SearchDSTable(DT,key); 初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果: 若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。 InsertDSTable(&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 DynamicSearchTable 2. 程序模块本程序只有两个模块，调用关系简单本程序只有两个模块，调用关系简单：主程序模块和平衡二叉树的模块。即：Void main() Do 接受命令（根据提示输入终点城市和起点城市的序号）； 处理命令； while(“命令”=“退出”)； 3. 设计原理框图存在含x的结点，则删除该结点，并作中序遍历无结点x找到该节点输入元素x，查找二叉排序树T计算二叉排序树T的平均查找长度，并输出结果对二叉排序树T作中序遍历,并输出结果二叉链表作存储结构和顺序表作存储结构输入数列L， 以回车(n)为输入结束标志生成二叉排序树T；13二叉排序树T是否为平衡二叉树NO! N Y OK!三、 详细设计1. 根据题目要求和查找的基本特点，其结点类型typedef struct BSTnode int data; int bf; struct BSTnode *lchild,*rchild; BSTnode,*bstree; #define LH +1 #define EH 0 #define RH -1 /*对平衡二叉树的操作 bstree InsertAVL(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为TRUE if(!T) T=(bstree)malloc(sizeof(BSTnode); 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 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) /继续在*T的右子树中搜索 else /插入到右子树且使右子树长高 p=InsertAVL(T-rchild,e); if (p) T-rchild=p; if(taller) switch(T-bf) /检查*T的平衡度 case LH: /原本左子树比右子树高，现在左右子树等高 T-bf=EH; taller=FALSE; 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) /else return T; int Preordertraverse(bstree T) if(T) printf( %d %dn,T-data,T-bf); Preordertraverse(T-lchild); Preordertraverse(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=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) else /在右子树上寻找 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) InsertAVL(T,d); Preordertraverse(T); c=FindAVL(T,t); if(c=1)printf(有要查找的节点n); else printf(无要查找的节点n); do DeleteAVL(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=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) /修改*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(rc-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) /修改*T及其右孩子的平衡因子 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-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(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-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(bstree &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; T-lchild=p2-rchild; p2-rchild=T; switch(p2-bf) case LH:T-bf=RH;p1-bf=EH;break;