第十一章 树与图基础

第十章的网格中，一个格子可以向哪些位置移动，由行列坐标和方向决定。如果把格子换成城市、网页或家庭成员，就不能再用固定的坐标增量寻找邻居。此时需要先记录“谁与谁相连”，再执行搜索。

本章用一张五点道路图依次学习存储、DFS、BFS 和连通块。随后把图中的环去掉、把各部分连起来，观察树为什么会有唯一的路径。选根、子树、二叉遍历和建树，都从这些具体关系继续推出。后面的搜索树与哈夫曼树则增加了各自的大小或合并规则。

阅读前需要掌握第七章的递归，以及第九章的栈、队列和堆。第十章解释过搜索中的标记，本章会再次明确：寻找可达点时，标记表示“已经发现”，返回旧顶点时不撤销。以下 C++17 程序彼此独立，均使用标准输入输出；自设小任务在代码前说明格式和范围。

1. 从道路关系到图的存储

有五个地点，双向道路为 $(1,2)$、$(1,3)$、$(2,4)$、$(3,4)$，地点 $5$ 没有道路。从 $1$ 能直接到 $2$，到 $4$ 则需要经过别的地点，从 $1$ 无法到 $5$。

地点叫作顶点，直接连接两个地点的道路叫作边。沿若干条边连续行走得到一条路径。两个点相邻，只说明它们之间有一条边；两个点可达，则允许经过中间顶点。顶点编号只是名字，不表示它离起点的远近。

双向道路对应无向图。一条边可以往两个方向走，但仍是一条道路。如果只允许从 $u$ 到 $v$，就用有向边 $u\to v$；网页引用常属于这种情况，被引用的网页不一定也引用回来。

1.1 先把道路画出来，再保存进数组

如果要查询“$u$ 到 $v$ 有没有直接道路”，可以准备一个表格：第 $u$ 行、第 $v$ 列写 $1$ 表示有边，写 $0$ 表示无边。这张表叫作邻接矩阵。

图中边 $(1,2)$ 在矩阵的 $(1,2)$、$(2,1)$ 两处都有标记。它也分别出现在顶点 $1$ 和顶点 $2$ 的邻居列表中。图没有变成两条道路；这两份记录只是为了从任一端都能找到另一端。

读入的道路	矩阵中改为 1 的位置	邻居列表的变化
$(1,2)$	$(1,2)$、$(2,1)$	给 $g[1]$ 加入 2，给 $g[2]$ 加入 1
$(1,3)$	$(1,3)$、$(3,1)$	给 $g[1]$ 加入 3，给 $g[3]$ 加入 1
$(2,4)$	$(2,4)$、$(4,2)$	给 $g[2]$ 加入 4，给 $g[4]$ 加入 2
$(3,4)$	$(3,4)$、$(4,3)$	给 $g[3]$ 加入 4，给 $g[4]$ 加入 3

只存每个顶点实际邻居的办法叫作邻接表。本例的完整列表为 $g[1]=[2,3]$、$g[2]=[1,4]$、$g[3]=[1,4]$、$g[4]=[2,3]$，$g[5]$ 为空。数组 g[u] 的下标是顶点编号；列表内部的下标表示第几个邻居，通常从 $0$ 开始。两种下标不能混淆。

1.2 查询什么，决定保存什么

矩阵查一条边只用 $O(1)$ 时间，但要找 $u$ 的所有邻居，仍需扫描一整行的 $n$ 个格子。空间为 $O(n^2)$；$n=10^5$ 时有 $10^{10}$ 个格子，通常无法直接保存。

邻接表只枚举真实存在的邻居。无向图的 $m$ 条边留下 $2m$ 份记录，加上 $n$ 份列表，空间为 $O(n+m)$。后面采用 vector<int> g[N]：顶点数有上界，每个顶点的邻居数量则随输入变化。若只查两点有没有边，未排序的邻接表需要逐个找，不能把它当成矩阵一样的常数时间查询。

有向边只加入 g[u]，无向边还要加入 g[v]。布尔矩阵会把同一对点之间的多条边合成一个“存在”；邻接表可能保留重复邻居。是否需要保留重边、边权，应由任务决定。用数值矩阵保存权值时，还要区分没有边和权值为 $0$ 的边。

2. 同一张图上的 DFS 与 BFS

现在求从 $1$ 能到达的所有顶点，每个顶点只输出一次。如果有多个邻居可尝试，总是按编号从小到大检查。为满足这个要求，先把每份邻接表排序；读入顺序本身不保证邻居已经有序。

2.1 DFS 怎样进入、返回和继续

DFS 先沿当前分支向深处走，当前顶点的邻居都检查完，才返回前一个顶点。对于道路图，从 $1$ 先到 $2$，再到 $4$，最后从 $4$ 到 $3$。首次到达顺序为 $1,2,4,3$。

下表中，路径栈左端是起点，右端是当前顶点。“已发现”是整个搜索共享的集合；从 $3$ 返回 $4$ 时，不会把 $3$ 从集合中删掉。

