平衡二叉树操作演示.doc

.数据结构实习报告题目：平衡二叉树的操作演示班级：信息管理与信息系统11-1姓名：崔佳学号：201101050903完成日期：2013.06.25一、需求分析1. 初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、删除、销毁、合并两棵树，几种选择。其中查找、插入和删除操作均要提示用户输入关键字。每次插入或删除一个节点后都会更新平衡二叉树的显示。2. 平衡二叉树的显示采用凹入表形式。3.每次操作完毕后都会给出相应的操作结果，并进入下一次操作，知道用户选择退出二、概要设计1.平衡二叉树的抽象数据类型定义：ADT BalancedBinaryTree 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitAVL(BSTree& T) 操作结果：构造一个空的平衡二叉树T DestroyAVL(BSTree& T) 初始条件：平衡二叉树T存在 操作结果：销毁平衡二叉树T SearchAVL(BSTree T,int key) 初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值 操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的指针，否则为空 InsertAVL(BSTree& T,int key,Status& taller) 初始条件：平衡二叉树T存在，key和关键字的类型相同 操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入一个关键字为key的元素 DeleteAVL(BSTree& T,int &key,Status& lower) 初始条件：平衡二叉树T存在，key和关键字的类型相同 操作结果：若T中存在关键字和key相同的数据元素则删除它ADT BalancedBinaryTree2.本程序包含二个模块1） 主程序模块：void main（） 接收命令； While(“命令”！“退出”) 处理命令； 清屏并得新打印提示信息； 接收下一条命令；2） 平衡二叉树基本操作实现平衡二叉树的抽象数据类型的各函数原型。各模块之间的调用关系如下：主程序模块平衡二叉树模块三、详细设计1. 根据题目要求和平衡二叉树的操作特点，平衡二叉树采用整数链式存储结构基本操作的函数原型：#define LH 1 /左高#define EH 0 /等高#define RH -1 /右高#define TRUE 1 #define FALSE 0#define ERROR 0#define OK 1typedef int Status;typedef int ElemType; /本程序处理数据对象为整型typedef struct BSTNode ElemType data;int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;1）平衡二叉树基本操作实现/构造平衡二叉树TStatus InitAVL(BSTree &T) T=NULL; return OK;/对以*p为根的二叉树作左旋处理,处理之后p指向新的树根结点/即旋转处理之前的右子树的根结点void L_Rotate(BSTree &p) BSTree rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc;/对以*p为根的二叉树作右旋处理,处理之后p指向新的树根结点/即旋转处理之前的左子树的根结点void R_Rotate(BSTree &p) BSTree lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc;/对以指针T所指结点为根的二叉树作右平衡处理/本算法结束时T指向新的根结点void LeftBalance(BSTree &T) BSTree lc,rd; lc=T-lchild; switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T); break; case RH: rd=lc-rchild; switch(rd-bf) 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; rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /对以指针T所指结点为根的二叉树作右平衡处理/本算法结束时T指向新的根结点void RightBalance(BSTree& T) BSTree rc,rd; rc=T-rchild; switch(rc-bf) case RH: T-bf=rc-bf=EH; L_Rotate(T); break; case LH: rd=rc-lchild; switch(rd-bf) case RH: T-bf=LH; rc-bf=EH; break; case EH: T-bf=rc-bf=EH; break; case LH:T-bf=EH; rc-bf=RH; break; rd-bf=EH; R_Rotate(T-rchild); L_Rotate(T); /查找关键字为key的结点/如有返回指向此结点的指针，如无返回空Status SearchAVL(BSTree T,int e)if(!T) return ERROR;if(T-data=e) printf(t结果: %d%dnt,T-data,T-bf); return OK; else if(T-lchild)if(SearchAVL(T-lchild,e)return OK; if(T-rchild)if(SearchAVL(T-rchild,e)return OK; return ERROR; /若在平衡的二叉排序树中不存在和e相同的关键字的结点，则插入一个数据元素为e的新结点并返回1，否则返回0。/若因插入而使二叉排序树失去平衡，则做平衡旋转处理/布尔变量taller反映T长高与否Status InsertAVL(BSTree &T,ElemType e,Status &taller) if(!T) T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=TRUE; else if(e=T-data) taller=FALSE; return FALSE; if(edata) if(!InsertAVL(T-lchild,e,taller) return FALSE; if(taller) switch(T-bf) case LH: LeftBalance(T); taller=FALSE; break; case EH: T-bf=LH; taller=TRUE; break; case RH: T-bf=EH; taller=FALSE; break; else if(!InsertAVL(T-rchild,e,taller) return FALSE; if(taller) switch(T-bf) case RH: RightBalance(T); taller=FALSE; break; case EH: T-bf=RH; taller=TRUE; break; case LH: T-bf=EH; taller=FALSE; break; return TRUE; /打印空格void Printblank(int i) while(i =0) printf( ); i-; /以凹入表的形式显示平衡二叉树Tvoid ViewTree(BSTree T,int i) if(T) Printblank(i); printf(%d%dn,T-data,T-bf); else Printblank(i); printf(NULLn); return; ViewTree(T-lchild,i+5); ViewTree(T-rchild,i+5);/销毁平衡二叉树void DestroyAVL(BSTree &T)if(T)if(T-lchild)DestroyAVL(T-lchild);if(T-rchild)DestroyAVL(T-rchild);free(T);T=NULL;Status Delete(BSTree& p,int &e,int &flag) BSTree q,s; if(!p-rchild) q=p; if(p-lchild) p-lchild-bf=p-bf; e=p-lchild-data; p=p-lchild; free(q); flag=1; else if(!p-lchild) q=p; p-rchild-bf=p-bf; e=p-rchild-data; p=p-rchild; free(q); flag=1; else q=p; s=p-lchild; while(s-rchild)q=s; s=s-rchild; p-data=s-data; if(q!=p)q-rchild=s-lchild; else q-lchild=s-lchild; p-bf=RH; e=q-data; free(s); return TRUE; /若二叉排序树T中存在关键字等于e的数据元素时，则删除该数据元素结点/并返回TRUE，否则返回FALSEStatus DeleteBST(BSTree& T,int &e,int &flag) if(!T)return FALSE; else if(e=T-data)return Delete(T,e,flag); else if(edata) if(!DeleteBST(T-lchild,e,flag) return FALSE; return TRUE; else if(!DeleteBST(T-rchild,e,flag) return FALSE; return TRUE; void DelBalance(BSTree& T,int e, Status &lower,int &flag) if(!T) lower=TRUE; return; if(e=T-data)if(flag=1) switch(T-bf)case RH:case LH: T-bf=EH; lower=TRUE; break; else switch(T-bf) case RH: lower=FALSE; break; case EH: T-bf=LH; lower=FALSE; break; case LH: LeftBalance(T); lower=TRUE; break; return ; if(edata) DelBalance(T-lchild,e,lower,flag); if(lower) switch(T-bf) case LH: T-bf=EH; lower=TRUE; break; case EH:T-bf=RH; lower=FALSE; break; case RH:RightBalance(T); lower=TRUE; break; if(eT-data) DelBalance(T-rchild,e,lower,flag); if(lower) switch(T-bf) case RH: T-bf=EH; lower=TRUE; break; case EH: T-bf=LH; lower=FALSE; break; case LH: LeftBalance(T); lower=TRUE; break; return ;/删除平衡二叉树结点Status DeleteAVL(BSTree &T,int &e,Status &lower)int flag=0;if(!DeleteBST(T,e,flag) return FALSE;else DelBalance(T,e,lower,flag);return TRUE;2）主函数Main及其它辅助函数的实现 /*主函数*/void main() void Print(); void About(); BSTree T,t,p; int e,s; Status taller,lower; InitAVL(T); InitAVL(t); InitAVL(p); Print(); scanf(%d,&s); while(s!=6) switch(s) case 1: /显示 printf(按凹入表形式打印二叉树结构：n); printf(T:n); PrintTree(T,1); printf(t:n); PrintTree(t,1); break; case 2: /查找 printf(t选择树(1,2):); scanf(%d,&s); printf(t关键字(整数):); scanf(%d,&e); if(s=1) s=SearchAVL(T,e); if(s=2) s=SearchAVL(t,e); if(!s) printf(t查找失败nt); break; case 3: /插入 printf(t选择树(1-T,2-t):); scanf(%d,&s); printf(t关键字(整数):); scanf(%d,&e); if(s=1) InsertAVL(T,e,taller); printf(T:n); PrintTree(T,1); if(s=2) InsertAVL(t,e,taller); printf(t:n); PrintTree(t,1); break; case 4: /删除 printf(t选择树(1-T,2-t):); scanf(%d,&s); printf(t关键字(整数):); scanf(%d,&e); if(s=1)if(DeleteAVL(T,e,lower)printf(t删除成功nt);elseprintf(t删除失败nt); if(s=2)if(DeleteAVL(t,e,lower)printf(t删除成功nt);elseprintf(t删除失败nt); break; case 5: /销毁 printf(t选择树(1