二叉平衡排序树.docx

上传人:王** 文档编号:796983 上传时间:2024-01-14 格式:DOCX 页数:20 大小:46.35KB
下载 相关 举报
二叉平衡排序树.docx_第1页
第1页 / 共20页
二叉平衡排序树.docx_第2页
第2页 / 共20页
二叉平衡排序树.docx_第3页
第3页 / 共20页
二叉平衡排序树.docx_第4页
第4页 / 共20页
二叉平衡排序树.docx_第5页
第5页 / 共20页
二叉平衡排序树.docx_第6页
第6页 / 共20页
二叉平衡排序树.docx_第7页
第7页 / 共20页
二叉平衡排序树.docx_第8页
第8页 / 共20页
二叉平衡排序树.docx_第9页
第9页 / 共20页
二叉平衡排序树.docx_第10页
第10页 / 共20页
亲,该文档总共20页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《二叉平衡排序树.docx》由会员分享,可在线阅读,更多相关《二叉平衡排序树.docx(20页珍藏版)》请在优知文库上搜索。

1、数据结构课程设计报告专业:计算机科学与技术班级:2009级1姓名:陈雪敏指导教师:张珑学号:2009040608二叉平衡排序树一、课程设计内容问题描述:从一棵空树开始创建,在创建过程中,保证树的有序性,同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求:L创建(插入、调整、改组)2.输出二、概要设计1、.主要数据结构定义typedefstructnodenode;structnodenode*parent;node*left;node*right;intbalance;左右子树高度之差intkey;I.2:主要函数说明intSearchNode(intke

2、y,node*root,node*parent):按key查找结点node*minNode(node*root):树root的最小结点node*maxNode(node*root):树root的最大结点node*preNode(node*target):求前驱结点node*nextNode(node*target):求后继结点node*adjustAVL(node*root,node*parent,node*child):调整,保证二叉树的平衡性node*insertNode(intkey,node*root):插入node*deleteNode(intkey,node*root):删除nod

3、e*CreateAVL(int*data,intsize):建造新的二叉树voidinterordertraverse(node*root):中序遍历voidpreordertraverse(node*root):先序遍历3、二叉排序树的插入和删除a.二叉排序树的插入在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。插入过程:若二叉排序树已存在,则返回根节点;当节点不存在时,将待插结点关键字key和树根关键字parent-key进行比较,若keykey,则插入到根的左子树中,否则,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同,如此进行下去,直到把结点作为一

4、个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。并且注意二叉树的平衡性,时刻调整。b.二叉排序树的删除假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性,可设*parent是*Parent-left;的左孩子。下面分3种情况进行讨论:(1)若*parent结点为叶子结点,即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构,则只需要修改其双亲结点的指针即可。(2)若*parent结点只有左子树PL或者只有右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然,作此修改也不破坏二叉排序树的特性。(3)若*parent结点的左子

5、树和右子树均不空。并且注意二叉树的平衡性,时刻调整。4、中序遍历和先序遍历voidinterordertraverse(node*root)中序遍历(if(root!=NULL)(interordertraverse(root-left);printf(,%d,%dn”,root-key,root-balance);interordertraverse(root-right);)voidpreordertraverse(node*root)先序遍历if(root!=NULL)printf(z,%d,%dn”,root-key,root-balance);preordertraverse(roo

6、t-left);preordertraverse(root-right);1J5、调整二叉树的平衡性node*adjustAVL(node*root,node*parent,node*child)主要有四种调整类型根据平衡因子主要有LR、LL、RL、RR(1)根据Parent-balance的值为2时,child-balance=-1时是LR型,否则为LL型;if(child-balance=-1)LR型(cur-child-right;cur-parent=parent-parent;child-right=cur-left;if(cur-left!=NULL)cur-left-parent

7、=child;parent-left=cur-right;if(cur-right!=NULL)cur-right-parent-parent;cur-left=child;child-parent-cur;cur-right=parent;if(parent-parent!-NULL)if(parent-parent-left=parent)parent-parent-left-cur;elseparent-parent-right=cur;elseroot=cur;parent-parent-cur;if(cur-balance=0)parent-balance=0;child-balan

8、ce=0;)elseif(cur-balance=-1)(parent-balance-0;child-balance=1;elseparent-balance=-1;child-balance-0;)cur-balance=0;)else/LL型child-parent-parent-parent;parent-left=child-right;if(child-right!=NULL)child-right-parent=parent;child-right=parent;if(parent-parent!=NULL)if(parent-parent-left=parent)parent-

9、parent-left=child;elseparent-parent-right-child;elseroot=child;parent-parent=child;if(child-balance=1)插入时child-balance-O;parent-balance=O;)else删除时child-balance=-1;parent-balance-1;)break;(2)、Parent-balance的值为-2时,child-balance=1时是RL型,否则为RRif(child-balance=1)/RL型(cur=child-left;cur-parent=parent-paren

10、t;child-left=cur-right;if(cur-right!=NULL)cur-right-parent=child;parent-right=cur-left;if(cur-left!=NULL)cur-left-parent=parent;cur-left=parent;cur-right=child;child-parent-cur;if(parent-parent!=NULL)if(parent-parent-left=parent)parent-parent-left=cur;elseparent-parent-right=cur;elseroot-cur;parent-

11、parent=cur;if(cur-balance=0)(parent-balance=0;child-balance=0;elseif(cur-balance=1)parent-balance=0;child-balance-1;)else(parent-balance-1;child-balance=O;cur-balance=O;)else/RR型child-parent=parent-parent;parent-right=child-left;if(child-left!=NULL)child-left-parent=parent;child-left=parent;if(paren

12、t-parent!-NULL)if(parent-parent-left=parent)parent-parent-left-child;elseparent-parent-right=child;elseroot=child;parent-parent-child;if(child-balance=-1)插入时child-balance=0;parent-balance=0;else删除时child-balance-1;parent-balance=-1;)break;6、主函数Voidmain()给出了一组数据1,13,7,4),对数据中序遍历和先序遍历,然后是插入、删除、查询、退出操作。

13、三、系统实现运行环境Windows7操作系统,MicrosoftVisualC+6.0。四、程序#includeinclude#include#include#includeinclude/assert用于调试声明宏,用于定位程序开发中的逻辑错误当参数expression为false时程序执行被中断tjedefstructnodenode;structnodenode*parent;node*left;node*right;intbalance;平衡因子(左右子树高度之差)intkey;);externvoidinterordertraverse(node*root);中序遍历externvo

14、idpreordertraverse(node*root);前序遍历intSearchNode(intkey,node*root,node*parent)按key查找结点(node*temp;assert(root!=NULL);temp=root;*parent=root-parent;while(temp!=NULL)(if(temp-key=key)return1;else*parent=temp;if(temp-keykey)temp=temp-left;elsetemp=temp-right;returnO;)node*minNode(node*root)树root的最小结点returnNULL;while(root-left!=NULL)root=root-left;returnroot;node*max

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!