当前动作	路径栈	已发现的点	为什么这样做
进入 1	1	1	起点首次发现
1 检查邻居 2，进入 2	1,2	1,2	2 未发现
2 检查 1，再进入 4	1,2,4	1,2,4	1 已发现，跳过；4 未发现
4 检查 2，再进入 3	1,2,4,3	1,2,3,4	2 已发现，跳过；3 未发现
3 检查 1、4，返回 4	1,2,4	1,2,3,4	两个邻居都已发现
4 返回 2，2 返回 1	1	1,2,3,4	各自已没有未检查的邻居
1 检查 3，结束	空	1,2,3,4	3 虽不是由 1 首次发现，仍应跳过

蓝色是当前顶点，绿色表示已发现，灰色表示尚未发现；右侧的栈保留还没有处理完的顶点。返回时丢掉的是当前工作现场，永久标记继续保留。动画的完整动作也列在上表，静态过程见下图。

寻找可达点时，只要一个顶点已经展开，它能继续到达的邻居也会被检查，再从别的道路到达它不会产生新的顶点。这与第十章枚举每一条迷宫路径不同：路径枚举中的“当前路线已用过哪些格子”会影响后续选择，因而要恢复路径标记。

2.2 从递归现场推出带游标的栈

递归调用会自动记住“返回后执行哪一步”。上例在 $1$ 进入 $2$ 后，必须记住 $g[1]$ 的第一个邻居已经尝试过，回来应接着检查第二个邻居 $3$。

如果图是一条很长的链，递归深度可以达到 $n$。下面用数组 st 保存当前路径，用 cur[u] 保存顶点 $u$ 下一条待检查的邻边下标。读取 g[u][cur[u]++] 后，游标已经指向下一条；即使随后深入新顶点，回来也能接着做。游标等于列表长度时，说明当前顶点的工作结束，可以弹栈。

只把全部邻居倒序压栈并立即标记，并不总能得到同样的 DFS 顺序。用一个短反例检查：无向边为 $(1,2)$、$(1,3)$、$(2,3)$、$(2,4)$，递归顺序是 $1,2,3,4$。若展开 $1$ 时就把 $3,2$ 都压栈并标记，展开 $2$ 时会跳过已标记的 $3$，先压入并处理 $4$，出栈输出顺序变成 $1,2,4,3$。可达集合仍相同，但访问顺序不同。需要精确复现递归访问顺序时，保存“处理到哪条邻边”这一信息。

2.3 BFS 的队列保存已经发现、尚未展开的点

BFS 先处理起点的直接邻居，再处理更远的点。它不沿一条分支走到底，而是把发现的新顶点放到队尾，等待排在前面的顶点先展开。

出队并输出的点	新发现并加入的点	完成这一轮后的队列
开始前	1	1
1	2,3	2,3
2	4	3,4
3	无	4
4	无	空

队列左端是下一次出队的位置。处理 $2$ 时发现 $4$，立刻标记；因此稍后处理 $3$，即使也看到邻居 $4$，也不会再次入队。绿色包括已经出队的点和还在队列里的点，“发现”不等于“已经展开”。静态过程保留每一轮的队列。

两种搜索都只能到达 $1,2,3,4$，都不会自动访问孤立点 $5$。DFS 顺序为 $1,2,4,3$，BFS 顺序为 $1,2,3,4$。在每条边代价相等时，BFS 首次发现的层次还能给出最少边数；本节只输出访问顺序。

2.4 把两种过程对应到代码

独立任务：第一行输入 $n,m,t$，其中 $1\le n\le2\times10^5$、$0\le m\le2\times10^5$。$t=0$ 表示无向图，$t=1$ 表示有向图；随后 $m$ 行给出边的两个端点。顶点编号为 $1$ 到 $n$。从 $1$ 出发，第一行输出 DFS，第二行输出 BFS，邻居均按编号升序尝试。允许重边与自环，仍然只输出每个顶点一次。

