第17章 高级数据表示 17.7 二叉搜索树(第一部分ADT 和 接口)
博客专区 > idreamo 的博客 > 博客详情
第17章 高级数据表示 17.7 二叉搜索树(第一部分ADT 和 接口)
idreamo 发表于8个月前
第17章 高级数据表示 17.7 二叉搜索树(第一部分ADT 和 接口)
  • 发表于 8个月前
  • 阅读 38
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

第一部分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_

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

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 12
博文 139
码字总数 224743
×
idreamo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: