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

二叉查找树

一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了key域和卫星数据域外,还包含域left,right和p,它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在,则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。

一般情况下,一棵二叉查找树的存储结构如下:

type node = record

key : longint; {关键值} left, right, p : longint; {左儿子、右儿子、父结点} {根据需要增加一些数据域} end;

var bst : array[1..maxn] of node;

(三)二叉查找树的遍历

根据二叉查找树的性质,若要求按递增顺序输出树的所有关键字,只需要采用中序遍历算法递归即可:

procedure inorder_print(root : integer); {递归中序输出,从小到大} begin

if bst[root].left<>0 then inorder_print(bst[root].left); write(bst[root].key, ' ');

if bst[root].right<>0 then inorder_print(bst[root].right); end;

也可以用广义表的形式输出:

procedure out(root : integer); begin write('(');

if bst[root].left<>0 then out(bst[root].left); write(bst[root].key);

if bst[root].right<>0 then out(bst[root].right); write(')'); end;

二叉查找树看似简单,且没有太多的规则,其实它在题目中变化无常,所以要真正要用好它,是需要下一番功夫的。首先要熟练掌握好它的各种基本操作,下面一一给出。

二、查询二叉查找树

对于二叉查找树,最常见的操作是查找树中的某个关键字。除了search操作外,二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作,并说明对于高度为h的树,它们都可以在O(h)时间内完成。

上一页第2页

你可能喜欢

热门文档

相关文档

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