数据结构与算法课件13动态查找-二叉排序树的查找_第1页
数据结构与算法课件13动态查找-二叉排序树的查找_第2页
数据结构与算法课件13动态查找-二叉排序树的查找_第3页
数据结构与算法课件13动态查找-二叉排序树的查找_第4页
数据结构与算法课件13动态查找-二叉排序树的查找_第5页
已阅读5页，还剩2页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

8.3动态查找动态查找特点：表结构本身是在查找中动态生成，对于给定值K，如表中存在，则查找成功；否则在适当的位置插入K动态查找的结构主要针对二叉树结构讲解。二叉排序树

又称为二叉查找树,它或者是空树，或者是满足如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。（3）它的左、右子树本身又各是一棵二叉排序树。8.3动态查找例如，由关键字值序列{50，70，20，10，60，30，80，5，75，35，95}构成的一棵二叉排序树如下图所示。按中序遍历该树所得到的中序序列是一个递增有序序列如上例：（5,10,20,30,35,50,60,70,75,75,80,95）二叉排序树的查找在二叉排序树中查找的基本思想用给定值k与根结点关键字值比较，如果k小于根结点的值，就继续在左子树中查找，否则将继续在右子树中查找，依此方法，一直查找下去，直至查找成功或查找失败为止。二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败（2）将给定值k与根结点的关键字值比较，若相等，则查找成功（3）若给定值k小于根结点的关键字值，则在左子树中继续搜索，如果左子树为空，则查找失败。（4）否则，在右子树中继续查找，如果右子树为空，则查找失败二叉排序树结构的定义：typedefstructBSTNode{KeyTypekey;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;二叉排序树的查找算法描述如下BSTreef;/*f指向移动指针p的双亲*/BSTreeBSTSearch(BSTreet,KeyTypek){ /*在根结点为t的二叉排序树中查找关键字值

等于k的结点*/ p=t;f=NULL;while(p!=NULL){if(k==p->key)return(p); /*查找成功*/elseif(k<p->key){f=p;p=p->lchild;} /*在左子树中继续查找*/else{f=p;p=p->rchild;} /*在右子树中继续查找*/

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论