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
