文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 电脑基础知识 > 二叉查找树
侵权投诉

二叉查找树

二叉查找树

(2)如果结点x的左子树为空,且x有一个前趋y,则y是x的最低祖先结点,且y的右儿子也是x的祖先。如上图中,关键字为9的结点的前驱是关键字为7的结点。也就是要从x开始,往上找某个结点y,它的右儿子是x的祖先。其实,在没有左子树的情况下,如果x是右儿子,则前趋就是x的父结点。

下面给出查找结点x的前驱结点y的函数:

function pred(x : integer) : integer; var y : integer; begin

if bst[x].left<>0

then y:=max(bst[x].left) else begin y:=bst[x].p;

while (bst[y].p<>0) and (x=bst[y].left) do begin x:=y; y:=bst[y].p; end; end; pred:=y; end;

三、二叉查找树的插入与删除

插入和删除操作会引起以二叉查找树表示的动态集合的变化。要反应出这种变化,就要修改数据结构,但在修改的同时,还要保持二叉查找树性质。

(一)二叉查找树的插入

把结点z插入到二叉查找树T中,使T仍然满足二叉查找树的性质。

例如,下图是把关键字为14的结点,插入到一棵已存在的二叉查找树中的情况。从插入后的结果中可以看出:只要从根结点开始,不断沿着树枝下降即可。用指针x跟踪这条路径,而y始终指向x的父结点。根据key[z]与key[x]的比较结果,可以决定向左或者向右。直到x成为NIL时为止。这个NIL所占位置即我们想插入z的地方。

在下面描述的插入过程中,先将插入结点z的相关信息存放在bst数组的位置i上,插入结点的关键字为t。

上一页第5页

你可能喜欢

热门文档

相关文档

  • 数据结构实验报告六—BST(二叉查找树)实现动态查找表

    数据结构实验报告六—BST(二叉查找树)实现动态查找表_工学_高等教育_教育专区。C++数据结构实验报告六—BST(二叉查找树)实现动态查找表BST...

  • 二叉查找树、平衡树和B-树

    在根指针T所指二叉排序树中 二叉排序树用二叉链表存储。 二叉排序树用二叉链表存储 在根指针T 递归地查找关键字等于key的记录,若查找成功, key的记录 递归地查找...

  • Java数据结构之二叉查找树

    Java数据结构之二叉查找树_计算机软件及应用_IT/计算机_专业资料。介绍二叉查找树类的具体实现和相关性质。Java数据结构之二叉查找树二叉查找树是二叉树在查找领域的一...

  • 二叉查找树

    1、二叉排序树的定义 、 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者 是空树,或者是满足如下性质的二叉...

  • 二叉查找树

    二叉查找树报告人:朱贡睿 报告时间:2010.11.07 报告地点:计算机楼401 上讲内容回顾——散列表 散列表 上讲内容回顾直接寻址表 散列表 散列函数乘法散列发 除法...

  • 二叉查找树、平衡树和B-树 2

    在二叉排序树上的操作 1)查找例:在如下二叉排序树中查找关键字为24的记录。 24?45 继续在左 子树中查找 12 3 24?37 继续在左 子树中查找 37 45 24?12 ...

  • 二叉查找树,算法,排序

    二叉查找树,算法,排序_IT/计算机_专业资料。讲解二叉查找树的算法二叉查找树维基百科,自由的百科全书 自由的百科全书(重定向自二叉排序树) 3 层二叉查找树 二叉查...

  • bst二叉查找树

    二叉查找树(BST) 一、需求分析 利用二叉查找树(BST)实现一个动态查找表。 (1) 使用二叉树(BST)来实现。 (2) 二叉树使用链式结构(二叉链表)实现。 (3) ...

  • 二叉查找树实现代码及运行结果

    二叉查找树实现代码及运行结果_IT/计算机_专业资料。以C语言实现的二叉查找树。实现了一下基本操作:构造空表、销毁表、搜索指定关键字的元素、插入新元素、删除指定...

  • 二叉搜索树

    二叉搜索树_IT/计算机_专业资料。C语言二叉搜索树二叉搜索树定义 ? 查找 ? 二叉搜索树创建 ? 插入 ? 删除 示例 ? 二叉搜索树性能分析 ? 课后练习P197 10.4 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email