- 1、本文档共59页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
50 30 80 20 90 85 40 35 88 32 例如: 二叉排序树 给定值 == 35 , 50 30 40 35 90 , 50 80 90 95 , 三、基于树的查找 class BinaryTreeNode { int data; //结点中的数据元素,以整型为例 BinaryTreeNode left; //指向左孩子的对象 BinaryTreeNode right; //指向右孩子的对象 } 二叉排序树的查找算法 采用二叉链表存储结构 三、基于树的查找 public class BinarySearch { public BinaryTreeNode binary_search(BinaryTreeNode root,int kx){ BinaryTreeNode p,f; p=root; f=p; while(p!=null){ if(kx==p.data) return p; //查找结束 else if(kxp.data){//在左子树中继续查找 f=p; p=p.left; }else{//在右子树中继续查找 f=p; p=p.right; } } return null; //查找失败 } } 三、基于树的查找 三、基于树的查找 3.二叉排序树的插入 插入过程:设待插入结点的关键字为kx,为将其插入,先要在二叉排序树中进行查找,若查找成功,按二叉排序树定义,待插入结点已存在,不用插入;查找失败时,才进行插入操作。 中序遍历二叉排序树可得到一个关键字的有序序列 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 【例】记录的关键字序列为: 10, 18, 3, 8, 12, 2, 7 ,则构造一棵二叉排序树的过程为: 三、基于树的查找 首先在BinaryTreeNode类中增加构造函数: public BinaryTreeNode(int data,BinaryTreeNode left,BinaryTreeNode right){ this.data=data; this.left=left; this.right=right; } 然后创建新类BinaryInsert,并定义BinaryInsert方法,算法如下: /* *程序功能:在根结点为root的二叉排序树中插入关键字值等于kx的结点,插入成功返回*true,失败返回false。 */ public class BinaryInsert { public boolean binary_insert(BinaryTreeNode root,int kx){ 二叉排序树的插入算法 三、基于树的查找 if(root==null){//建立根结点 root=new BinaryTreeNode(kx,null,null); return true; } return insert(root,kx);//插入kx到以root为根的二叉排序树中 } //将kx插入到以p为根的子树中,递归算法 private boolean insert(BinaryTreeNode p,int kx){ if(kx==p.data) return false;//不插入关键字重复的结点 else if(kxp.data) if(p.left==null){//建立叶子结点作为p的左孩子 p.left=new BinaryTreeNode(kx,null,null); return true; } else //将value插入到p的左子树中 return insert(p.left,kx); 三、基于树的查找 else if(p.right==null){//建立叶子结点作为p的右孩子 p.right=new BinaryTreeNode(kx,null,null); return true; } else //将value插入到p的右子树中 return insert(p.right,kx); } } 三、基于树的查找 三、基于树的查找 4.二叉排序树的删除 删除过程:设待删结点为p(设p为指向待删除结点的对象),其双亲结点为parent,删除过程分以下三种情况进行讨论: 。 (1)被删除的结点是叶子; (2)被删除的结点只有左子树,或者只有右子树; (3)被删除的结点既有
您可能关注的文档
- 收房时要先看开发商的“三书一证一表”解读.doc
- 收费人员岗前培训应知应会手册4正文解读.doc
- 收费系统收费文明服务管理标准解读.docx
- 数的顺序和组成解读.pptx
- 数电chapter9解读.ppt
- 数电复习要点解读.ppt
- 数电实验报告实验二利用MSI设计组合逻辑电路解读.docx
- 数据仓库1解读.ppt
- 数据仓库解决方案概述解读.ppt
- 数据仓库实验二解读.docx
- 《GB/Z 44363-2024致热性 医疗器械热原试验的原理和方法》.pdf
- GB/T 16716.6-2024包装与环境 第6部分:有机循环.pdf
- 中国国家标准 GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 《GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统》.pdf
- GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 中国国家标准 GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 44305.2-2024塑料 增塑聚氯乙烯(PVC-P)模塑和挤塑材料 第2部分:试样制备和性能测定.pdf
- 《GB/T 44315-2024科技馆展品设计通用要求》.pdf
- GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 39560.9-2024电子电气产品中某些物质的测定 第9 部分:气相色谱-质谱法(GC-MS)测定聚合物中的六溴环十二烷.pdf
最近下载
- 理财教材《小狗钱钱》.pdf
- 护理品管圈问题解决型之提高慢性肾功能不全患者饮食指导知晓率.pptx VIP
- 复旦投毒案林森浩(详细的参考资料整理).docx
- Axure RP原型设计图解微课视频教程(Web+App)(刘刚)PPT全套完整教学课件.pptx
- 2024年国家电网招聘之财务会计类题库附参考答案(轻巧夺冠).docx
- 1精益管理倡导者培训.pptx
- 整本书阅读 《朝花夕拾》(同步课件) 七年级语文上册(统编版2024).pptx
- 2024-2029年中国房地产投资行业发展分析及投资风险预警与发展策略研究报告.docx
- 文旅融合背景下的文化遗产活化措施.pptx VIP
- 非物质文化遗产活化策略PPT.pptx VIP
文档评论(0)