6.3.词汇和定义

我们已经看了树的示例,我们将正式定义树及其组件。

节点

节点是树的基本部分。它可以有一个名称,我们称之为“键”。节点也可以有附加信息。我们将这个附加信息称为“有效载荷”。虽然有效载荷信息不是许多树算法的核心,但在利用树的应用中通常是关键的。

边是树的另一个基本部分。边连接两个节点以显示它们之间存在关系。每个节点(除根之外)都恰好从另一个节点的传入连接。每个节点可以具有多个输出边。

树的根是树中唯一没有传入边的节点。在 Figure 2 中,/ 是树的根。

路径

路径是由边连接节点的有序列表。例如,Mammal→→Carnivora→→Felidae→→Felis→→Domestica是一条路径。

子节点

具有来自相同传入边的节点 c 的集合称为该节点的子节点。在 Figure 2中,节点 log/,spool/ 和 yp/ 是节点 var/ 的子节点。

父节点

具有和它相同传入边的所连接的节点称为父节点。在 Figure 2 中,节点 var/ 是节点 log/,spool/ 和 yp/ 的父节点。

兄弟

树中作为同一父节点的子节点的节点被称为兄弟节点。节点 etc/ 和 usr/ 是文件系统树中的兄弟节点。

子树

子树是由父节点和该父节点的所有后代组成的一组节点和边。

叶节点

叶节点是没有子节点的节点。 例如,人类和黑猩猩是 Figure 1 中的叶节点。

层数

节点 n 的层数为从根结点到该结点所经过的分支数目。 例如,图1中的Felis节点的级别为五。根据定义,根节点的层数为零。

高度

树的高度等于树中任何节点的最大层数。 Figure 2 中的树的高度是 2。

现在已经定义了基本词汇,我们可以继续对树的正式定义。 事实上,我们将提供一个树的两个定义。 一个定义涉及节点和边。 第二个定义,将被证明是非常有用的,是一个递归定义。

定义一:树由一组节点和一组连接节点的边组成。树具有以下属性:

  • 树的一个节点被指定为根节点。

  • 除了根节点之外,每个节点 n 通过一个其他节点 p 的边连接,其中 p 是 n 的父节点。

  • 从根路径遍历到每个节点路径唯一。

  • 如果树中的每个节点最多有两个子节点,我们说该树是一个二叉树。

定义二:树是空的,或者由一个根节点和零个或多个子树组成,每个子树也是一棵树。每个子树的根节点通过边连接到父树的根节点。 Figure 4 说明了树的这种递归定义。使用树的递归定义,我们知道 Figure 4 中的树至少有四个节点,因为表示一个子树的每个三角形必须有一个根节点。 它可能有比这更多的节点,但我们不知道,除非我们更深入树。

Last updated