Question

6.3.词汇和定义

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

节点

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

边

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

根

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

路径

路径是由边连接节点的有序列表。例如， $Mammal \to Carnivora \to Felidae \to Felis \to Domestica$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 3 展示了适合定义一的树。边上的箭头指示连接的方向。

Figure 3

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

Figure 4