![点击分享此内容可以赚币 分享](/master/images/share_but.png)
用顺序和二叉链表作存储结构实现二叉排序树.doc
《用顺序和二叉链表作存储结构实现二叉排序树.doc》由会员分享,可在线阅读,更多相关《用顺序和二叉链表作存储结构实现二叉排序树.doc(30页珍藏版)》请在咨信网上搜索。
1、(完整word版)用顺序和二叉链表作存储结构实现二叉排序树河南城建学院课程设计报告书专 业:计算机科学与技术 课程设计名称:用顺序和二叉链表作存储结构实现二叉排序树题 目:班 级:学号:姓名:同 组 人 员:指 导 老 师:完 成 时 间:摘要数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设中的二叉排序树,可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树,一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。关键词:二叉排序树;中序遍历;搜索结点;删除结点;CC+目录目录2第一章课程设计题目及要求3
2、1.1C语言简介31.2 课程设计题目31.3 课程设计要求3第二章 算法思想42.1 二叉排序树的定义42.2 二叉排序树的实现42.2.1 建立二叉排序树52.2.2 二叉排序树的中序遍历52.2.3 二叉排序树中元素的查找52.2.4 二叉排序树中元素的删除.5 第三章算法实现73.1 程序设计思想73.2 程序模块73.3 流程图103.4 源程序代码11第四章测试与分析174.1 程序调试174.2 调试结果分析19总 结20心得体会21参考文献22第一章 课程设计题目及要求1.1 C/ C +语言简介C语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。语言
3、的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型,便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址,进行位(bit)一级的操作。由于语言实现了对硬件的编程操作,因此语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发,也适合于应用软件的开发。C是C+的基础,C+语言和语言在很多方面是兼容的,C+程序员可以利用C+与C的兼容性而直接并有效的使用大量现成的程序库,从而开发出更简洁更高效的系统。1.2 课程设计题目用顺序和二叉链表作存储结构实现二叉排序树:(1)以回车(n)为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)输
4、入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”。1.3课程设计要求在处理题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告。对于稍复杂的程序设计,要充分利用模块化程序设计方法,自顶向下,逐步细化,在整体思路确定的情况下,考虑所需模块数,各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述,用流程图或伪代码表示。说明:在设计的过程中,步骤1-步骤4往往是反复进行,在后续步骤中发现问题,往往需要从头重新分析、设计。
5、第二章 算法思想2.1二叉排序树的定义 二叉排序树的定义:二叉排序树或者是一棵空树,或者是一棵具有如下性质的二叉树:(1)每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同;(2) 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;(3) 若它的右子树非空,则右子树上所有结点的值均大于根结点的值;(4) 左、右子树本身又各是一棵二叉排序树2.2二叉排序树的实现2.2.1建立二叉排序树建二叉树的结点至少应当包含三个域,分别存放结点的数据data,左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针,它指向二叉树的根结
6、点,其作用是当作树的访问点从空的二叉排序树开始,经过一系列的查找插入操作以后,生成了一棵二叉排序树。根据二叉排序树的定义,建立一棵二叉排序树的过程是按照待排序序列元素的先后次序,不断动态生成二叉树的结点,逐个插入到二叉树中。若p为根结点指针,b为当前待插入元素,其过程可以描述为:若为空树(p=nil),动态生成一个结点,其数据域为当前待插入元素b,左、右指针域为“空”,p指向该结点。若非空树,比较b与根结点数据data(p)如果bdata)*p=t;return (1); else if(keydata) searchBST(t-lchild,key,t,p); elsesearchBST(t
7、-rchild,key,t,p); 对二叉排序树进行中序遍历:inorderTraverse(node *t)if(*t)if(inorderTraverse(&(*t)-lchild)printf(%d,(*t)-data);if(inorderTraverse(&(*t)-rchild); return(1) ;删除节点node Delete(node t,intkey) /*删除函数*/nodep=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*/if(p-data=key) break;q=p;if(p-datakey) p=p-lchild;else p
8、=p-rchild;if(p=NULL)returnt;/*查找失败*/if(p-lchild=NULL) /*p指向当前要删除的结点*/if(q=NULL) t=p-rchild;/*q指向要删结点的父母*/else if(q-lchild=p)q-lchild=p-rchild;/*p为q的左孩子*/else q-rchild=p-rchild;/*p为q的右孩子*/free(p);else /*p的左孩子不为空*/f=p;s=p-lchild;while(s-rchild) /*左拐后向右走到底*/f=s;s=s-rchild;if(f=p)f-lchild=s-lchild;/*重接f
9、的左子树*/elsef-rchild=s-lchild; /*重接f的右子树*/p-data=s-data;free (s);returnt;3.3流程图初始化输入数据无X查找函数中序遍历遍历结果插入节点X1 2删除节点存在含x的结点不存在输出遍历结果3.4源程序代码用顺序存储实现:#include#includetypedef struct Tnodeint data; /*输入的数据*/structTnode*lchild,*rchild; /*结点的左右指针,分别指向结点的左右孩子*/*node,BSTnode;searchBST(node t,int key,node f,node *
10、p) /*查找函数*/if(!t)*p=f;return (0); /*查找不成功*/else if(key=t-data)*p=t;return (1); /*查找成功*/else if(keydata) searchBST(t-lchild,key,t,p); /*在左子树中继续查找*/elsesearchBST(t-rchild,key,t,p); /*在右子树中继续查找*/insertBST(node *t,int key)/*插入函数*/node p=NULL,s=NULL;if(!searchBST(*t,key,NULL,&p) /*查找不成功*/s=(node)malloc(s
11、izeof(BSTnode);s-data=key;s-lchild=s-rchild=NULL;if(!p)*t=s; /*被插结点*s为新的根结点*/else if(keydata) p-lchild=s;/*被插结点*s为左孩子*/elsep-rchild=s;/*被插结点*s为右孩子*/return (1);else return (0);/*树中已有关键字相同的结点,不再插入*/inorderTraverse(node *t)/*中序遍历函数*/if(*t)if(inorderTraverse(&(*t)-lchild)/*中序遍历根的左子树*/printf(%d,(*t)-data
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 顺序 二叉 链表作 存储 结构 实现 二叉排序树
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。