平衡二叉树操作的演示

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

1、数据结构课程设计题目：平衡二叉树操作的演示学生学院计算机学院专业班级08级计算机科学与技术7班学号学生姓名冯海东指导教师曾孜2010年06月26日平衡二叉树操作的演示一、需求分析1．本程序是是利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找、插入和删除。2．初始，平衡二叉树为空树，可以按先序输入平衡二叉树，以输入0结束，中间以回车隔开，创建好二叉树后，可以对其查找，再对其插入，输入0结束插入，再可以对其删除，输入0结束，每次插入或删除一个结点后，更新平衡二叉树的显示。3．本程序以用户和计算机的对话方式执行，根据计

2、算机终端显示：“提示信息”下，用户可由键盘输入要执行的操作。4．测试数据（附后）二、概要设计1．抽象数据类型动态查找表的定义如下：ADTDynamicSearchTable{数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初试条件：动态查找表DT存在。操作结果:销毁动态查找表DT。SearchDSTable(DT,key);初

3、试条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果:若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。InsertDSTable(&DT,e);初试条件：动态查找表DT存在，e为待插入的数据元素。操作结果:若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&DT,key);初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果:若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT

4、,Visit());初试条件：动态查找表DT存在，Visit()是结点操作的应用函数。操作结果:按某种次序对DT的每个结点调用函数Visit()一次。如果Visit()失败，则操作失败。}ADTDynamicSearchTable2．本程序包含两个模块：Voidmain(){do{输入命令；执行命令；}while(“命令”=“退出”)；}3．本程序包含两个模块：主程序模块平衡二叉树的模块三、详细设计1.平衡二叉树结点类型;#include#includetypedefstructBSTnode{

5、intdata;intbf;structBSTnode*lchild,*rchild;}BSTnode,*bstree;#defineLH+1#defineEH0#defineRH-1#defineTRUE1#defineFALSE0//对平衡二叉树的操作//bstreeInsertAVL(bstree&T,inte);//在平衡二叉树中插入结点//intFindAVL(bstreep,inte);//查找平衡二叉树中是否有结点e//bstreeDeleteAVL(bstree&T,inte);//删除平衡平衡二叉树的结点e，并保持

6、平衡二叉树的性质//intPreordertraverse(bstreeT);//按先序遍历平衡二叉树////平衡二叉树的操作的详细算法//intshorter,taller;intPreordertraverse(bstreeT){if(T){printf("%d%d",T->data,T->bf);Preordertraverse(T->lchild);Preordertraverse(T->rchild);}return1;}intFindAVL(bstreep,inte){if(p==NULL)returnNULL;el

7、seif(e==p->data)returntrue;elseif(edata){p=p->lchild;returnFindAVL(p,e);}//左子树上查找//else{p=p->rchild;returnFindAVL(p,e);}//右子树上查找//}//右旋//bstreeR_Rotate(bstree&p){bstreelc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;returnp;}//左旋//bstreeL_Rotate(bstree&p){bs

8、treerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;returnp;}//左平衡处理//bstreeLeftBalance(bstree&T){bstreelc,rd;