树的概念与存储

树是图的一类特殊形式。它既是无向图，又具有更加严格的结构约束：连通且不含环。由于这一特性，树常常被用来刻画分层、分支状的关系。

树的定义

形式化地，树是一个无向连通无环的简单图，具有以下等价刻画：

1. 含有 $n$ 个顶点且恰好有 $n-1$ 条边；
2. 任意两个顶点之间存在且仅存在一条简单路径；
3. 是极小的连通图，去掉任意一条边就会失去连通性。

这些性质互相等价，通常可以作为树的判别条件。它们共同表明，树是最“精简”的连通结构。

树的基本概念

在一棵树中，任意选择一个顶点作为根，就得到了一棵有根树。在有根树中，顶点之间形成天然的层次结构：

• 与根相连的顶点称为它的子节点；
• 与某个节点直接相连并在根方向上的顶点称为它的父节点；
• 没有子节点的顶点称为叶子节点。

这种层次结构使得树能够自然地表示许多层级关系，如组织架构、文件目录等。

树的存储方式

树作为图的特例，也可以用邻接矩阵和邻接表来存储。但由于其结构特殊，往往有更为简化的表示方法。

邻接表表示

树的稀疏性（边数 $=n-1$）使得邻接表成为更自然的存储方式。每个节点只需要记录实际存在的邻居，空间复杂度为 $O(n)$。

一般情况下都是选择邻接表作为树的表示方式，从而可以统一的处理图和树。

父节点数组

对于有根树，可以直接用一个数组 parent[] 存储每个节点的父节点编号。根节点的父节点记为 $-1$ 或空值。这种方式空间效率高，且能快速得到任意节点的父节点。