501 树的基本术语及性质

树的基本术语及性质

基本术语

树（Tree）是计算机科学中一种重要的数据结构，用来表示具有层次关系的数据集合。它由有限个节点组成，形似一棵倒挂的树，根在上，叶在下。下面将以结构化的方式，使用标题和 Markdown 表格详细解释树的基本概念。

节点关系相关概念

概念	定义
祖先（Ancestor）	从树的根节点到某个节点所经过路径上的所有节点（不包括该节点本身）。例如，对于节点 H，其祖先可能是 A、B、D 等。
子孙（Descendant）	以某个节点为根的子树中的所有节点。例如，节点 B 的子孙可能包括 D、G、H、I 等。
双亲（Parent）	某个节点的直接上层节点，即直接连接它的父节点。例如，节点 B 是节点 D 的双亲。
孩子（Child）	某个节点的直接下层节点，即直接连接它的子节点。例如，节点 D 是节点 B 的孩子。
兄弟（Sibling）	具有相同双亲节点的节点互称为兄弟节点。例如，节点 E 和 F 如果有共同的双亲 B，则它们是兄弟节点。
堂兄弟（Cousin）	双亲节点在同一层次的节点互称为堂兄弟节点。例如，节点 D、E、F 如果它们的双亲都在同一层，则它们互为堂兄弟。

层次与深度相关概念

概念	定义
节点的层次（Level）	节点的层次从根节点开始定义，根节点为第 1 层，其孩子节点为第 2 层，依此类推。每个节点的层次等于其双亲节点的层次加 1。
树的深度（Depth）或高度（Height）	树中节点的最大层次值。例如，如果树的最大层次为 4，则树的深度为 4（部分定义中深度可能指分支数，会比层次少 1）。

度相关概念

概念	定义
节点的度（Degree of a Node）	一个节点拥有的子节点（或子树）的数量。例如，节点 A 有 3 个孩子，则其度为 3。
树的度（Degree of a Tree）	树中所有节点的度的最大值。例如，如果树中某个节点的度为 3，且这是最大值，则树的度为 3。
分支节点（Branch Node）	度不为 0 的节点，也称为非终端节点或内部节点（除根节点外）。它们有至少一个孩子节点。
叶节点（Leaf Node）	度为 0 的节点，也称为终端节点。它们没有孩子节点。

树的分类相关概念

概念	定义
有序树（Ordered Tree）	树中每个节点的子树从左到右有固定次序，不能互换。通常讨论的树默认是有序树，例如二叉树。
无序树（Unordered Tree）	树中每个节点的子树没有固定次序，可以互换，也叫自由树。

路径相关概念

概念	定义
路径（Path）	从树中一个节点到另一个节点所经过的分支构成的路线。树中任意两节点之间有且仅有一条路径。
路径长度（Path Length）	路径上的分支数目。例如，从根节点到某个节点经过 3 条边，则路径长度为 3。
树的路径长度	从根节点到每个节点的路径长度之和，反映了树中所有节点的访问成本。

一般树主要性质

1. 结点数与边数

   • 结论：含有 $N$ 个结点的树有 $N-1$ 条边。
   • 推导：树被定义为连通且无环的图。根结点有0条边，每增加一个结点（非根），需恰好增加一条边以保持连通性且不形成环。

2. 结点数与总出度

   • 结论：一棵含有 $N$ 个结点的树，其所有结点的总出度等于边数，即 $N-1$。
   • 推导：在树结构中，除根结点外，每个结点恰好有一条入边。这些入边均由其父结点发出。因此，所有结点的入度之和（等于总边数）等于所有结点的出度之和。

3. 每层最多结点数

   • 结论：若根结点为第 1 层，则第 $k$ 层最多有 $m^{k-1}$ 个结点。
   • 推导：第 1 层（根）有 $1=m^0$ 个结点。每个结点最多有 $m$ 个孩子，故第 $k$ 层最多有 $m\times m^{k-2}=m^{k-1}$ 个结点。

