树的定义与存储

树的定义与存储

树的定义与相关概念；树的表示与存储。

概念

树是有 $n$（$n\ge0$）个结点的有限集：空树；或有一个根结点，其余结点分成若干互不相交的子树。相关概念包括：结点的度（子树个数）、树的度（各结点度的最大值）、层次、高度（根高度常为 1）、叶子（度为 0 的结点）、双亲与孩子。树不限制每个结点最多几个孩子——三叉、四叉都仍是树。存储方式常见：双亲表示法（数组存 parent 下标）、孩子表示法（每个结点挂链表存孩子）、孩子兄弟表示法（左孩子右兄弟，可转为二叉树）。与 cspj.ds.binary-tree 的区别：二叉树每个结点最多两个孩子且分左右；与 cspj.ds.special-tree 的区别：特殊树是完全二叉树、哈夫曼树、BST 等加了额外约束的二叉树或其变种，不在本叶展开。

CSP-J 常考

目前语料只有 1 道：

• cspj-r1-2023 第 5 题：根高度为 1，问拥有 2023 个结点的三叉树高度至少为多少（考查一般树的高度下界，不是二叉树遍历）。

// 双亲表示法：tree[i] 存结点 i 的父结点下标，根为 -1
const int N = 100;
int parent[N];

int height(int u) {          // 从 u 向上数到根
    int h = 1;
    while (parent[u] != -1) {
        u = parent[u];
        ++h;
    }
    return h;
}

易错点

• 树的高度计数：CSP-J 题面常约定根高度为 1，与部分教材「根高度为 0」不同，读题先看约定。
• 一般树求最小高度：$m$ 叉树 $n$ 个结点时，高度至少 $\lceil \log_m n \rceil$ 一类估算要分清几叉。
• 不要把「孩子兄弟表示法」当成「树只有两个孩子」——右指针只是兄弟链，不是第二个孩子限制。
• 图的连通性与树混淆：$n$ 个顶点的树恰有 $n-1$ 条边，但那是 cspj.ds.graph 的考点。