道路例的第一行为 5 4 0，后面依次给出本章四条道路。程序输出两行 1 2 4 3 与 1 2 3 4。DFS 在首次压栈时输出，BFS 在出队时输出；入队顺序与出队顺序相同。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, m, t, st[N], cur[N], top;
bool vis[N];
vector<int> g[N];
int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        if (t == 0)
        {
            g[v].push_back(u);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(g[i].begin(), g[i].end());
    }
    st[++top] = 1;
    vis[1] = true;
    printf("1");
    while (top)
    {
        int u = st[top];
        if (cur[u] == (int)g[u].size())
        {
            --top;
            continue;
        }
        int v = g[u][cur[u]++];
        if (!vis[v])
        {
            vis[v] = true;
            printf(" %d", v);
            st[++top] = v;
        }
    }
    printf("\n");
    // 两次遍历各自记录首次发现，BFS 不能沿用 DFS 的标记。
    fill(vis + 1, vis + n + 1, false);
    queue<int> q;
    q.push(1);
    vis[1] = true;
    bool first = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (!first)
        {
            printf(" ");
        }
        printf("%d", u);
        first = false;
        for (int v : g[u])
        {
            if (!vis[v])
            {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    printf("\n");
    return 0;
}

每个顶点最多进入栈或队列一次，每份邻接记录最多检查一次。排序后的每次遍历时间为 $O(n+m)$；图的空间为 $O(n+m)$，栈、游标、标记和队列另需 $O(n)$。排序是额外工作，若各顶点邻居数为 $d_u$，所需时间为 $O(\sum_u d_u\log(d_u+1))$，不能算进常数时间读入。

查找文献 使用有向引用关系，从文献 $1$ 输出 DFS 和 BFS。该题只给 $n,m$，没有上述教学任务的 t，并且边数可达 $10^6$；应用时应按它的输入格式只存给定方向。原题要求优先访问编号较小的邻居，与这里排序的目的相同。

3. 从一次搜索扩展到全部连通块

在无向图中，一组彼此可沿路径到达、并且不能再加入其他顶点的集合叫作连通块。从一个顶点搜索，得到的恰好是它所在的连通块。

本章道路图第一次从 $1$ 搜索，标记 $1,2,3,4$。继续按编号扫描：$2,3,4$ 已发现，跳过；扫描到 $5$ 时，它仍未发现，于是再启动一次 BFS。虽然 $g[5]$ 为空，$5$ 本身仍然算一个点。这就得到大小为 $4$ 和 $1$ 的两个块。

这里的标记必须在所有 BFS 之间共享。如果每次启动都清空标记，扫描到 $2$ 时就会再数一次相同的连通块。与上一节 DFS 做完再单独做 BFS 时的清空不同：上一节是两次独立任务，本节是一次全图统计。

作为块大小统计的另一个例子，七点图的边为 $(1,2)$、$(2,3)$、$(4,5)$、$(6,7)$。从 $1$、$4$、$6$ 各启动一次，依次得到 $3,2,2$，排序后为 $2,2,3$。

独立任务：输入 $n,m$ 及 $m$ 条无向边，范围与上一节相同；输出连通块数量，再输出升序排列的各块大小。允许孤立点、重边与自环。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, m, cnt, a[N];
bool vis[N];
vector<int> g[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int s = 1; s <= n; ++s)
    {
        if (vis[s])
        {
            continue;
        }
        ++cnt;
        queue<int> q;
        q.push(s);
        vis[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            ++a[cnt];
            for (int v : g[u])
            {
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    sort(a + 1, a + cnt + 1);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i)
    {
        printf("%d%c", a[i], i == cnt ? '\n' : ' ');
    }
    return 0;
}

从一个起点沿边行走不会离开它的连通块；块中每个点都有一条从起点到它的路径，搜索会沿这些边逐步发现它。每次只从未标记的点启动，所以各次搜索集合互不重叠；外层检查全部顶点，保证没有块被遗漏。

搜索总时间为 $O(n+m)$，若共有 $c$ 个块，排序另需 $O(c\log c)$，总空间为 $O(n+m)$。有向图也能用 DFS/BFS 求从某点可达的集合，但单向可达不是这里的无向连通块；有向图的弱连通、强连通需要另作定义，本节程序只处理无向图。

4. 树为什么能确定父子关系

原道路图中可以沿 $1\to2\to4\to3\to1$ 走回出发点，中间顶点不重复，这样的闭合路线叫作环。现在删去 $(2,4)$，剩下 $1,2,3,4$ 之间没有环，但顶点 $5$ 仍孤立。再加入 $(3,5)$，全部点连起来，且没有产生新的环，得到一棵树。

左图红虚线标出被删除的 $(2,4)$，绿色边 $(3,5)$ 连接孤立点。中图以 $1$ 为根，右图以 $3$ 为根；两个有根画法使用相同的四条边。换根改变上下位置和父子关系，不会添加或删除边。

4.1 连通、无环和唯一路径

树是连通且无环的无向图。 简单路径要求路径中的顶点不重复。连通保证任意两点间至少有一条简单路径；如果有两条不同的简单路径，沿分开的部分走出去、再沿另一条返回，会形成环。因此树中任意两点间恰有一条简单路径。

删去树的任意一条边后，两端不能再连通，否则剩下的路径加上被删边就形成了环。这个性质意味着每条树边都不能随意省掉。

只有一个结点的树没有边。结点数大于 $1$ 时，从任意点沿不重复的顶点一直向前走，直到不能继续。终点除了来路没有其他邻居：有未走过的邻居就还能延长，有已走过的其他邻居就会形成环。这样的度数为 $1$ 的点叫作无根树的叶子。删掉它和唯一相连的边，剩下的仍是一棵树。反复删到只剩一个点，共删去 $n-1$ 个点和 $n-1$ 条边，所以树有 $n-1$ 条边。

仅有 $n-1$ 条边不足以判断是树。例如 $1,2,3$ 构成三角形，$4$ 孤立，四点三边仍不是树。必须同时保证相应的连通、无环条件。选根后常把没有孩子的点称为叶结点；这与前面无根树的度数定义要区分，单结点有根树的根也是叶结点。

4.2 选根之后，信息分别向哪里传

以 $1$ 为根，根到 $u$ 的唯一路径上，紧挨 $u$ 的前一个点就是它的父结点。沿边远离根的邻居是孩子；一个点和它的全部后代合起来组成它的子树。深度按根到它的边数计算，根深度为 $0$。

继续用树边 $(1,2)$、$(1,3)$、$(3,4)$、$(3,5)$：

结点	父结点	深度	子树包含的点	子树大小
1	无	0	1,2,3,4,5	5
2	1	1	2	1
3	1	1	3,4,5	3
4	3	2	4	1
5	3	2	5	1

从父结点 $u$ 走一条边到孩子 $v$，深度就增加 $1$，因此 $dep[v]=dep[u]+1$。子树大小却不能在刚到 $u$ 时立即确定：要先知道每个孩子的子树有多少点，再加上 $u$ 自己：

$$siz[u]=1+\sum_{v\text{ 是 }u\text{ 的孩子}}siz[v].$$

不同孩子的子树互不重叠，否则会出现到同一后代的两条路径；它们连同 $u$ 又覆盖整棵 $u$ 子树，所以这个加法既不漏算也不重复。

如果改以 $3$ 为根，$1$ 的父亲变为 $3$，$2$ 仍是 $1$ 的孩子。结点 $3$ 的子树从三个点变成全部五点，结点 $1$ 的子树变为 $1,2$。可见 siz 不是原图上与根无关的属性。

4.3 正序传深度，倒序汇总子树

队列遍历可以得到父亲一定在孩子之前的顺序 $1,2,3,4,5$。发现孩子时计算深度。随后反向处理 $5,4,3,2,1$，孩子就一定先于父亲完成。

图中左侧向下的箭头表示深度增加一，右侧表格中的箭头表示把孩子的子树大小加给父亲。先把每个 siz[u] 设为 $1$，表示只数自己。倒序不是重新遍历邻居，而是利用保存下来的顺序安排依赖。

倒序处理	加给父亲的值	更新结果
5	$siz[5]=1$ 加给 3	$siz[3]=2$
4	$siz[4]=1$ 加给 3	$siz[3]=3$
3	$siz[3]=3$ 加给 1	$siz[1]=4$
2	$siz[2]=1$ 加给 1	$siz[1]=5$
1	没有父亲	汇总结束

独立任务：第一行输入 $n,root$，接着输入 $n-1$ 条无向边，保证它们构成一棵树，$1\le n\le2\times10^5$。按结点编号依次输出深度，再输出子树大小。根可以不是 $1$。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, root, fa[N], dep[N], siz[N], que[N];
vector<int> g[N];
int main()
{
    scanf("%d%d", &n, &root);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fill(fa + 1, fa + n + 1, -1);
    fill(siz + 1, siz + n + 1, 1);
    int l = 1, r = 1;
    que[1] = root;
    fa[root] = 0;
    while (l <= r)
    {
        int u = que[l++];
        for (int v : g[u])
        {
            if (fa[v] != -1)
            {
                continue;
            }
            fa[v] = u;
            dep[v] = dep[u] + 1;
            que[++r] = v;
        }
    }
    // que 是父亲在前的遍历序，倒序时每个孩子已经完成汇总。
    for (int i = r; i > 1; --i)
    {
        int u = que[i];
        siz[fa[u]] += siz[u];
    }
    for (int i = 1; i <= n; ++i)
    {
        printf("%d%c", dep[i], i == n ? '\n' : ' ');
    }
    for (int i = 1; i <= n; ++i)
    {
        printf("%d%c", siz[i], i == n ? '\n' : ' ');
    }
    return 0;
}

fa[u]=-1 表示尚未发现，根的父亲记为 $0$；发现新点时立即设父亲，所以不会沿无向边走回来并再次入队。数组 que[1..n] 既保存 BFS 队列，也留下完整遍历顺序；根在首位，倒序循环到第 $2$ 位即可，不把根加给不存在的父亲。

每个点、每份邻接记录只处理常数次，时间和空间均为 $O(n)$。单点树得到深度 $0$、大小 $1$。链形树也不需要深递归。输入若不是树，这段程序可能得到一棵搜索生成树上的信息，不能把它解释成原图所有路径的子树信息。

练习 二叉树深度 按“根到叶经过几层”计深度，根算第 $1$ 层，并以左右孩子形式输入，结点数可达 $10^6$。应用本节边数深度时，需要加 $1$，也要相应调整容量和建图方式，不能直接提交上述教学任务的输入输出。

5. 二叉树的左右位置与三种遍历

一般有根树可以有许多孩子。二叉树则为每个结点指定左、右两个位置，各至多放一个孩子；即使只有一个孩子，也要说明它是左孩子还是右孩子。

结点的编号、保存的值、左右位置是三件事。例如编号 $2$ 的结点可以保存字母 B，并以编号 $4,5$ 为左右孩子。数组 lc[u]、rc[u] 保存孩子的编号，值为 $0$ 表示该位置没有孩子。不能因为某个结点编号较小，就把它当成左孩子。

5.1 进入、左侧返回、右侧返回

换用一棵明确有左右次序的五结点树：根 $1$ 的左、右孩子是 $2,3$，结点 $2$ 的左、右孩子是 $4,5$。其余点没有孩子。先到一个结点，再处理它的左子树，最后处理它的右子树。在这个过程里，有三个适合“输出当前结点”的时刻。

蓝色是当前处理的结点，旁边标出正在经历的阶段；底部三行分别积累三种遍历。这里三次记录是为了对照规则，实际任务通常只需要其中一种。

记录时刻	本子树内的记录顺序	这棵树的结果
刚进入当前结点	根、左、右，叫先序	1,2,4,5,3
左子树处理完之后	左、根、右，叫中序	4,2,5,1,3
左右子树都处理完之后	左、右、根，叫后序	4,5,2,3,1

例如结点 $2$ 的后序：先得到左子树中的 $4$，再得到右子树中的 $5$，最后才记录 $2$。把整个 4,5,2 当成根 $1$ 左子树的结果，再接右子树 3，最后记 1，就是整树后序。

先序适合先记录当前结构再进入孩子；后序适合先求孩子结果再汇总父结点。中序只是约定的一种顺序，普通二叉树的中序不保证结点值有序，后面的二叉搜索树才具有额外大小关系。

5.2 用阶段保存还没有完成的工作

先不写栈代码，想一想递归在孩子返回后要做什么：进入结点后要等左子树，左边结束后要等右子树，右边结束后才能返回父亲。因此一个工作现场需要保存结点编号 u 和阶段 p。

• p=0：还没进入左子树，可以记录先序；随后把当前现场改成 1，再进入左孩子。
• p=1：左子树已完成，可以记录中序；随后改成 2，再进入右孩子。
• p=2：两边都已完成，可以记录后序并弹出当前现场。

必须先修改父结点的阶段，再压入孩子，否则返回父结点时还会重复处理相同孩子。没有左孩子时，不压入新现场，下一轮直接进入阶段 1；右孩子为空同理。静态过程中的叶子 $4$ 会连续经历 0、1、2，然后返回 $2$。

独立任务：第一行输入 $n,root$，随后 $n$ 行输入编号 $1$ 到 $n$ 的左右孩子。保证表示合法二叉树，$1\le n\le2\times10^5$；也允许输入 0 0 表示空树。依次输出先序、中序、后序三行，空树输出三行空行。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, root, lc[N], rc[N], pre[N], in[N], post[N];
int a, b, c, top;
struct Frame
{
    int u, p;
} st[N];
int main()
{
    scanf("%d%d", &n, &root);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &lc[i], &rc[i]);
    }
    if (root)
    {
        st[++top] = {root, 0};
    }
    while (top)
    {
        int u = st[top].u, p = st[top].p;
        if (p == 0)
        {
            pre[++a] = u;
            st[top].p = 1;
            if (lc[u])
            {
                st[++top] = {lc[u], 0};
            }
        }
        else if (p == 1)
        {
            in[++b] = u;
            st[top].p = 2;
            if (rc[u])
            {
                st[++top] = {rc[u], 0};
            }
        }
        else
        {
            post[++c] = u;
            --top;
        }
    }
    for (int i = 1; i <= a; ++i)
    {
        printf("%d%c", pre[i], i == a ? '\n' : ' ');
    }
    for (int i = 1; i <= b; ++i)
    {
        printf("%d%c", in[i], i == b ? '\n' : ' ');
    }
    for (int i = 1; i <= c; ++i)
    {
        printf("%d%c", post[i], i == c ? '\n' : ' ');
    }
    if (n == 0)
    {
        printf("\n\n\n");
    }
    return 0;
}

