数据结构程序报告(平衡二叉树的操作).doc

数据结构程序报告(平衡二叉树的操作).doc

ID:58536268

大小:284.50 KB

页数:16页

时间:2020-09-03

数据结构程序报告(平衡二叉树的操作).doc_第1页
数据结构程序报告(平衡二叉树的操作).doc_第2页
数据结构程序报告(平衡二叉树的操作).doc_第3页
数据结构程序报告(平衡二叉树的操作).doc_第4页
数据结构程序报告(平衡二叉树的操作).doc_第5页
资源描述:

《数据结构程序报告(平衡二叉树的操作).doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、计算机科学学院数据结构课程设计报告平衡二叉树操作学生姓名:学号:班级:指导老师:报告日期:1.需求分析1.建立平衡二叉树并进行创建、查找、插入、删除等功能。2.设计一个实现平衡二叉树的程序,可进行创建、查找、插入、删除等操作,实现动态的输入数据,实时的输出该树结构。3.测试数据:自选数据2.概要设计1.抽象数据类型定义:typedefstructBSTNode{intdata;intbf;//节点的平衡因子structBSTNode*lchild,*rchild;//左右孩子指针}BSTNode,*BSTree;voidCreat

2、BST(BSTree&T);//创建平衡二叉树voidR_Rotate(BSTree&p);//对以*p为根的二叉排序树作左旋处理voidL_Rotate(BSTree&p);//对以*p为根的二叉排序树作左旋处理voidLeftBalance(BSTree&T);//对以指针T所指结点为根的二叉树作左平衡旋转处理voidRightBalance(BSTree&T);//对以指针T所指结点为根的二叉树作右平衡旋转处理boolInsertAVL(BSTree&T,inte,bool&taller);//插入结点eboolSearch

3、BST(BSTree&T,intkey);//查找元素key是否在树T中voidLeftBalance_div(BSTree&p,int&shorter);//删除结点时左平衡旋转处理voidRightBalance_div(BSTree&p,int&shorter);//删除结点时右平衡旋转处理voidDelete(BSTreeq,BSTree&r,int&shorter);//删除结点intDeleteAVL(BSTree&p,intx,int&shorter);//平衡二叉树的删除操作voidPrintBST(BSTreeT

4、,intm);//按树状打印输出二叉树的元素2.主程序的流程请输入操作的选项编号(1-5)1---创建平衡二叉树2---查找3---插入4---删除5---结束3.各模块之间的层次调用退出输出删除插入查找平衡化输入数据元素显示主菜单主模块1.详细设计1.以平衡二叉树的插入和平衡化为例:boolInsertAVL(BSTree&T,inte,bool&taller){//若存在平衡的二叉排序树T中不存在和e有相同关键字的节点,则插入一个数据元素为e//的新结点,并返回1,否者返回0。若因插入而使二叉排序树失去平衡,则作平衡旋转理,/

5、/布尔变量taller反映T长高与否。if(!T)//插入新结点,树“长高”,置taller为true{T=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=true;}else{if(EQ(e,T->data))//树中已存在和有相同关键字的结点{taller=false;printf("已存在相同关键字的结点");return0;}//则不再插入if(LT(e,T->data))//应继续在*T的左子树中进行

6、搜索{if(!InsertAVL(T->lchild,e,taller))return0;//未插入if(taller)//已插入到*T的左子树中且左子树“长高”switch(T->bf)//检查*T的平衡度{caseLH://原本左子树比右子树高,需要作左平衡处理LeftBalance(T);taller=false;break;caseEH://原本左子树、右子等高,现因左子树增高而使树增高T->bf=LH;taller=true;break;caseRH://原本右子树比左子树高,现左、右子树等高T->bf=EH;talle

7、r=false;break;}//switch(T->bf)}//ifelse//应继续在*T的右子树中进行搜索{if(!InsertAVL(T->rchild,e,taller))return0;//未插入if(taller)//已插入到*T的右子树中且右子树“长高”switch(T->bf)//检查*T的平衡度{caseLH://原本左子树比右子树高,现左、右子树等高T->bf=EH;taller=false;break;caseEH://原本左子树、右子等高,现因右子树增高而使树增高T->bf=RH;taller=true;

8、break;caseRH://原本右子树比左子树高,需要作右平衡处理RightBalance(T);taller=false;break;}//switch(T->bf)}//else}//elsereturn1;}//InsertAVL2.说明:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。