




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030数码相机行业市场现状供需分析及重点企业投资评估规划分析研究报告
- 2025-2030护肤品行业发展分析及投资价值研究咨询报告
- 2025-2030手机相机模组行业市场发展分析及前景趋势与投资研究报告
- 人教部编版语文七年级上册《 10 再塑生命的人 》(新课标单元整体教学设计+课时教学设计)
- 2025-2030幽门螺杆菌检测试剂盒市场供给预测分析及竞争前景可行性规划报告
- 2025-2030干红葡萄酒行业市场发展分析及前景趋势与投资研究报告
- 2025-2030差速器壳项目可行性研究报告
- 2025-2030少儿期刊出版行业市场现状供需分析及投资评估规划分析研究报告
- 2025-2030小商品行业市场深度调研及前景趋势与投资研究报告
- 2025-2030室内乳胶漆行业市场现状供需分析及投资评估规划分析研究报告
- 城镇燃气安全技术与管理
- 清产核资工作方案
- 初级会计实务全书电子教案
- 2025年安徽安徽省合肥汽车客运有限公司招聘笔试参考题库含答案解析
- 安徽省 2025 年九年级中考历史模拟试卷二(含答案)
- 武汉市部分学校2024-2025学年下学期3月考七年级数学试题(含答案)
- 2024-2030全球动态细胞分析行业调研及趋势分析报告
- 2025年临床试验数据保密协议
- 湖南中烟工业有限责任公司招聘考试真题2024
- 《X射线管原理与应用》课件
- 2024年湖北省襄阳市第四中学第五中学自主招生考试语文试卷
评论
0/150
提交评论