每个结点恰好经历三个阶段，三份结果各记录它一次，所以时间为 $O(n)$。结果数组占 $O(n)$，现场栈最多为树高，最坏也为 $O(n)$。空树不入栈，单点树在三行各输出根。代码假定不存在环、共享孩子等非法结构，否则“每个孩子属于唯一父亲”的依据不再成立。

5.3 完全二叉树何时能直接计算孩子编号

如果除最后一层外每层都填满，最后一层的结点从左到右连续排列，中间没有空位，这样的二叉树叫作完全二叉树。它不要求最后一层也填满。

左图 $n=6$，最后一层是 $4,5,6$，最右位置空着，仍然是完全二叉树。按层从左到右编号时，父结点 $u$ 的两个孩子位置为 $2u$、$2u+1$；编号超过 $n$ 就不存在。于是结点 $3$ 的左孩子是 $6$，右孩子候选 $7$ 不存在。除根外，结点 $u$ 的父亲是 $\lfloor u/2\rfloor$。

右图只有右侧延伸，若仍按这些位置公式编号，会得到 $1,3,7,15$。只有四个点，编号却已经到 $15$；继续延伸时编号快速增大。如果把它们重新连续编号成 $1,2,3,4$，孩子又不再满足 $2u,2u+1$。因此一般二叉树使用独立的左右孩子数组。公式依赖树形与编号方式，计算 $2u+1$ 前也要确认整数类型能容纳。

