




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2016数据结构Data structure讲授:贺宁 二叉排序树的插入与生成常州信息职业技术学院0203二叉排序树的插入(1)插入方法在二叉排序树中插入新结点,设其关键字域的值为key,要保证插入后仍满足BST性质。插入过程是:若二叉排序树T为空,则为待插入结点申请存储空间,并令其为根;若二叉排序树T不空,则将待插入结点关键字key与根的关键字比较:(i)若key=T-key,则树中已有此关键字key,无须插入;(ii)若keykey,则将key插入根的左子树中;(iii)若keyT-key,则将key插入根的右子树中。子树中的插入过程与上述的树中插入过程相同。如此进行下去,直到将key作为
2、一个新的叶结点关键字插入到二叉排序树中,或者直到发现树中已有此关键字为止。 04二叉排序树的插入(2)递归算法int InsertBSTR(BSTree *Tptr,KeyType key)/二叉排序树插入新结点递归算法,插入成功返回1,失败返回0if(!(*Tptr)(*Tptr)=(BSTNode *)malloc(sizeof(BSTNode);if(*Tptr =NULL) puts (内存申请不成功!);return 0; (*Tptr)-key=key;(*Tptr)-lchild=NULL;(*Tptr)-rchild=NULL;elseif(*Tptr)-key=key)ret
3、urn 0;if(keykey)InsertBSTR(&(*Tptr)-lchild,key);elseInsertBSTR(&(*Tptr)-rchild,key); return 1;05二叉排序树的生成 二叉排序树的生成,是从空的二叉排序树开始,每输入一个结点数据,就调用一次插入算法将它插入到当前已生成的二叉排序树中。BSTree CreateBST(void) /输入一个结点序列,建立一棵二叉排序树,将根结点指针返回BSTree T=NULL;/初始时T为空树KeyType key;scanf(%d,&key);/读入一个关键字while(key)/假设key=0是输入结束标志InsertBSTR(&T,key);/将key插入二叉排序树Tscanf(%d,&key);/读入下一关键字return T;/返回建立的二叉排序树的根指针 注意二叉排序树的形态与输入序列的顺序有关,第一个输入的结点一定是根结点。二叉排序树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉排序树,其实质是对此关键字序列进行排序,这种排序的平均执行时间亦为O(nlgn),“排序树”的名称也由此而来。06二叉排序树的生成 按输入序列(25,32,9,18,27,6,29)的顺序构造二叉排序树T,具体过程如下图所示。图示 二叉排序树生成过程6T初始为空T25插入25T
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 第5课 活动B《我和蔬菜交朋友·我的蔬菜朋友》(教学设计)-2023-2024学年一年级下册综合实践活动浙教版
- 《10以内的连加、连减》教学设计-2024-2025学年数学苏教版(2024)一年级上册
- 2024年五年级语文下册 第五单元 习作例文教学实录 新人教版
- 山东省郯城第三中学高一体育 挺身式跳远教学实录 新人教版
- 池河镇八年级历史下册 第三单元 建设中国特色社会主义 第10课 伟大的历史转折教学实录1 北师大版
- 2025年分子诊断试剂合作协议书
- 中国呼吸道疾病检测行业市场规模测算逻辑模型 头豹词条报告系列
- 精密仪器振动隔离桌行业深度调研及发展战略咨询报告
- 电影-电视剧植入广告创新行业跨境出海战略研究报告
- 法律高级培训企业制定与实施新质生产力战略研究报告
- 隧道光面爆破交流材料
- 晶体的双折射课件
- 医院院内科研项目管理办法
- 天津马城马术赛马休闲骑乘现代马业项目商业计划书
- 2022-2023学年高中政治统编版选择性必修二5-1家和万事兴 第1课时 学案
- 土的击实试验JTG34302020
- 大气污染防治与总量减排
- 引风机检修工艺规程
- GB/T 3836.9-2021爆炸性环境第9部分:由浇封型“m”保护的设备
- GB/T 20001.4-2015标准编写规则第4部分:试验方法标准
- GB/T 19666-2005阻燃和耐火电线电缆通则
评论
0/150
提交评论