文档章节

第17章 高级数据表示 17.7 二叉搜索树(第一部分ADT 和 接口)

idreamo
 idreamo
发布于 2017/08/26 08:21
字数 1833
阅读 46
收藏 0
点赞 0
评论 0

第一部分ADT 和 接口

二叉搜索树是一种结合了折半搜索策略的链接结构。

树中的每一个节点都包含一个项目和两个指向其他节点的(称为子节点,child node)指针。这种构思是每个节点都有两个子节点,左节点 和 右节点

其顺序按如下规则确定:在左节点中的项目是父节点中项目的前序项,而在右节点中的项目是父节点中项目的后序项。这种关系存在于每一个有子节点的节点中。而且,所有能循其祖先回溯到左节点的项目都是该左节点的父节点项目的前序项,所有以右节点为祖先的项目都是该右节点的父节点项目的后序项。很有趣的是,与植物学相反,树的顶部是根。树是一个分层的组织,这意味着数据是以等级或者说层次来组织的一般地,每个等级都有其上或其下的等级。如果二叉搜索树是满的,那么每一层的节点数都二倍于其上层的节点数。

二叉搜索树中的每一个节点本身都是其后代节点的根,此节点与其后代节点构成一个子树(subtree)

假设您想在树中查找一个项目(仍称为子项目)。如果此项目在根节点项目的前面,只须查找树的左半部分,如果此项目在根节点项目的后面,只须查找右半部分。因而一次比较就排除了半个树。假设您查找左半边,那意味着将目标项与左子节点的项目进行比较。如果目标项在左子节点项目的前面,只须查找其后代的左半部分,依此类推。就像折半搜索一样,每次比较都排除一半可能的匹配性。

这样,二叉搜索树在链表结构中结合了折半搜索的效率。编程的代价是构造一颗树比创建一个链表更复杂。下面我们来创建一个二叉树,并最后建立一个ADT工程。

17.7.1  二叉树ADT

像前面那样,我们从定义二叉树的常规内容开始。该定义假设树中不包含相同的项目。很多操作与列表操作相同。不同之处在于数据的层次性安排。表17.4是有关此ADT的非正式总结。

二叉树类型总结

类型名称: 二叉搜索树
类型属性:

二叉树或者是一个空的节点集合(空树),或者是一个指定某一节点为根的节点集合

每个节点有两个作为其后代的树,称为左子树和右子树

每一个子树本身又是一个二叉树,也包含它是一个空树的可能性

二叉搜索树是一个有序的二叉树,它的每个节点包含一个项目,它的所有左子树的项目都排在根项目的前面,而根项目排在所有右子树项目的前面

类型操作

把树初始化为空树

确定树是否为空

确定树是否已满

确定树中项目的个数

向树中添加一个项目

从树中删除一个项目

在树中搜索一个项目

访问树中的每一个项目

清空树

17.7.2  二叉搜索树的接口

理论上讲,可以用多种方法实现二叉搜索树,甚至可以通过操作索引来用数组实现 。但实现二叉搜索树最直接的方法是用指针链接动态分配的节点。因此我们从如下的定义开始:

typedef SOMETHING Item;
typedef struct node
{
    Item item;
    struct node * left;
    struct node * right;
} Node;
typedef struct tree
{
    Node * root;
    int size;
} Tree;

每个节点包含一个项目,一个指向左子节点的指针和一个指向右子节点的指针。可以将Tree定义成指向Node的指针类型,因为只需要知道根节点的位置即可访问整个树。不过使用带有一个指示树大小的成员结构可以使跟踪树的大小更为简单。

我们要开发的示例程序是维护Nerfville宠物俱乐部的花名册。每一个项目由宠物的名字和各类组成。据此,我们可以建立 一个如程序清单17.10所示的接口。树的大小被限制为10个节点,以使我们更容易测试当树已满时程序是否正确运行。如果需要,您可以把MAXITEMS设置为更大的值。

/*tree.h--二叉搜索树*/
/*树中不允许有相同的项目*/
#ifdef _TREE_H_
#define _TREE_H
#include <stdbool.h>

/*您可以把Item重新定义为合适的类型*/
typedef struct item
{
    char getname[20];
    char getkind[20];
}Item;

#define MAXITEMS 10

typedef struct node
{
    Item item;
    struct node * left;  /*指向左分支的指针*/
    struct node * right; /*指向右分支的指针*/
}Node;

typedef struct tree
{
    Node * root;  /*指向树根的指针*/
    int size;     /*树中项目的个数*/
} Tree;

/*函数原型*/
/*操作:把一个树初始化为空树*/
/*操作前:ptree指向一个树*/
/*操作后:该树被初始化为空树*/
void InitializeTree(Tree * ptree);

/*操作:确定树是否为空*/
/*操作前:ptree指向一个树*/
/*操作后:如果树为空则函数返回true;否则返回false*/
bool TreeIsEmpty(const Tree * ptree);

/*操作:确定树是否已满*/
/*操作前:ptree指向一个树*/
/*操作后:如果树已满则函数返回true;否则返回false*/
bool TreeIsFull(const Tree * ptree);

/*操作:确定树中项目的个数*/
/*操作前:ptree指向一个树*/
/*操作后:函数返回树中项目的个数*/
int TreeItemCount(const Tree * ptree);