6. 已知两种遍历，怎样恢复子树边界

求先序排列 给出中序和后序，结点由互不相同的大写字母表示，原题最多 $8$ 个结点，要求输出先序。直接枚举所有可能树形，再检查两串会产生很多无用尝试。后序的最后一个字符已经指出当前子树的根。

将上一节五个结点依次记作 A、B、C、D、E。中序是 DBEAC，后序是 DEBCA。后序末尾 A 是整树根；在中序找到 A，它左边 DBE 对应左子树，右边 C 对应右子树。

6.1 为什么一串的长度能切开另一串

左子树有三个结点，所以后序开头的三个字符 DEB 必须全属于左子树；紧接着的 C 属于右子树，末尾 A 已经用于根。现在左子树本身又成为同一种问题：中序 DBE，后序 DEB。它的根是 B，左右分别为 D、E。

橙色标当前根，蓝色表示它的左子树，绿色表示右子树。两串里同色的字符顺序可能不同，但字符数量相同。每次只处理当前子树对应的两段，不能在整条后序中另找一个固定位置当根。

字符串使用从 $0$ 开始的下标。设中序区间是 $[l,r]$，后序区间是 $[x,y]$；根是 post[y]，它在中序的位置为 $mid$，左子树长度 $len=mid-l$。

部分	中序闭区间	后序闭区间
左子树	$[l,mid-1]$	$[x,x+len-1]$
右子树	$[mid+1,r]$	$[x+len,y-1]$
根	$mid$	$y$

