文档章节

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

idreamo
 idreamo
发布于 2017/08/26 08:21
字数 1833
阅读 54
收藏 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
粉丝 17
博文 139
码字总数 224743
作品 0
青岛
产品经理
私信 提问
转行程序员?你可能忽略了一件事。

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

java进阶架构师
10/25
0
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
算法之路

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

李序锴
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

在PC上测试移动端网站和模拟手机浏览器的5大方法

总结很全面,保存下来以备不时之需。原文地址:https://www.cnblogs.com/coolfeng/p/4708942.html

kitty1116
35分钟前
3
0
分布式Session共享解决方案

分布式Session一致性? 说白了就是服务器集群Session共享的问题 Session的作用? Session 是客户端与服务器通讯会话跟踪技术,服务器与客户端保持整个通讯的会话基本信息。 客户端在第一次访...

Java干货分享
41分钟前
5
0
开源软件和开源模式面临的生存危机

导读 开源模式可能正面临一场危机。越来越多的开源软件和平台被大型云计算服务商融入自家的云服务体系,并以此获利颇丰,但并不支付费用,也没有对开源社区做出相应的回馈。而实际上,大部分...

问题终结者
43分钟前
3
0
让看不见的AI算法,助你拿下看得见的广阔市场

人工智能技术的飞速发展给各行各业都带来了深远的影响,AI已被视为企业提升运营效能、应对市场竞争的必经之路。然而对于一些企业而言,让AI真正实现落地和应用,并且创造价值,仍是一件需要努...

个推
47分钟前
2
0
用SAN还是NAS?我来告诉你

存储区域网络(SAN)是以一种结构连接的存储,通常通过交换机连接,使许多不同的服务器能够轻松访问存储设备。从服务器应用程序和操作系统的角度来看,访问SAN中的数据存储或直接连接的存储之间...

linux-tao
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部