/*操作:向树中添加一个项目*/
/*操作前:pi是待添加项目的地址
          ptree指向一个已初始化的树*/
/*操作后:如果可能函数把该项目添加到树中并返回true;否则返回false*/
bool AddItem(const Item * pi,Tree * ptree);

/*操作:在树中查找一个项目*/
/*操作前:pi是指向一个项目
          ptree指向一个已初始化的树*/
/*操作后:如果该项目在树中,则返回true;否则返回false*/
bool InTree(const Item * pi,const Tree * ptree);

/*操作:从树中删除一个项目*/
/*操作前:pi是指向待删除项目的地址
          ptree指向一个已初始化的树*/
/*操作后:如果可能,函数从树中删除该项目并返回true;否则返回false*/
bool DeleteItem(const Item * pi,Tree * ptree);

/*操作:把一个函数作用于树中的每一个项目*/
/*操作前:pfun指向一个没有返回值的函数,该函数接受一个Item作为参数
          ptree指向一个已初始化的树*/
/*操作后:pfun指向的函数被作用于树中的每一个项目一次*/
void Traverse (const Tree * ptree,void (*pfun)(Item item));

/*操作:从树中删除所有节点*/
/*操作前:ptree指向一个已初始化的树*/
/*操作后:该树为空树*/
void DeleteAll(Tree * ptree);

#endif // _TREE_H_

下一节专门讲二叉树的实现

© 著作权归作者所有

共有 人打赏支持
idreamo
粉丝 12
博文 139
码字总数 224743
作品 0
青岛
产品经理
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
07/12
0
0
算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/18
0
0
《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构,在查找上比链表有优势,但是在插入与删除上比不上链表。 Java中的数组有长度限制,为int值。在内存模型中,...

刀狂剑痴
2016/05/27
155
0
数据结构-二叉搜索树的实现

定义 二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 相较于普通的二叉树,非空的二叉搜索树有如下性质: 非空左子树的所有键值小于其根结点的键值; 非空右子树的所有...

IAM四十二
2017/10/27
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
当我们在聊TreeMap(一)——红黑树详解Java代码实现

本文出自:https://blog.csdn.net/DT235201314/article/details/80661157 一丶概述 上一篇讲HashMap,避开了红黑树,这边讲TreeMap,好好说一下红黑树。 二丶概述目录图 三丶聊聊TreeMap 数据...

天一方蓝
06/13
0
0
无处不在的算法---《算法神探》读后感

最近,我参加了CSDN举办的“从高考到程序员”征文活动,获赠了一本图书。在众多图书中,我选了《算法神探》,觉得这本书从名字上来看就比较有意思。拿到书之后,我分两次就把它读完了,可以毫...

zhouzxi
2017/07/22
0
0
二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜
07/04
0
0
二叉树,排序二叉树

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相...

长平狐
2013/12/25
129
0
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

rabbitmq学习记录(三)

工作队列:一个生产者,多个消费者,生产者直接将消息发送到rabbitmq的队列之中 默认采用的是轮询分配:即不管消费者处理信息的效率,队列给所有消费者轮流发送一条信息,直至消息发送完毕 ...

人觉非常君
18分钟前
0
0
Java 之 反射

反射,剖析 Java类 中的 各个组成部分,映射成 一个个 Java对象,多用于 框架和组件,写出复用性高的通用程序。 测试类代码如下: class Person { private String name; public St...

绝世武神
22分钟前
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
27分钟前
0
0
多 SSH Key 实现同一台服务器部署多 Git 仓库

本文以以下需求为背景,介绍详细的做法: 需在同一台服务器同时部署两个不同的 Github 仓库(对 Bitbucket 等 git 服务同样适用) root 用户可在远程登录 SSH 后附上预期的 SSH Key 进行 gi...

yeahlife
30分钟前
0
0
003. es6数值的扩展

一、普通扩展 Number 方法,将字符串、数值转为十进制 : Number('0b111') Number.isFinite() 用来检查一个数值是否为有限的:Number.isFinite(15) Number.isNan() 用来检查一个值是否为NaN N...

秋季长青
44分钟前
0
0
C语言数组和指针的语法糖

对于C语言,我可以这样秀:比如当创建一个数组arr[n]之后,一般我们去遍历数组的时候是for (int i = 0; i < n; i++) { a[i]; }但是我知道下表访问符[]是个语法糖,也就是说a[i]在编译器看来是...

ustbgaofan
52分钟前
0
0
Call to undefined function bcmath()的解决方法

乐意黎的ECS主机环境,Centos7.2 + PHP7 由于使用了bcdiv()函数,运行时总在抛错。 Fatal error: Call to undefined function bcmath() in /usr/loca/apache/htdocs/... on line 4 一查得知:......

dragon_tech
58分钟前
0
0
css优先级

..

architect刘源源
今天
0
0
【转】Twitter的分布式自增ID算法snowflake

结构 snowflake的结构如下(每部分用-分开): 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 第一位为未使用,接下来的41位为毫秒级时间(41位的长度可以...

talen
今天
0
0
hive支持行级修改

Hive从0.14版本开始支持事务和行级更新,但缺省是不支持的,需要一些附加的配置。要想支持行级insert、update、delete,需要配置Hive支持事务。 一、Hive具有ACID语义事务的使用场景 1. 流式...

hblt-j
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部