第一步具体得到左侧中序 $[0,2]$、后序 $[0,2]$，右侧中序 $[4,4]$、后序 $[3,3]$。接着处理左子树时，B 在中序下标 $1$，左右长度各为 $1$。先输出 A，再输出左子树先序 BDE，再输出 C，答案为 ABDEC。

如果某边没有结点，相应区间左端大于右端，递归直接返回。非空时先输出根，再递归处理左、右子树，恰好就是先序。这里无需另建孩子数组：已经确定了每个子树范围，直接按所需顺序输出即可。

#include <bits/stdc++.h>
using namespace std;
string in, post;
int pos[26];
void build(int l, int r, int x, int y)
{
    if (l > r)
    {
        return;
    }
    char c = post[y];
    int mid = pos[c - 'A'], len = mid - l;
    cout << c;
    build(l, mid - 1, x, x + len - 1);
    build(mid + 1, r, x + len, y - 1);
}
int main()
{
    cin >> in >> post;
    int n = in.size();
    for (int i = 0; i < n; ++i)
    {
        pos[in[i] - 'A'] = i;
    }
    build(0, n - 1, 0, n - 1);
    cout << '\n';
    return 0;
}

pos 预先保存每个字母在中序中的位置，避免每次从头寻找。每个结点作为当前子树的根处理一次，两侧又是不相交的剩余结点，所以时间为 $O(n)$。保存输入和位置需要 $O(n+26)$ 空间，递归栈最坏为 $O(n)$；原题只有八个点，不存在深链栈风险。若结点值允许重复，同一字符可能对应多个中序位置，这个方法的唯一切分依据就不再成立。

7. FBI 树：返回类型和后序输出各做什么

FBI 树 给出长度为 $2^N$ 的零一串，$0\le N\le10$。把当前串从中间平分为两段，继续平分，直到单字符。每段对应一个结点：全 0 是 B，全 1 是 I，混合是 F。要求输出这棵树的后序。

如果每到一个结点就重新扫描它对应的子串，同一个字符会在每一层被反复读取。能否直接用已经得到的左右孩子信息判断父亲？两个孩子都为 B，父亲就是 B；都为 I，父亲就是 I；其余情况含有 0 和 1，父亲就是 F。两个孩子都为 F 时，也仍为 F。

叶子对应单字符 0,0,1,1，类型为 B、B、I、I。左侧 00 的两个 B 合成 B，右侧 11 的两个 I 合成 I，根 0011 合成 F。图内上行箭头表示返回类型，旁边的序号表示输出先后，这两个方向不能混为一件事。

当前完成的区间	得到的类型	此时已输出
$[0,0]$	B	B
$[1,1]$	B	BB
$[0,1]$	B	BBB
$[2,2]$	I	BBBI
$[3,3]$	I	BBBII
$[2,3]$	I	BBBIII
$[0,3]$	F	BBBIIIF

函数 dfs(l,r) 的返回值供父亲合并，函数内部的输出满足题目的访问顺序。父亲必须先得到左右返回值，再输出自己；因此后序不需要另外保存。最短混合例 01 输出 BIF。

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
char dfs(int l, int r)
{
    char c;
    if (l == r)
    {
        c = s[l] == '0' ? 'B' : 'I';
    }
    else
    {
        int mid = (l + r) / 2;
        char a = dfs(l, mid), b = dfs(mid + 1, r);
        c = a == b ? a : 'F';
    }
    cout << c;
    return c;
}
int main()
{
    cin >> n >> s;
    dfs(0, (1 << n) - 1);
    cout << '\n';
    return 0;
}

