平衡二叉树操作演示

《平衡二叉树操作演示》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.数据结构实习报告题目：平衡二叉树的操作演示班级：信息管理与信息系统11-1姓名：崔佳学号：201101050903完成日期：2013.06.25word教育资料.一、需求分析1.初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、删除、销毁、合并两棵树，几种选择。其中查找、插入和删除操作均要提示用户输入关键字。每次插入或删除一个节点后都会更新平衡二叉树的显示。2.平衡二叉树的显示采用凹入表形式。3.每次操作完毕后都会给出相应的操作结果，并进入下一次操作，知道用户选择退出二、概要设计1.平衡二叉树的抽象数据类型定义：ADTBalancedBinaryTree{

2、数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：InitAVL(BSTree&T)操作结果：构造一个空的平衡二叉树TDestroyAVL(BSTree&T)初始条件：平衡二叉树T存在操作结果：销毁平衡二叉树TSearchAVL(BSTreeT,intkey)初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的指针，否则为空InsertAVL(BSTree&T,intkey,Status&taller)初

3、始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入一个关键字为key的元素DeleteAVL(BSTree&T,int&key,Status&lower)初始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字和key相同的数据元素则删除它}ADTBalancedBinaryTreeword教育资料.2.本程序包含二个模块1）主程序模块：voidmain（）{接收命令；While(“命令”！＝“退出”){处理命令；清屏并得新打印提示信息；接收下一条命令；}}2）平衡二叉树基本操作实现平衡二

4、叉树的抽象数据类型的各函数原型。各模块之间的调用关系如下：主程序模块平衡二叉树模块三、详细设计1.根据题目要求和平衡二叉树的操作特点，平衡二叉树采用整数链式存储结构基本操作的函数原型：#defineLH1//左高#defineEH0//等高#defineRH-1//右高#defineTRUE1#defineFALSE0#defineERROR0#defineOK1word教育资料.typedefintStatus;typedefintElemType;//本程序处理数据对象为整型typedefstructBSTNode{ElemTypedata;intbf;structBSTN

5、ode*lchild,*rchild;}BSTNode,*BSTree;1）平衡二叉树基本操作实现//构造平衡二叉树TStatusInitAVL(BSTree&T){T=NULL;returnOK;}//对以*p为根的二叉树作左旋处理,处理之后p指向新的树根结点//即旋转处理之前的右子树的根结点voidL_Rotate(BSTree&p){BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}//对以*p为根的二叉树作右旋处理,处理之后p指向新的树根结点word教育资料.//即旋转处理之前的左子树的根结点vo

6、idR_Rotate(BSTree&p){BSTreelc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}//对以指针T所指结点为根的二叉树作右平衡处理//本算法结束时T指向新的根结点voidLeftBalance(BSTree&T){BSTreelc,rd;lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;caseRH:rd=lc->rchild;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;b

7、reak;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}word教育资料.rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);}}//对以指针T所指结点为根的二叉树作右平衡处理//本算法结束时T指向新的根结点voidRightBalance(BSTree&T){BSTreerc,rd;rc=T->rchild;switch(rc->bf){caseRH:T->bf=rc->bf=EH