4. 最大结点数

   • 结论：高度为 $h$ 的 $m$ 叉树（根结点为第 1 层，树有 $h$ 层）最多有 $\frac{m^h-1}{m-1}$ 个结点（当 $m>1$；若 $m=1$ 则为 $h$ 个）。
   • 推导：最大结点数是各层最多结点数之和：${\sum }_{k=1}^h{m}^{k-1}$。这是一个等比数列求和，结果为 $\frac{m^h-1}{m-1}$。

5. 最小高度

   • 结论：具有 $N$ 个结点的 $m$ 叉树的最小高度 $h_{min}$ 为 $\lceil {\log }_m(N(m-1)+1)\rceil$（当 $m>1$；若 $m=1$ 则为 $N$）。
   • 推导：最小高度发生在树尽可能平衡时，即 $N\le \frac{m^{h_{min}}-1}{m-1}$。解此不等式得 $h_{min}\ge {\log }_m(N(m-1)+1)$。由于高度必须是整数，取其上限。

6. 最后非叶子结点的位置

   • 结论：在含有 $N$ 个结点的完全 m 叉树中 (按层次从左到右，1-indexed 存储于数组)，最后一个非叶子结点的结点索引为 $\lfloor (N-2)/m\rfloor +1$。
   • 推导：结点 $i$ 是有分支结点，当且仅当其至少有一个孩子。对于 1-indexed 存储，结点 $i$ 的第一个孩子索引为 $m(i-1)+2$。若 $m(i-1)+2\le N$，则 $i$ 有孩子。最大满足此条件的 $i$ 即为所求。

7. 叶子结点数

   • 结论：对于一棵一般树，设 $n_k$ 为度为 $k$ 的结点数，则叶子结点数 $n_0=1+{\sum }_{k=2}^m(k-1)n_k$。
   • 推导：总结点数 $N={\sum }_{k=0}^m{n}_k$。总出度（即边数）$E={\sum }_{k=0}^{m}k\cdot n_k$。根据性质1， $E=N-1$。将 $N$ 代入 $E=N-1$ 并整理可得出此关系。

叶子结点数公式推导（基于出度定义）

对于任意有根树，设 $n_i$ 表示出度为 $i$ 的节点数量，$n$ 表示总节点数，则有：

1. 总节点数：

   $$n=n_0+n_1+n_2+\cdots +n_m$$

   其中 $n_0$ 是出度为 $0$ 的节点数量，即叶节点数量；$m$ 是树中节点的最大出度。

2. 出度总和与边数关系： 在一个有 $n$ 个节点的树中，总共有 $n-1$ 条边。每条边都从一个父节点指向一个子节点。因此，所有节点的出度之和，恰好等于树中的总边数。

   $$\sum _{i=0}^{m}i\cdot n_i=n-1$$

   推导：每个节点 $v$ 的出度 $out(v)$ 代表它有多少个孩子节点。树中的每一条边 $e=(u,v)$ 都表示 $u$ 是 $v$ 的父节点，且 $v$ 是 $u$ 的孩子节点。因此，对所有节点 $v$ 的出度求和，其结果就是树中边的总数。

3. 叶节点数公式推导：

   我们有以下两个基本等式：

   • 总节点数：$n=n_0+n_1+n_2+\cdots +n_m$
   • 出度总和：$n_1+2n_2+3n_3+\cdots +m{n}_m=n-1$

   将第一个等式中的 $n$ 代入第二个等式：

   $$n_1+2n_2+3n_3+\cdots +m{n}_m=(n_0+n_1+n_2+\cdots +n_m)-1$$

   将等式两边的 $n_1$ 抵消：

   $$2n_2+3n_3+\cdots +m{n}_m=n_0+n_2+n_3+\cdots +n_m-1$$

   将右侧的 $n_2,n_3,\dots ,n_m$ 项移到左侧：

   $$(2n_2-n_2)+(3n_3-n_3)+\cdots +(m{n}_m-n_m)=n_0-1$$

   整理后得到：

   $$n_2+2n_3+\cdots +(m-1)n_m=n_0-1$$

   用求和符号表示为：

   $$\sum _{i=2}^m(i-1)\cdot n_i=n_0-1$$

   最终得出叶节点数公式：

   $$n_0=1+\sum _{i=2}^m(i-1)\cdot n_i$$