长度 $L=2^N$ 的字符串产生 $L$ 个叶子。每个内部结点恰好分成两个孩子，整棵树有 $L-1$ 个内部结点，总共 $2L-1$ 个结点；每个结点只判断或合并一次，时间为 $O(L)$。递归栈深度为 $N+1=O(\log L+1)$，字符串占 $O(L)$。$N=0$ 时只有一个字符，直接输出 B 或 I，也不会继续平分。

8. 二叉搜索树：怎样排除一整棵子树

普通二叉树只规定左右位置，并不规定大小。现在增加一个约束：每个结点左子树的所有值都小于它，右子树的所有值都大于它，各子树也满足这个规则。这就是本节讨论的二叉搜索树，保存的整数互不相同。

8.1 从一次插入看比较的作用范围

依次插入 $3,1,4,2$。树为空时，$3$ 成为根。插入 $1$，因 $1<3$ 去左侧；插入 $4$ 去右侧。插入 $2$ 时，先因 $2<3$ 进入以 $1$ 为根的子树，再因 $2>1$ 进入 $1$ 的右侧空位置。

圆圈中的大字是结点值，小字是存储编号。编号按新建顺序为 $1,2,3,4$，并不是值的大小顺序。最终的存储如下，孩子字段保存编号：

编号	值	左孩子编号	右孩子编号
1	3	2	3
2	1	0	4
3	4	0	0
4	2	0	0

查找 $2$ 重复同样的比较路径，经过值 $3,1,2$。查找 $5$，从 $3$ 走到 $4$，再往右遇到空位置，说明不存在。

排除另一边依赖的是整棵子树的大小约束。若 $x<3$，右子树每个值都大于 $3$，就都不可能是 $x$；只保证右孩子本身大于 $3$ 还不够。中序先访问所有较小值，再访问根，再访问所有较大值，递归下去就得到严格递增的序列。

8.2 代码中的空位置与新编号

独立任务：先输入操作数 $q$，$1\le q\le5000$；随后每行输入 op x，$|x|\le10^9$。op=1 插入 $x$，已经存在时忽略；op=2 查询 $x$ 是否存在，输出 1 或 0。树最初为空。

用 root=0 表示空树，孩子编号为 $0$ 表示没有孩子。每次真正插入，tot 加一，给新编号保存值，再把父结点对应的孩子改成该编号。全局数组初始为零，所以新点的左右孩子自动为空。相等时直接结束，不创建第二个同值结点。

#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 10;
int q, root, tot, a[N], lc[N], rc[N];
void insert(int x)
{
    if (!root)
    {
        root = ++tot;
        a[root] = x;
        return;
    }
    int u = root;
    while (true)
    {
        if (a[u] == x)
        {
            return;
        }
        int v = x < a[u] ? lc[u] : rc[u];
        if (!v)
        {
            a[++tot] = x;
            if (x < a[u])
            {
                lc[u] = tot;
            }
            else
            {
                rc[u] = tot;
            }
            return;
        }
        u = v;
    }
}
bool find(int x)
{
    int u = root;
    while (u)
    {
        if (a[u] == x)
        {
            return true;
        }
        u = x < a[u] ? lc[u] : rc[u];
    }
    return false;
}
int main()
{
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            insert(x);
        }
        else
        {
            printf("%d\n", find(x));
        }
    }
    return 0;
}

一次查找或插入只沿一条向下路径，时间为 $O(h+1)$，其中 $h$ 是按边计的树高。若依次插入 $1,2,3,4$，每个新值都比前面的大，图中下方的退化形态就是一条链。普通二叉搜索树不保证 $O(\log n)$；本任务最多 5000 次操作，最坏总时间 $O(q^2)$，保存的结点不超过 $q$，空间 $O(q)$。

练习 普通二叉树（简化版） 还要求排名、按排名查询、前驱和后继。这些是继续训练的任务，不能直接用“是否存在”代替；其中排名需要额外维护子树中的元素个数，并沿比较路径累计被跳过的部分。题目保证插入前该值不存在，本节则主动定义了重复插入时忽略的行为。

9. 哈夫曼树：每次合并如何累计为叶子深度

第九章用小根堆取出当前最小的两堆解决合并果子。本节继续研究同一合并过程：为什么每次合并可以画成树，总代价又为什么能按原来的每一堆来算。

9.1 从合并记录画出一棵树

有重量为 $1,2,3,4$ 的四堆。先把 $1,2$ 合成新堆 $3$，再把新堆 $3$ 和原来的 $3$ 合成 $6$，最后与 $4$ 合成 $10$。注意两个重量为 $3$ 的结点来源不同，不能把它们合成同一个结点。

原来的堆是叶子；每次把两个当前堆连到一个新父结点，父结点权值就是两个孩子之和。橙色标本轮新建的父结点，底部是本轮和累计代价。最终树见静态图。

原始重量	经过的祖先合并	深度	在总代价中贡献
1	3、6、10	3	$1\times3=3$
2	3、6、10	3	$2\times3=6$
3	6、10	2	$3\times2=6$
4	10	1	$4\times1=4$

