二叉平衡排序树课程设计.doc
《二叉平衡排序树课程设计.doc》由会员分享,可在线阅读,更多相关《二叉平衡排序树课程设计.doc(20页珍藏版)》请在咨信网上搜索。
1、数据结构课程设计数据结构课程设计报告设计题目:_二叉平衡排序树_ 姓 名:_宗小林_ 学 号:_ 210908046_ 专 业:_ 计算机科学与技术_ 院 系:_计算机科学与技术学院_班 级:_ 0902_指导教师:_ 王江涛_2011年 6 月 10 日摘要:树形结构是以分支关系定义的层次结构,它是一种重要的非线性结构。树形结构在客观世界里普遍存在。而平衡二叉树因其特性:1、左右子树都是平衡二叉树。2、左子树和右子树的深度之差的绝对值不超过1.然而在二叉查找树中不论是插入还是删除,都需要在在二叉树上进行查找,查找的效率取决于二叉树的形态,二叉树越匀态,树的层次越少,平均查找深度越小,该树的查
2、找效率就越高;构造一棵形态均匀的二叉查找树与结点插入的顺序有关,而结点插入的顺序往往不是随着人的而定的、由此便引发了平衡二叉树关键词:二叉树、平衡二叉树、查找Abstract: Tree shape structure with the level structure that the sub - branch relates to definition, It is a kind of nonlinear structure. The tree shape structure is universal to exist in the objective world. But two fork
3、 the equilibrium tree is because of its characteristic:1. The or so son tree is all equilibrium two fork treeses.2. The bad absolute value anti of the depth of left son tree and right son tree over 1. However check to seek in two forks tree amid in spite of plug into or delete, all requirement in al
4、l aspects two the fork treetop progress check to seek, Check the efficiency for seeking to be decided by the appearance of two fork trees,Two fork tree more even state, the level of tree is more little, check to seek depth on the average more small, the checking of tree seeks an efficiency more high
5、.Two forks that construct an appearance blance check to seek a tree to have something to do with node plugging into of sequence, But the node plug into of sequence usually be not along with person of but settle ofFrom here and then kindled equilibrium two fork treeses.Keywords: binary treebanlanced
6、binary treesearch目 录1 问题描述42 需求分析43 概要设计44 数据结构设计55 算法设计56 程序测试与实现187 调试分析198 遇到的问题及解决办法209 心得体会201 问题描述创建二叉平衡排序树要求:1、 输入数据的数量不得低于15个2、 建立二叉平衡排序树(要求包括LL型LR型RR型RL型四种调整方式)3、完成任意数据的查找(要求给出查找执行的次数)。2 需求分析1 迷本程序的功能包括二叉平衡树的创建、新结点的插入和删除、中序和先序(数据的查找)遍历二叉树。2 程序运行后显现提示信息,等候用户输入1-5以进入相应的操作功能。3 用户输入数据完毕,程序将输出运行
7、结果。4 测试数据应为不少于15个整形数据。3 概要设计1 总体使用的头文件:#include#include /cout函数要使用#include /setw要使用2.常量定义:#define LH 1 /左高#define EH 0 /等高#define RH -1 /右高#define TRUE 1#define FALSE 0 3.全局变量定义: int taller=0; /taller反映T长高与否 int shorter=0; /shorter反映T变矮与否 4.几个关键函数:(1)void Midorder(BSTree T) /树的中序遍历递归算法,一并输出平衡因子和左右结点
8、的值,无返回值类型;(2)BSTree R_Rotate(BSTree p) /以p为根的二叉排序树作右旋处理,处理之p指向新的树根节点即旋转处理之前的左子树根节点;(3) BSTree L_Rotate(BSTree p) /以p为根的二叉排序树作左旋处理,处理之p指向新的树根节点即旋转处理之前的右子树根节点;(4) BSTree LeftBalance(BSTree T) /对以指针T所指结点为根的二叉树作做左平衡旋转处理,本算法结束时指针T指向新的根节点;(5) BSTree RightBalance(BSTree T) /对以指针T所指结点为根的二叉树作做右平衡旋转处理,本算法结束时指
9、针T指向新的根节点;(6) BSTree InsertAVL(BSTree T,int e) /向平衡树中插入一个节点,返回插入后的新根节点;(7) BSTree LeftBalancel(BSTree p) /删除节点时对以指针T所指节点为根的二叉树作左平衡旋转处理,本算法结束时指针T指向新的根节点;(8) BSTree RightBalancel(BSTree p) /删除节点时对以指针T所指节点为根的二叉树作右平衡旋转处理,本算法结束时指针T指向新的根节点;(9) BSTree Delete(BSTree q, BSTree r) /对节点进行删除处理,本算法结束时q指针指向新的根节点。
10、(10)BSTree DeleteAVL(BSTree p, BSTree e) /找到要删除的节点,调用删除函数对其进行删除,本算法结束时指针p指向新的根结点 (11)BSTree CreatNode(int nodeValue) /建立关键字值为nodeValue的新结点,返回根节点4 数据结构设计1 数据结构定义/根据平衡二叉树的特点可以定义平衡二叉树的存储结构/二叉排序树的类型定义Typedef struct BSTNode int data; /结点值 int bf; /结点的平衡因子 struct BSTNode *lchild,*rchild; /分别指向左右孩子的指针 BSTN
11、ode,* BSTree; /同时声明一个BSTNode和一个指针类型的BSTree5 算法设计5.1 算法分析如何去构造一棵平衡二叉树呢?下面来看一个具体的例子,假设表中关键子序列为(1,2,3,9,5)。空树和一个结点(1)的树显然都是平衡的二叉树。插入2之后仍是平衡的,只是根结点的平衡因子BF由0变为-1;继续插入3之后,由于结点1的BF由-1变为-2,出现了不平衡现象。这就好比一根扁担出现了一根轻一根重的现象。如将扁担的支撑点由结点1改为结点2,扁担的两头就平衡了。因此,可以对树做一个左逆时针“旋转”的操作,令结点2为根,而结点1作为它的左孩子,这样,结点1和2的平衡因子都为0,而且仍
12、然保持二叉查找树的特性。继续插入9和5之后,由于结点3的BF由-1变成-2,出现了新的不平衡因子,需进行调整。但此时由于结点5插在结点9的左子树上,因此不能还像上次那样做简单的调整。对于以结点3为根的子树来说,既要保持二叉查找树的特性又要保持平衡,所以必须以5作为根结点而使3成为它的左子树的根,9成为它的右子树的根。这就好比对树做了;两次“旋转”操作-先向右顺时针旋转,后向左逆时针旋转,使二叉树由不平衡变为平衡。总之,在构造一棵平衡二叉树或在平衡二叉树上插入一个结点时,可能造成二叉树失衡,这时就要对失衡的二叉树进行平衡化处理。平衡处理的方法有4种:LL、RR、LR、RL5.2 算法实现#inc
13、lude#include /cout函数要使用#include#define LH 1 /左高#define EH 0 /等高#define RH -1 /右高#define TRUE 1#define FALSE 0int taller=0; /taller反映T长高与否int shorter=0; /shorter反映T变矮与否Typedef struct BSTNode int data; /结点值 int bf; /结点的平衡因子 struct BSTNode *lchild,*rchild; /分别指向左右孩子的指针 BSTNode,*BSTree; /同时声明一个BSTNode和一
14、个指针类型的BSTree/建立新结点BSTree CreatNode(int nodeValue) BSTree node; node=(BSTree)malloc(sizeof(BSTree); node-data=nodeValue; node-bf=0; node-lchild=NULL;node-rchild=NULL;return node;/新建二叉树函数BSTree BuildTree(BSTree r)/如果传入根结点不为空,则数以构建过,退出函数if(r!=NULL)cout二叉平衡树已建立;return NULL;/根节点为空则开始创建cout请输入节点值,输入零则结束no
15、deValue;while(nodeValue)/插入任何小于0的数值BSTree node=CreatNode(nodeValue);/如果根为空,则将此节点设置为根结点,否则将此节点作为非根节点插入if(r=NULL)r=node;elser=InsertAVL(r.nodeValue);cinnodeValue;/获取用户输入的新值return r;void MidOrder(BSTree T) /树的中序遍历递归算法,一并输出平衡因子和左右结点的值,无返回值类型; /中序遍历的特点是当二叉树为空时则空操作,否则 /1,中序遍历左子树/2,访问根结点 /3,中序遍历右子树if(T-lch
16、ild) MidOrder(T-lchild);if(T-data) /以适当的形式格式化输出各个节点及其附加信息可以方便用户重构二叉树 coutsetw(4)datasetw(6)bf;if(T-lchild) coutsetw(8)lchild-data; else coutsetw(8)rchild) cout setw(8)rchild-data; else coutsetw(8)-;coutrchild) MidOrder(T-rchild);void RootOrder(BSTree T) /树的先序遍历递归算法,一并输出平衡因子和左右结点的值,无返回值类型; /先序遍历的特点是当
17、二叉树为空时则空操作,否则 /1,访问根结点/2,先序遍历左子树 /3,先序遍历右子树if(T-data) coutsetw(4)datasetw(6)bf; if(T-lchild) coutsetw(8)lchild-data; else coutsetw(8)rchild) cout setw(8)rchild-data; else coutsetw(8)-;coutlchild) RootOrder(T-lchild);if(T-rchild) RootOrder(T-rchild);BSTree R_Rotate(BSTree p) /以p为根的二叉排序树作右旋处理,处理之p指向新的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 平衡 排序 课程设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。