树基础

树定义

考虑一个有 $n$ 个节点，$n-1$ 条边的无向连通图，任取两个节点有且仅有一条简单路径，考虑这种图为无根树。

在此基础上，指定某一个节点为根节点，节点之间出现了层级关系，称之为有根树

之后的讨论都基于有根树，简称有根树为树

---

树概念

对于树上的某个非根节点 $N$，定义其（唯一的）直接前驱为父节点，将 $N$ 与父节点断开后，剩余的以 $N$ 为根节点的树称为 $N$ 的子树；

如果一个节点的父节点是 $N$，那么该节点为 $N$ 的子节点；一个父节点可以有多个子节点，这些并列关系的子节点互相为兄弟节点；

某个节点的子节点个数称为该节点的度，所有节点的度的最大值称为树的度；

度为 0 的节点称为叶节点，度不为 0 的节点称为分支节点

定义混乱的一些定义

节点的高度定义为：叶节点的高度为 1；一个节点的父节点高度为该节点高度加 1；树的高度为根节点的高度

节点的深度定义为：根节点的深度为 1；一个节点的子节点深度为该节点深度加 1；树的高度为所有节点的深度的最大值

规定节点的层次和节点的深度等价；规定根节点的深度与层次均为 1

如果一棵树需要关心各个节点子树的顺序，那么这类数为有序树，否则为无序树

典型的有序树例子为二叉树，其严格要求左右子树的顺序

---

树抽象

一个存储信息较为完整的树可以构造出这些常用的函数

// pos 记录节点地址，可以是数组下标 / 链表指针等
pos BuildRoot(const T& value);          // 建立根节点，返回根节点地址
pos FirstChild(pos p);                  // 返回节点 p 的第一个子节点地址
pos NextSibling(pos p);                 // 返回节点 p 的下一个兄弟节点地址
pos Parent(pos p);                      // 返回节点 p 的父节点地址
T GetData(pos p);                       // 取出节点 p 的存放地址
bool InsertChild(pos p, T& value);      // 在节点 p 处插入新子节点
bool DeleteChild (pos p, int i);        // 删除节点 p 的第 i 个子节点（递归删除子树）
bool DeleteSubTree (position t);        // 删除以节点 p 为根节点的子树
bool IsEmpty ();                        // 判断树是否非空
void Traversal (void (*visit)(pos p));  // 采用某种遍历方式遍历以节点 p 为根节点的子树
                                        // visit 是一个指向函数的指针，指向具体的遍历方式

---

树存储

存储父节点

因为任意节点的父节点唯一，所以用一维数组即可储存，只适用于自底向上的遍历

// 下标表示节点的标签，存储的值为父节点标签
vector<int> parent(n);

在涉及树的自底向上递推 / DP 等操作，以及并查集构造中，这一存储方式简单实用

存储子节点

因为任意节点的子节点不唯一，所以用二维邻接表储存，只适用于自顶向下的遍历

// 下标表示节点的标签，存储的子向量为所有子节点标签
vector<vector<int>> adj(n);

通常来说，将二维数组 adj 和一维数组 parent 结合使用，就可以较好地存储一张有向树

“左孩子右兄弟”

我们发现邻接表的存储方案用到了开销大的二维数组，并且如果需要访问一个节点的兄弟节点，需要先访问父节点，再访问父节点对应的邻接表

这里有一种内存开销更小的方案：

vector<int> sib(n);     // 记录下一个兄弟节点
vector<int> child(n);   // 记录第一个子节点

如果需要自底向上遍历可以直接加上 parent 数组

不难发现通过这种存储方式，我们将任意的多叉树转化为了二叉树的存储（任何节点都只有 “下一个兄弟节点” 和 “第一个子节点” 两个分叉），因此可以直接对任意多叉树使用二叉树算法，并且将各种树形结构统一化存储

容易得到多叉树和这种存储方式得到的二叉树之间存在双向的转换

2025-10-262025-11-21