按内部结点计费，总代价是 $3+6+10=19$。按原始叶子计费，是 $3+6+6+4=19$。每个原始重量每经过一次祖先合并，就在那次新堆重量中出现一次；祖先个数正好是从根到叶的边数。因此，若叶子重量为 $w_i$、深度为 $d_i$，总代价等于

$$\sum_i w_i d_i.$$

9.2 为什么可以先合并最小的两项

任何合并方案都能画成每个内部结点恰有两个孩子的二叉树。在最深层取一个叶子，它的兄弟也必须是叶子；若兄弟还有孩子，那些孩子会更深，违反最深层的选择。因此最深处有一对兄弟叶子。

把较小的重量放得更深，不会增加总代价。设 $a\le b$，两个位置深度 $p\le q$。原来小重量在浅处的代价为 $ap+bq$，交换后的代价为 $aq+bp$，两者之差是

$$(aq+bp)-(ap+bq)=(b-a)(p-q)\le0.$$

现在取一棵最优树，把全体最小的两个重量交换到那对最深兄弟位置上，代价不会增大，所以仍有一个最优方案让它们成为兄弟。把这两个叶子缩成重量为两者之和的一个叶子，缩小后的问题仍然是“合并这些重量”。原问题总代价等于缩小问题的总代价，加上这两个重量的和。

如果缩小问题还有更优方案，展开这对叶子就能改进原来的最优树，产生矛盾。因此可以先合并当前最小的两项，再对剩余问题重复这个规则。小根堆负责快速找到它们，新堆必须放回，参加之后的比较。

9.3 直接计算总代价

独立任务：输入 $n$ 和 $n$ 个正整数重量，$1\le n\le2\times10^5$、每个重量不超过 $10^6$。每次允许合并任意两堆，代价是两堆重量之和，求合成一堆的最小总代价。若只要总代价，不需要真的保存树边；合并树用来解释代价与正确性。

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
priority_queue<long long, vector<long long>, greater<long long>> q;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        q.push(x);
    }
    while (q.size() > 1)
    {
        long long x = q.top();
        q.pop();
        long long y = q.top();
        q.pop();
        ans += x + y;
        q.push(x + y);
    }
    printf("%lld\n", ans);
    return 0;
}

共进行 $n-1$ 次合并，每次堆操作需要 $O(\log n)$，总时间 $O(n\log n)$，空间 $O(n)$。只有一堆时循环不执行，答案为 $0$。总重量至多 $2\times10^{11}$，每次合并代价不会超过总重量；即使用粗略的 $(n-1)$ 倍上界，总代价也小于 $4\times10^{16}$，故使用 long long 能容纳，int 则不够。

合并果子 是该模型的练习。若改为只能合并相邻两堆，交换叶子位置就可能违反相邻限制，上面的证明失效。这正是第十二章区间 DP 中需要重新分析的条件。

9.4 从根到叶的路径成为编码

如果叶子表示字符，重量表示出现次数，可以给左边写 0、右边写 1，从根走到某个字符叶子，沿途的 0、1 就是它的编码。频次大的字符若较浅，每次出现使用的位数就较少；总位数仍是频次乘深度之和。

A、B、C 的频次为 $5,2,1$。先合并 B、C，再与 A 合并，可以安排 A 在根的左侧，B、C 在右子树的左右侧，编码分别为 0、10、11。总位数是 $5\times1+2\times2+1\times2=11$。交换同一父结点的左右孩子会改变码字，但不改变任何叶子的深度和总位数。

一个码字若是另一个的前缀，意味着到达前一个字符后，还要继续往下才能到另一个字符。但字符只放在叶子，叶子没有孩子，所以这种情况不会发生。接收比特时，从根沿边走，到叶子就识别出一个字符，再回根读下一段。

只有一种字符时，树根本身就是叶子，根到它的路径为空。实际编码协议必须另外约定用一位表示、或记录字符数量等信息；否则仅靠空码串无法恢复出现次数。这是编码应用的约定，不能从合并代价为零直接推成“无需任何信息”。

10. 练习时要复现哪些过程

• 查找文献：先画引用方向，再手写某点返回后应继续检查的邻边；核对 DFS、BFS 各自的标记。
• 二叉树深度：先确定根算第几层，再从父结点计算孩子深度；规模较大时使用队列或显式栈。
• 新二叉树：把字符结点映射到左右孩子，识别输入中的 * 空位置；原题首行描述的结点就是根，最多 26 个结点。
• 求先序排列：给每次递归写出两串对应的区间，核对左子树长度与后序切分位置。
• FBI 树：在同一个结点分别指出返回给父亲什么、什么时候输出，不能只记住后序字符串。
• 普通二叉树（简化版）：在已有大小关系上继续维护子树数量，再考虑排名、前驱与后继。
• 合并果子：画出至少三次合并，分别按内部合并代价与叶子带权深度求和，检查两者一致。

图的存储回答“邻居在哪里”，遍历回答“下一步展开谁”；树的唯一路径进一步确定父子关系。面对新任务，应先说清当前状态代表顶点、子树还是一个合并结果，再决定信息沿哪个方向传递。