文档章节

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

idreamo
 idreamo
发布于 2017/08/26 08:21
字数 1833
阅读 63
收藏 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
粉丝 18
博文 139
码字总数 224743
作品 0
青岛
产品经理
私信 提问
自己动手实现java数据结构(六)二叉搜索树

1.二叉搜索树介绍   前面我们已经介绍过了向量和链表。有序向量可以以二分查找的方式高效的查找特定元素,而缺点是插入删除的效率较低(需要整体移动内部元素);链表的优点在于插入,删除元...

小熊餐馆
01/24
0
0
数据结构与算法(4)——优先队列和堆

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

我没有三颗心脏
2018/07/12
0
0
转行程序员?你可能忽略了一件事。

     程序 = 数据结构 + 算法   ——图灵奖得主,计算机科学家N.Wirth(沃斯)      作为程序员,我们做机器学习也好,做python开发也好,java开发也好。   有一种对所有程序员无一...

java进阶架构师
2018/10/25
0
0
算法知识梳理(10) - 二叉查找树

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

泽毛
2017/12/18
0
0
自己动手实现java数据结构(八) 优先级队列

1.优先级队列介绍 1.1 优先级队列   有时在调度任务时,我们会想要先处理优先级更高的任务。例如,对于同一个柜台,在决定队列中下一个服务的用户时,总是倾向于优先服务VIP用户,而让普通...

小熊餐馆
02/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Phpstorm2018 永久激活

1、安装phpstorm,安装包请自行官网下载 http://www.jetbrains.com/phpstorm/download/ 2、下载JetbrainsCrack.jar文件,存放至你的phpstorm执行文件同级目录下 下载JetbrainsCrack.jar 提取...

happyfish319
14分钟前
3
0
谈一谈Android进程间通信的几种方式

###来看一下Android中除了AIDL还有哪些进程间通信的方式: 1、Bundle Bundle实现了Parcelable,所以在Android中我们可以通过Intent在不同进程间传递Bundle数据。 但是在Intent 传输数据的过程...

二营长的意大利炮手
15分钟前
6
0
互联网薪资“高开低走”,你的能力是否真的可以匹配高薪?

对于国内外主流互联网大厂,技术出身似乎已经成为各大掌门人的必备标签。谷歌 CEO 桑达尔·皮查伊、马克·扎克伯格、李彦宏、马化腾、雷军等等皆为技术人出身,都曾参与了公司内部重要产品的...

Java技术剑
17分钟前
6
0
java 多线程

线程声明周期 线程的五个状态:新建,就绪,运行,阻塞,死亡。 其中就绪和运行两个状态客户互相转换,但运行到阻塞,阻塞到就绪,只能单向转换。 刚new出的线程就是【新建】状态,调用start...

雷开你的门
18分钟前
5
0
构造器Constructor是否可被overrid

构造器不能被重写,不能用static修饰构造器,只能用public private protected这三个权限修饰符,且不能有返回语句。

无名氏的程序员
22分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部