目标
- 学习树数据结构的相关术语 。
- 了解树数据结构适用的各种应用程序 。
- 能够使用链接或者数组来实现树结构,并且熟悉基于树的基本算法 。
- 了解二叉搜索树结构以及它的各种操作的效率 。
- 通过更多的练习来提高对递归算法的理解 。
比如说,我们可以使用树来表示生物学家使用的生物类群里的动物 。动物可以细分为脊椎动物和无脊椎动物;脊椎动物可以细分为爬行动物、鱼类、哺乳动物等 。这个树看起来就会如图7.1所示 。层次关系在我们的生活中随处可见,因此,树在许多的应用程序里都被用来作为数据的自然表示 。
文章插图
图7.1 生物学家的生物类群的一部分
可能会让你惊讶的是,事实证明,在实现之前提到普通的序列数据的时候,树也非常有用 。在这一章里,我们将看到被称为二叉搜索树(binary search tree)的树结构 。它被用来实现一个允许高效插入和删除(类似于链表)的集合,但它同时也能够进行高效的搜索(类似于有序数组) 。基于树的数据结构和算法对于高效处理大量的数据(如数据库和文件系统)来说至关重要 。
7.2 树的术语计算机科学家们用一个包含节点的集合(类似于链表中的节点)以及用来连接它们的边(edge)来表示树 。图7.2所示为一个包含7个节点的树,其中每个节点都包含着一个整数 。图中最顶端的节点被称为根(root) 。在这个树里,根包含的数据值是2 。一个树只能有一个根 。因此,你可以跟随从根开始的边(箭头)到达树里面的任何一个其他节点 。
文章插图
图7.2 二叉树示例
树里的每个节点都可以通过边与它的子节点(child)相连接 。在一个普通的树里,一个节点可以有任意数量的子节点,但在这里,让我们先只关注二叉树(binary tree) 。在二叉树里,每个节点最多只能有两个子节点 。就像图7.2所示的那样,这里所描绘的树就是二叉树 。树里面的关系是用家庭和树相关的术语混合起来描述的 。根节点有两个子节点:包含7的节点是它的左子节点(left child);包含6的节点是它的右子节点(right child) 。这两个节点也被称为兄弟节点(sibling) 。同样地,包含8和4的两个节点也是兄弟节点 。那么节点5的父节点(parent)是节点7 。同样节点3是节点7的后代(descendant),节点7是节点3的祖先(ancestor) 。最后,没有任何子节点的节点则被叫作叶节点(leaf) 。节点的深度(depth)代表它与根节点之间的边数 。对于根节点来说,它的深度为零 。节点7和6的深度为1,节点3的深度则为3 。树的高度(height)或者说树的深度(depth)是所有节点里的最大深度 。
在满二叉树(full binary tree)中,每个深度级别的每一个可能的位置都有一个节点 。在最下面一层,所有的节点都是叶节点(也就是说,所有的叶节点都处于相同的深度,并且每个非叶节点都具有两个子节点) 。而完全二叉树是在最深层之外的每一个可能位置都有一个节点,并且在最深的那一层,节点按照从左到右的位置进行排列 。可以从满二叉树开始,然后在下一层从左到右添加节点,或者是从右到左删除最后一层的节点来创建完全二叉树 。它们两个的示例如图7.3所示 。
文章插图
图7.3 左侧是完全二叉树,右侧是满二叉树
树的每个节点及其后代都可以被视为一个子树(subtree) 。比如说,在图7.2里,节点7、5和3组合在一起可以被认为是整个树的一个子树,其中,节点7是这个子树的根节点 。通过这种方式来看的话,很明显地,树可以被当作递归结构 。一个二叉树可以是空树,也可以是根节点和(可能为空的)左右子树组合起来的树 。
和列表类似,树的一个非常有用的操作是遍历 。给定一个树,我们需要有一种合适的方式来系统地“走过”这个树的每一个节点 。但是和列表不同的是,并没有一个很清晰的遍历树的方法 。可以看到,树里的每一个节点都由3部分组成:数据、左子树和右子树 。因此,根据我们的侧重点来决定处理这些数据,我们可以有3种不同的遍历顺序来进行选择 。如果我们先在根节点处理数据,然后再去处理左右子树的话,我们将会执行被称为前序遍历(preorder traversal)的遍历方法 。这个遍历方法之所以叫这个名字,是因为我们首先需要考虑的是根节点里的数据 。前序遍历可以很容易地被表示成一个递归算法:
推荐阅读
- 在生意参谋中通过以下哪个模块可以查看竞品的流量结构 在生意参谋中通过以下哪个模块可以查看竞品的流量结构
- centos7目录结构 理解各个目录的功能
- 茶树菇怎么保存呢,茶树菇怎么炒好吃
- MAC如何实现屏幕缩放
- 懂过古树的口感特点,懂过古茶山
- 成年老茶的别样滋味,新品上市2015老同志深山老树茶生茶上市
- 茶树菇炒羊肉的做法,茶树菇炒里脊肉的做法
- 茶香胡乱炖的做法,茶树菇炖柴鸡的做法
- 倒茶也能端庄大雅,2012年中茶牌布朗大树开汤品鉴
- 茶树菇有哪些功效禁忌,百合菊花茶的功效和禁忌有多少