数据结构-基于C++语言（微课版） 课件 1-4 二叉排序树_第1页
数据结构-基于C++语言（微课版） 课件 1-4 二叉排序树_第2页
数据结构-基于C++语言（微课版） 课件 1-4 二叉排序树_第3页
数据结构-基于C++语言（微课版） 课件 1-4 二叉排序树_第4页
数据结构-基于C++语言（微课版） 课件 1-4 二叉排序树_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

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

文档简介

二叉排序树中查找结点；二叉排序树中删除结点。本节目录：本节内容：二叉排序树二叉排序树

二叉排序树的查找

在二叉排序树中查找给定值k的过程是：⑴若root是空树，则查找失败；⑵若k==root->data，则查找成功，返回root;⑶若k＜root->data，则在root的左子树上查找;⑷若k>root->data，则在root的右子树上查找。上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率在于只需查找二个子树之一。二叉排序树的查找

例：在二叉排序树中查找关键字值为35，95的过程：5030208090858840353250302080908588403532二叉排序树的查找

二叉排序树的查找性能分析二叉排序树的查找性能取决于二叉排序树的形状，在O(log2n)和O(n)之间。由序列{3,1,2,5,4}得到二叉排序树：由序列{1,2,3,4,5}得到二叉排序树：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.21234531254二叉排序树的删除

在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。删除的结点可以分三种情况：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树又有右子树。二叉排序树的删除

情况1：被删除的结点是叶子，只需要将其双亲结点相应的指针域置为空，并释放该结点。二叉排序树的删除

情况2：被删除的结点只有左子树，使用左孩子代替被删除的结点二叉排序树的删除

情况2：被删除的结点只有右子树，使用右孩子代替被删除的结点二叉排序树的删除

情况3：被删除的结点既有左子树又有右子树使用被删除结点的中序遍历的后继来代替被删除的结点。结点p的中序遍历的后继为p的右子树最左下的结点s，使用结点s代替结点p，如果结点s有右子树，记为sr，结点s的双亲记为ps，使sr成为ps的左子树。二叉排序树的删除

特殊情况：当p的右孩子不存在左子树时，结点p的右孩子为其右子树最左下的结点，即p的右孩子为p的中序遍历的后继，直接使用p的右孩子代替p。

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

温馨提示

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

最新文档

评论

0/150

提交评论