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

二叉查找树

下面给出从树的某个结点出发,查找其子树中最大关键字值的结点位置的函数:

function max(x : integer) : integer; begin

while bst[x].right<>0 do x:=bst[x].right; max:=x; end;

(三)求一棵二叉查找树中结点x的后继(前趋)结点。

给定一个二叉查找树中的结点,有时候要求找出在中序遍历顺序下它的后继(前驱)。如果所有的关键字都不相同,则某一个结点x的后继结点即具有大于key[x]中的关键字中最小者的那个结点。根据二叉查找树的结构,不用对关键字做任何比较,就可以找到某个结点的后继。

查找结点x的后继时需要考虑两种情况:

(1)如果结点x的右子树非空,则x的后继即右子树中的最左(小)结点,如下图中关键字是6的结点的后继结点是关键字为7的结点,关键字是15的结点的后继结点是关键字为17的结点。

(2)如果结点x的右子树为空,且x有一个后继y,则y是x的最低祖先结点,且y的左儿子也是x的祖先。如下图中,关键字为13的结点的后继是关键字为15的结点。为找到y,可以从x开始往上查找,直到遇到某个结点是其父结点的左儿子结点时为止(或者某个节点的值恰好比x大为止,求前趋亦同)。

下面给出查找结点x的后继结点y的函数:

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

if bst[x].right<>0

then y:=min(bst[x].right) else begin y:=bst[x].p;

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

相应地,查找结点x的前驱与后继是对称的,也需要考虑两种情况:

(1)如果结点x的左子树非空,则x的前趋即左子树中的最右(大)结点,如上图中关键字是15的结点的前驱结点是关键字为13的结点。

上一页第4页

你可能喜欢

热门文档

相关文档

  • 数据结构实验报告六—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