欢迎大家来到数据结构的第一大重难点组成：树与二叉树。这两个概念不但在数据结构中得到广泛应用，它们的思想甚至渗透了包括但不限于计算机相关学科的各个领域之内。也就是说，生活中，这种树形结构你随处可见。哎呀，跑题了，总而言之，这一章的内容会很长，请各位参与复习的道友耐心阅读。

树与二叉树

树

一棵树的结构示例

首先我们来介绍一下树，就像大家平时在外边看到的大树一样，树这种数据结构是一个节点后面跟着好几个叉的结构。以下是详细内容。

相关概念（纯给零基础的科普用）：

  • 树：$n(n \ge 0)$个节点的有限集，当$n = 0$时称为空树。

  • 根节点：树这种数据结构中没有前驱，可以有零个或多个后继的节点。这里面$A$是根节点。

  • 子树：当$n \gt 1$时，其余节点可分成$m$个互不相交的有限集$T_1, T_2, \dots T_m$，其中每个集合本身又是一棵树。

  • 祖先：考虑节点$K$，从根节点$A$到节点$K$的唯一路径上经过的所有其他节点。

  • 子孙：树中任意一个节点为根节点的子树上，除去根节点之外的其他所有节点都是这个节点的子孙。

  • 双亲：其实就是父节点。

  • 兄弟节点：有相同父节点的节点互为兄弟节点。

  • 堂兄弟节点：父节点位于同一层的节点互为堂兄弟节点。

  • 层次：节点的层次从根开始定义，根为第一层，其孩子为第二层，以此类推。

  • 深度：节点的深度即其所在层次。

  • 高度：树的高度，也叫树的深度，是树中节点的最大层数；节点的高度是指以其为根的子树的高度。

  • 度：树中一个节点的子节点的数量称为节点的度；所有节点的度的最大值是树的度。

  • 分支节点：度大于$0$的节点。

  • 叶子节点：度为$0$的节点。

  • 有序树和无序树：树中各节点的子树从左到右有固定次序、不可互换，则称为有序树；否则称为无序树。

  • 路径和路径长度：两个节点之间的路径是从一个节点到另一个节点所经过的节点序列构成的；路径长度是该路径上边的数目。树的路径长度是根节点到所有节点的路径长度之和。

  • 森林：是$m(m \ge 0)$棵不相交的树的集合。

树的性质（选择题会考）

  • 树的节点数$n$等于所有节点的度数之和加$1$。

  • 度为$m$的树中，第$i$层上至多有$m^{i - 1}$个节点。

  • 高度为$h$的$m$叉树至多有$\frac{m^h - 1}{m - 1}$个节点。

  • 度为$m$，具有$n$个节点的树的最小高度$h$为$\lceil \log_m(n(m - 1) + 1) \rceil$。

  • 度为$m$，具有$n$个节点的树的最大高度$h$为$n - m + 1$。

二叉树

概念

二叉树是一种特殊的树形结构，每个节点最多只能有两棵子树，且这两棵子树有明确的左右之分，次序固定，不可调换。所以二叉树和度为$2$的有序树很像。但是二叉树可以为空，但度为$2$的子树至少包含$3$个节点。

几种特殊的二叉树

这里仅介绍一些基础的特殊二叉树，像红黑树什么的比较高精尖的我们不讲，考研初试不会考。

满二叉树

  • 概念：高度为$h$，且包含$2^h - 1$个节点的二叉树，即每一层都含有该层所能容纳的最大数量的节点。可对满二叉树进行编号，根节点编号为$1$，自上而下，自左至右编号。对于编号为$i$的节点，其父节点编号为$\lfloor \frac{i}{2} \rfloor$，若其存在左孩子，则左孩子编号为$2i$，若其存在右孩子，则右孩子编号为$2i + 1$。

完全二叉树

  • 概念：高度为$h$且包含$n$个节点的二叉树，其每个节点与高度为$h$的满二叉树一一对应。

满二叉树和完全二叉树特别适合用顺序存储方式表示，因为节点好找。

二叉排序树

  • 概念：左子树上所有节点的关键字均小于根节点的关键字，右子树上所有节点的关键字均大于根节点的关键字。

平衡二叉树

  • 概念：树中任意一个节点的左子树和右子树的高度差的绝对值不超过$1$。

关于二叉排序树和平衡二叉树的性质和算法，本文暂不展开。

正则二叉树

  • 概念：树中每个分支节点都有$2$个孩子，即树中仅有度为$0$或$2$的节点。

二叉树的性质（同样是选择题会考）

  • 非空二叉树的叶节点等于度为$2$的节点数加$1$，即$n_0 = n_2 + 1$。

  • 非空二叉树的第$k$层最多有$2^{k - 1}$个节点（$k \ge 1$）。

  • 高度为$h$的二叉树最多有$2^h - 1$个节点（$h \ge 1$）。

  • 对完全二叉树按从上到下、从左到右的顺序依次编号$1, 2, \cdots, n$，则有以下关系：

    • 最后一个分支节点的编号是$\lfloor n/2 \rfloor$。

    • 若$i \le \lfloor n/2 \rfloor$，则节点$i$是分支节点，否则是叶节点。

    • 叶节点只可能出现在最后两层。

    • 若存在度为$1$的节点，则最多只能有一个，且该节点只有左孩子没有右孩子。

    • 按层序编号后，一旦某个节点$i$为叶节点或只有左孩子，那么所有编号大于$i$的节点都是叶节点。

    • 若$n$是奇数，则每个分支节点都有左右孩子；若$n$是偶数，则编号最大的分支节点只有左孩子没有右孩子，其他分支节点都有左右孩子。

    • 当$i > 1$时，节点$i$的父节点编号是$\lfloor i/2 \rfloor$。

    • 若节点$i$有左右孩子，则左孩子编号是$2i$，右孩子编号是$2i+1$。

    • 节点$i$所在层次是$\lfloor \log_2 i \rfloor + 1$。

二叉树的存储结构

二叉树主要有两种存储结构：顺序存储结构和链式存储结构，前者把节点按次序排布在一起，后者用指针把节点串起来。

顺序存储结构

  • 概念：用一组地址连续的存储单元（也就是数组）依次存放二叉树中的节点。因为完全二叉树按层序编号后，节点$i$的左孩子编号是$2i$、右孩子编号是$2i+1$、父节点编号是$\lfloor i/2 \rfloor$，所以只要把节点按编号依次放进数组，用下标的算术运算就能确定节点之间的父子关系，并不需要额外的指针。

  • 优点：结构简单，不存指针因而省空间，而且能按下标随机访问任意节点。

  • 缺点：只适合完全二叉树。要是非完全二叉树（尤其是一路向右的右斜树），为了保住编号关系，空缺的位置也得照样占着，空间浪费极大：一棵高度为$h$的右斜树只有$h$个节点，却要占用大约$2^h - 1$个存储单元。

链式存储结构

  • 概念：给每个节点配一个结构体，里面除了存放数据的数据域，再放两个分别指向左孩子、右孩子的指针域：
typedef struct BiTNode
{
    ElemType data;                       // 数据域
    struct BiTNode *lchild, *rchild;     // 左、右孩子指针
} BiTNode, *BiTree;

  • 这种每个节点只有两个指针域的链表称为二叉链表；如果觉得找父节点不方便，还可以再增加一个指向父节点的指针，得到三叉链表。

  • 优点：对任意形状的二叉树都适用，不像顺序存储那样浪费空间，插入、删除节点也比较方便。

  • 缺点：访问节点只能顺着指针一级级走，不能像数组那样按下标随机访问；二叉链表找父节点也很麻烦，只能从头遍历。

  • 一个常考的小结论：一棵含$n$个节点的二叉链表共有$2n$个指针域，其中$n - 1$个用来指向孩子（除根节点外每个节点恰好被一个指针指着），因此空指针域有$2n - (n - 1) = n + 1$个。

二叉树的遍历

二叉树的遍历，是指按照某种次序依次访问树中的每一个节点，使每个节点都被访问一次且仅被访问一次。按照访问根节点的先后次序，二叉树的遍历可分为先序遍历、中序遍历和后序遍历三种。

先根遍历（先序遍历）

  • 过程：先访问根节点，再先序遍历左子树，最后先序遍历右子树。

  • 代码：

void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        visit(T);               // 访问根节点
        PreOrder(T->lchild);    // 递归先序遍历左子树
        PreOrder(T->rchild);    // 递归先序遍历右子树
    }
}

中根遍历（中序遍历）

  • 过程：先中序遍历左子树，再访问根节点，最后中序遍历右子树。

  • 代码：

void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);     // 递归中序遍历左子树
        visit(T);               // 访问根节点
        InOrder(T->rchild);     // 递归中序遍历右子树
    }
}

后根遍历（后序遍历）

  • 过程：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

  • 代码：

void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild);   // 递归后序遍历左子树
        PostOrder(T->rchild);   // 递归后序遍历右子树
        visit(T);               // 访问根节点
    }
}

层次遍历

  • 过程：从上到下、从左到右逐层访问二叉树的各节点。

  • 代码：

层次遍历需要借助一个队列，首先将根节点入队，随后不断出队并访问队头结点，同时将其存在的左右孩子依次加入队尾，直到队列为空。

#include <queue>
using namespace std;

void LevelOrder(BiTree T)
{
    queue<BiTree> Q;
    if (T != NULL)
        Q.push(T);
    while (!Q.empty())
    {
        BiTree p = Q.front();
        Q.pop();
        visit(p);
        if (p->lchild != NULL)
            Q.push(p->lchild);
        if (p->rchild != NULL)
            Q.push(p->rchild);
    }
}

一个例子

以如下二叉树为例：

        A
       / \
      B   C
     / \   \
    D   E   F

  • 先序遍历：$A, B, D, E, C, F$

  • 中序遍历：$D, B, E, A, C, F$

  • 后序遍历：$D, E, B, F, C, A$

  • 层次遍历：$A, B, C, D, E, F$

可以看出，三种遍历的递归代码几乎完全对称，唯一的区别就是visit(T)这一句分别放在左、中、右三个位置上。

通过已知遍历序列构造二叉树（选择题）

由遍历序列反推出一棵二叉树是很常见的考法，其中的关键就是中序序列：只要给出中序序列，再配上先序、后序、层序中的任意一种，就能唯一确定一棵二叉树。

由先序序列和中序序列构造

  • 思路：先序序列的第一个元素就是根节点。在中序序列里找到这个根节点，它左边的部分是左子树的中序序列、右边的部分是右子树的中序序列，据此数出左右子树的节点个数，再回到先序序列里把根节点后面的元素切分成左右子树的先序序列，最后对左右子树递归处理。

  • 例子：已知先序序列$A, B, D, E, C, F$，中序序列$D, B, E, A, C, F$。

    • 先序的首元素$A$是根；中序里$A$的左边是$D, B, E$（左子树），右边是$C, F$（右子树）。
    • 左子树：先序为$B, D, E$、中序为$D, B, E$，根是$B$，左孩子$D$、右孩子$E$。
    • 右子树：先序为$C, F$、中序为$C, F$，根是$C$，没有左孩子、有右孩子$F$。

还原出的二叉树为：

        A
       / \
      B   C
     / \   \
    D   E   F

由后序序列和中序序列构造

  • 思路：后序序列的最后一个元素就是根节点，其余步骤和先序完全一样——在中序序列里定位根节点、切分出左右子树，再对左右子树递归处理。

  • 例子：已知后序序列$D, E, B, F, C, A$，中序序列$D, B, E, A, C, F$。

    • 后序的末元素$A$是根；中序里$A$的左边是$D, B, E$，右边是$C, F$。
    • 左子树：后序为$D, E, B$、中序为$D, B, E$，根是$B$，左孩子$D$、右孩子$E$。
    • 右子树：后序为$F, C$、中序为$C, F$，根是$C$，没有左孩子、有右孩子$F$。

还原出的二叉树与上例完全相同。

由层序序列和中序序列构造

  • 思路：层序序列的第一个元素就是根节点。在中序序列里定位根节点、切分出左右子树后，再把层序序列中剩下的元素按它们分别落在左、右子树的中序区间里，分成左右子树的层序序列（保持原有先后次序），然后对左右子树递归处理。

  • 例子：已知层序序列$A, B, C, D, E, F$，中序序列$D, B, E, A, C, F$。

    • 层序的首元素$A$是根；中序里$A$的左边是$D, B, E$，右边是$C, F$。
    • 左子树：层序为$B, D, E$、中序为$D, B, E$，根是$B$，左孩子$D$、右孩子$E$。
    • 右子树：层序为$C, F$、中序为$C, F$，根是$C$，没有左孩子、有右孩子$F$。

还原出的二叉树同样与上例完全相同。

需要特别注意的是：先序序列、后序序列和层序序列中的任意两种组合，通常都无法唯一确定一棵二叉树。例如下面两棵二叉树：

  • 树$1$：根节点为$A$，$B$是$A$的左子节点；
  • 树$2$：根节点为$A$，$B$是$A$的右子节点。

它们的先序序列都是$A, B$，后序序列都是$B, A$，层序序列都是$A, B$。既然三种序列在这两棵树上完全一样，那么无论给出先序＋后序、先序＋层序还是后序＋层序，都会同时满足这两棵树，无法判断$B$究竟是左孩子还是右孩子，自然也就不能唯一确定一棵二叉树。

线索二叉树

概念

遍历一棵二叉树，就是把它的每个节点按某种次序访问一遍，得到一个线性的访问序列；序列里除第一个和最后一个节点外，每个节点都有唯一的前驱和后继。可普通的二叉链表只能顺着指针找到左右孩子，想直接得到某个节点在某种遍历次序下的前驱或后继，就得把整棵树重新遍历一遍，很不方便。

前面算过，含$n$个节点的二叉链表有$n+1$个空指针域。线索二叉树就是把这些空指针利用起来：约定节点的左指针若为空，就让它指向该节点在某种遍历次序下的前驱；右指针若为空，就让它指向该节点在该次序下的后继。为了区分指针到底指向孩子还是前驱、后继，再给每个节点增加两个标志位$ltag$和$rtag$：

  • $ltag=0$：$lchild$指向左孩子；$ltag=1$：$lchild$指向前驱。
  • $rtag=0$：$rchild$指向右孩子；$rtag=1$：$rchild$指向后继。

这样得到的二叉链表称为线索链表，其中指向前驱、后继的指针称为线索；把一棵二叉树按某种次序遍历、并把它改造成线索二叉树的过程称为线索化，按先序、中序、后序线索化就分别得到先序线索二叉树、中序线索二叉树和后序线索二叉树。

线索链表的节点结构

线索二叉树的节点比普通二叉链表多出两个标志位：

typedef struct ThreadNode
{
    ElemType data;                       // 数据域
    struct ThreadNode *lchild, *rchild;  // 左、右孩子指针（或前驱、后继线索）
    int ltag, rtag;                      // 左、右线索标志
} ThreadNode, *ThreadTree;

中序线索二叉树的构造

  • 描述：中序线索化就是一边做中序遍历，一边把节点的空指针改成线索。遍历时用一个指针$pre$始终指向“刚刚访问过的节点”，它也正是当前节点的前驱。当访问到节点$p$时：

    • 若$p$的左指针为空，就把它指向$pre$、并把$ltag$置$1$，也就是记下$p$的前驱；
    • 若$pre$的右指针为空，就把它指向$p$、并把$rtag$置$1$，也就是记下$pre$的后继；
    • 最后令$pre=p$，继续遍历。

    整棵树遍历完后，最后一个节点的右指针仍为空，把它也置成线索即可。

  • 代码：

ThreadNode *pre = NULL;        // 全局变量，始终指向当前节点的前驱

void InThread(ThreadTree p)
{
    if (p != NULL)
    {
        InThread(p->lchild);                     // 中序线索化左子树
        if (p->lchild == NULL)                   // 左指针为空，建立前驱线索
        {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL)  // 前驱的右指针为空，建立后继线索
        {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;                                 // 更新 pre
        InThread(p->rchild);                     // 中序线索化右子树
    }
}

void CreateInThread(ThreadTree T)
{
    pre = NULL;
    if (T != NULL)
    {
        InThread(T);
        if (pre->rchild == NULL)                 // 处理中序最后一个节点
            pre->rtag = 1;
    }
}

中序线索二叉树的遍历

  • 描述：有了中序线索，遍历时就不用再借助栈或递归了。先找到中序序列的第一个节点（从根一路向左，直到某个节点的$ltag=1$），访问它；然后反复求当前节点的中序后继并访问，直到没有后继为止。

  • 找后继：节点$p$的中序后继分两种情况：

    • 若$p$的$rtag=1$，则$rchild$就是后继线索，直接返回；
    • 若$p$的$rtag=0$，说明$p$有右子树，其中序后继是右子树中中序最先访问的节点，也就是从$p$的右孩子一路向左、直到$ltag=1$的那个节点。

  • 代码：

// 求以 p 为根的子树中，中序遍历最先访问的节点（最左下节点）
ThreadNode *FirstNode(ThreadNode *p)
{
    while (p->ltag == 0)      // 一路向左，直到左指针是线索
        p = p->lchild;
    return p;
}

// 求节点 p 在中序序列中的后继
ThreadNode *NextNode(ThreadNode *p)
{
    if (p->rtag == 1)         // 右指针是线索，它本身就是后继
        return p->rchild;
    else                      // 否则后继是右子树中最左下的节点
        return FirstNode(p->rchild);
}

// 中序遍历中序线索二叉树
void InOrder(ThreadTree T)
{
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
        visit(p);
}

先序线索二叉树与后序线索二叉树的特点

  • 先序线索二叉树：
    • 找先序后继很方便：若节点有左孩子（$ltag=0$），左孩子就是它的先序后继；否则（$ltag=1$）$rchild$就是后继——要么是右孩子，要么是右线索。
    • 找先序前驱却很不方便：仅凭节点自身的指针得不到，必须知道它的父节点（要用三叉链表），所以先序线索二叉树一般不拿来找前驱。
    • 线索化时要格外小心：因为先序先访问根，所以必须在递归左子树之前判断$ltag$，否则刚建立的前驱线索会把递归带回前驱处，造成死循环。
  • 后序线索二叉树：
    • 找后序前驱很方便：若节点有右孩子（$rtag=0$），右孩子就是它的后序前驱（后序里右子树的根紧接着它被访问）；否则（$rtag=1$）$lchild$就是前驱——要么是左孩子，要么是左线索。
    • 找后序后继却很不方便：同样必须借助父节点才能确定，所以后序线索二叉树一般不拿来找后继。
    • 线索化时要先把左右子树都处理完，最后再给根节点建立线索。
  • 相比之下，中序线索二叉树的前驱和后继都能直接从线索得到，不用知道父节点，所以实际中最常用。

查找节点后继的思想

求某个节点的后继，通用的思路是先看右指针的性质：

  • 若$rtag=1$，右指针本身就是线索，直接指向后继，一步到位；
  • 若$rtag=0$，说明右指针指向的是孩子（右子树存在），后继就落在右子树里，需要进入右子树、按对应次序找“最先被访问”的那个节点。

只不过三种次序下“右子树里最先被访问的节点”并不一样：

  • 中序：右子树中最左下的节点；
  • 先序：若节点有左孩子，后继其实是左孩子，跟右指针无关，只有没有左孩子时才用右指针；
  • 后序：不能只看右子树，必须借助父节点才能确定。

说到底，线索化的本质就是把“要重新遍历一遍才能找到前驱、后继”这件事，简化成“顺着线索走一步”或“在一棵子树里朝固定方向走到底”，从而让遍历和查找都摆脱递归和栈。

相关题目

终于来到千呼万唤始出来的练习题环节了，看知识点都看迷瞪的了吧。做几道题活活脑子。

$1$、假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

这道题采用层次遍历的算法，用变量$level$记录当前节点所在的层数，设置变量$last$指向当前层的最右节点，每次层次遍历出队的时候，令出队节点与$last$指针作比较，若两者相等，则层数加$1$，并让$last$指向下一层的最右节点，直到遍历完成。此时$level$的值就是二叉树的高度。

#include <queue>
using namespace std;

int TreeHeight(BiTree T)
{
    if (T == NULL)
        return 0;
    queue<BiTree> Q;
    Q.push(T);
    int level = 0;                 // 记录当前层数
    BiTree last = T;               // 指向当前层的最右节点
    while (!Q.empty())
    {
        BiTree p = Q.front();
        Q.pop();
        if (p->lchild != NULL)     // 左孩子入队
            Q.push(p->lchild);
        if (p->rchild != NULL)     // 右孩子入队
            Q.push(p->rchild);
        if (p == last)             // 出队的正是本层最右节点，本层结束
        {
            level++;               // 层数加一
            if (!Q.empty())
                last = Q.back();   // last 指向下一层的最右节点
        }
    }
    return level;
}

$2$、二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否是完全二叉树的算法。

根据完全二叉树的性质，具有$n$个节点的完全二叉树与满二叉树中编号$1 \sim n$的节点一一对应，所以这道题我们采用层次遍历的算法，将每个节点加入队列（包括空节点），遇到空节点时，查看其后是否有非空节点。若有，则二叉树不是完全二叉树。

bool IsComplete(BiTree T) 
{
	queue<BiTree> q;
	if (T == nullptr) 
	{
		return true;
	}
	q.push(T);
	bool flag = false;	// 尚未遇到空节点
	while (!q.empty()) 
	{
		BiTree p = q.front();
		q.pop();
		if (p == nullptr) 
		{
			flag = true;	// 遇到空节点
		} 
		else 
		{
			if (flag) 
			{
				return false;	// 遇到空节点后又遇到非空节点，说明不是完全二叉树
			}
			q.push(p->lchild);
			q.push(p->rchild);
		}
	}
	return true;	// 遍历完所有节点，说明是完全二叉树
}

$3$、假设二叉树采用二叉链表存储结构，试设计一个算法，计算一棵给定二叉树的所有双分支节点数。

这道题还是层次遍历二叉树，遇到双分支节点计数就加$1$，直到遍历完二叉树。

int CountTwoChildNodes(BiTree T) 
{
	if (T == nullptr) 
	{
		return 0;
	}
	queue<BiTree> q;
	q.push(T);
	int count = 0;
	
	while (!q.empty())
	{
		BiTree p = q.front();
		q.pop();
		if (p->lchild != nullptr && p->rchild != nullptr) 
		{
			count++;
		}
		if (p->lchild != nullptr) 
		{
			q.push(p->lchild);
		}
		if (p->rchild != nullptr) 
		{
			q.push(p->rchild);
		}
	}
	return count;
}

$4$、设一棵采用链式存储结构的二叉树，编写一个把其中所有节点的左右子树进行交换的函数。

这道题可以用先序遍历方法，递归处理。

void SwapLeftRight(BiTree T) 
{
	if (T == nullptr) 
	{
		return;                         // 空结点直接返回
	}

	// 1. 交换当前结点的左右孩子
	BiTree temp = T->lchild;
	T->lchild = T->rchild;
	T->rchild = temp;

	// 2. 递归交换左子树和右子树
	SwapLeftRight(T->lchild);
	SwapLeftRight(T->rchild);
}

$5$、已知二叉树采用二叉链表存储，对于树中每个值为$x$的节点，删除以它为根的子树，并释放相应的空间。

这道题用先序遍历法，找到一个值为$x$的节点就销毁以它为根节点的子树。

void DestroyTree(BiTree T) 
{
	if (T == nullptr) 
	{
		return;
	}
	DestroyTree(T->lchild);             // 先销毁左子树
	DestroyTree(T->rchild);             // 再销毁右子树
	delete T;                           // 最后释放当前结点
}

BiTree DeleteXSubtree(BiTree T, int x) 
{
	if (T == nullptr) 
	{
		return nullptr;
	}

	// 当前结点值为 x：销毁整棵子树，返回空
	if (T->data == x) 
	{
		DestroyTree(T);
		return nullptr;
	}

	// 否则先序递归处理左右子树，并把返回值接回指针
	T->lchild = DeleteXSubtree(T->lchild, x);
	T->rchild = DeleteXSubtree(T->rchild, x);

	return T;
}

$6$、一棵采用链式存储结构的二叉树，编写算法找出节点$p$和$q$的最近公共祖先。

采用非递归的后序遍历，栈中存放二叉树节点的指针，当访问到节点$p$或$q$时，栈中所有元素均是该节点的祖先。所以遍历$p$之后，把栈中元素复制到辅助栈中，然后继续遍历节点$q$，把遍历结果的栈和辅助栈元素挨个匹配，最长公共前缀的最后一个元素就是它们的最近公共祖先。

#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

BiTree FindLCA_PostOrder(BiTree T, BiTree p, BiTree q)
{
	if (T == nullptr || p == nullptr || q == nullptr)
	{
		return nullptr;
	}
	if (p == q)
	{
		return p;
	}

	stack<BiTree> st;
	vector<BiTree> path1;           // 先访问到的那个节点的路径（栈底→栈顶）
	BiTree cur = T;
	BiTree lastVisited = nullptr;
	bool foundFirst = false;

	while (cur != nullptr || !st.empty())
	{
		while (cur != nullptr)      // 一路向左
		{
			st.push(cur);
			cur = cur->lchild;
		}

		cur = st.top();

		// 右子树为空或已访问完，才能访问 cur
		if (cur->rchild == nullptr || cur->rchild == lastVisited)
		{
			if (cur == p || cur == q)
			{
				if (!foundFirst)
				{
					// 第一次找到：复制栈内容
					foundFirst = true;
					stack<BiTree> tmp = st;
					while (!tmp.empty())
					{
						path1.push_back(tmp.top());
						tmp.pop();
					}
					reverse(path1.begin(), path1.end());  // 变成栈底→栈顶
				}
				else
				{
					// 第二次找到：复制当前栈，找最长公共前缀
					vector<BiTree> path2;
					stack<BiTree> tmp = st;
					while (!tmp.empty())
					{
						path2.push_back(tmp.top());
						tmp.pop();
					}
					reverse(path2.begin(), path2.end());

					int minLen = min(path1.size(), path2.size());
					int i = 0;
					while (i < minLen && path1[i] == path2[i])
					{
						++i;
					}
					return path1[i - 1];    // 最后一个相同的元素
				}
			}

			st.pop();                   // 访问完才弹出
			lastVisited = cur;
			cur = nullptr;
		}
		else
		{
			cur = cur->rchild;          // 转向右子树
		}
	}

	return nullptr;                     // p 或 q 不在树中
}

$7$、已知一棵满二叉树和它的先序序列$pre$，求它的后序序列$post$。

满二叉树除了叶子节点外，其他所有节点都有左右子树且左右子树节点数量相等，因此给定先序序列$pre$，除去$pre[1]$是根节点外，剩下的分别是左右子树的先序序列，且长度各占一半。直接在$pre$数组里用双指针进行处理。

void PreToPost(const vector<int>& pre, int l, int r, vector<int>& post)
{
	if (l > r)
	{
		return;
	}

	int half = (r - l) / 2;                      // 左右子树长度相等
	PreToPost(pre, l + 1, l + half, post);       // 递归处理左子树
	PreToPost(pre, l + half + 1, r, post);       // 递归处理右子树
	post.push_back(pre[l]);                      // 根最后加入后序
}

树、森林

树的存储结构

双亲表示法

使用一组连续的存储空间来存放树中的节点，每个节点除了包含数据域外，还增设一个“伪指针”域，指示其父节点在数组中的下标，根节点在下标$0$处，其双亲域值为$-1$。

存储结构定义如下：

class PTNode
{
public:
	ElemType data;
	int parent;
};

class PTree
{
public:
	vector<PTNode> PT;
	int n;
};

双亲表示法利用了除根结点外所有节点都只有一个父节点的性质，因此查找任意节点的父节点非常高效，但查找某个节点的子节点需要遍历整个数组。

例子：树$A(B,C,D)$（括号里是孩子），其中$B(E,F)$，$D(G)$，按层序把节点放进数组，根节点$A$放在下标$0$，则parent数组为：

下标 $\mathrm{data}$ $\mathrm{parent}$
$0$ $A$ -$1$
$1$ $B$ $0$
$2$ $C$ $0$
$3$ $D$ $0$
$4$ $E$ $1$
$5$ $F$ $1$
$6$ $G$ $3$
  • 找双亲：直接读parent[i]，$O(1)$。
  • 找孩子：最坏要把整个数组扫一遍，$O(n)$。
  • 注意：根节点的parent为$-1$，其余节点的parent是双亲的下标。王道教材里用的是定长数组PTNode nodes[MAX_TREE_SIZE]，上面用vector只是为了方便，考试写数组更稳。

孩子表示法

将每个节点的所有孩子用单链表顺序存储，每个孩子链表的头部被集中存放在一个数组中，每个位置对应一个节点。即树中所有节点组织成一个数组，有子节点的节点就把它所有子节点都串在自己在数组的位置后面。

孩子表示法便于查找节点的孩子，但不方便查找节点的双亲。

存储结构可以这样写：

#define MAX_TREE_SIZE 100

typedef struct CNode {
    int child;              // 孩子在数组中的下标
    struct CNode *next;     // 下一个孩子
} CNode;

typedef struct {
    ElemType data;
    CNode *firstchild;      // 指向第一个孩子
} CTNode;

typedef struct {
    CTNode nodes[MAX_TREE_SIZE];
    int n;
} CTree;

例子：还是那棵树，孩子链表长这样（这里用字母表示孩子，实际存的是数组下标）：

A -> B -> C -> D
B -> E -> F
D -> G
  • 找孩子：顺着firstchild和next走，找某个节点的所有孩子是$O(度数)$，找第一个孩子是$O(1)$。
  • 找双亲：得把所有孩子链表都扫一遍，$O(n)$。
  • 改进：在每个CTNode里再加一个parent域，就是“双亲孩子表示法”，找双亲和孩子都方便，但结构更复杂，王道初试一般不会让你手写这种。

孩子兄弟表示法

也称二叉树表示法，即采用二叉链表作为树的存储结构，从根节点出发，左子树保存节点的第一个子节点，右子树保存树中与该节点处于同一层的节点右侧的兄弟节点。这也是后续树、森林转换成二叉树的原则。

存储结构代码如下：

class CSNode 
{
public:
	ElemType data;		// 数据域
	CSNode* firstchild, * nextbrother;	// 左儿子右兄弟
};
  • 找孩子：firstchild指向第一个孩子，再顺着nextbrother就能找到所有孩子。
  • 找兄弟：nextbrother直接指向下一个兄弟，$O(1)$。
  • 找双亲：没有parent指针，得从根开始遍历，$O(n)$。
  • 重点：孩子兄弟表示法的本质就是“左孩子右兄弟”——左指针管孩子，右指针管兄弟。它也是树、森林转换成二叉树的基础。注意右指针指向的是兄弟，不是右孩子，这是选择题最爱挖的坑。

树、森林和二叉树的转换

树和森林都可以转换成二叉树，转换规则就一句话：左孩子右兄弟。反过来，二叉树也可以还原成树或森林。这部分选择题特别爱考，尤其是转换后的根节点有没有右子树，以及遍历序列的对应关系。

树转换成二叉树

  • 规则：每个节点的左指针指向它的第一个孩子，右指针指向它在树中的下一个兄弟。
  • 三步口诀：加线、抹线、旋转。
    1. 加线：在所有相邻兄弟节点之间加一条线。
    2. 抹线：对每个节点，只保留它与第一个孩子的连线，抹去与其他孩子的连线。
    3. 旋转：以根节点为轴，把整棵树顺时针旋转一定角度，使层次分明。
  • 例子：树$A(B,C,D)$，其中$B(E,F)$，$D(G)$：
        A
      / | \
     B  C  D
    / \    |
   E   F   G

转换后的二叉树：

        A
       /
      B
     / \
    E   C
     \   \
      F   D
         /
        G
  • 对应关系：A.left = B，B.left = E，B.right = C，E.right = F，C.right = D，D.left = G。
  • 重点：树的根节点没有兄弟，所以转换后的二叉树根节点一定没有右子树。如果转换后的根节点有右子树，那它对应的就不是一棵树，而是森林。

森林转换成二叉树

  • 规则：先把森林中的每棵树分别转换成二叉树；然后从第二棵树开始，依次把后一棵树的根节点作为前一棵树根节点的右孩子。
  • 也可以理解成：森林中每棵树的根节点之间本来是兄弟关系，转换时用右指针把它们串起来。
  • 例子：森林里有两棵树，$T_1$是$A(B,C)$，$T_2$是$D(E)$。
    • $T_1$转换成二叉树：A.left = B，B.right = C。
    • $T_2$转换成二叉树：D.left = E。
    • 把$T_2$的根$D$接到$A$的右指针上：A.right = D。
    • 最后得到：A.left = B, A.right = D, B.right = C, D.left = E。
  • 重点：森林转换成的二叉树，根节点一定有右子树（除非森林只有一棵树）。右子树里放的就是森林中剩下的树。

二叉树转换成树或森林

  • 判断规则：看二叉树的根节点有没有右子树。
    • 根节点没有右子树：对应一棵树。
    • 根节点有右子树：对应森林，右子树里的每一段对应森林中的一棵树。
  • 还原方法：把根节点沿右指针方向断开，得到若干棵子二叉树；对每棵子二叉树，把“左孩子”还原成孩子，把“右孩子”还原成兄弟。
  • 例子：上面的二叉树A.left = B, A.right = D, B.right = C, D.left = E，根节点$A$有右子树，所以对应森林：
    • 第一棵树：$A(B,C)$；
    • 第二棵树：$D(E)$。
  • 易错点：不要看到二叉树就以为只能还原成一棵树；只要根节点有右子树，就说明它是森林转换来的。

转换的易错点

  • 孩子兄弟表示法是“左孩子右兄弟”，不是“左孩子右孩子”。
  • 树转换成二叉树，根节点没有右子树；森林转换成二叉树，根节点有右子树。
  • 二叉树转换成树还是森林，只看根节点有没有右子树。
  • 转换前后节点个数不变，只是指针的含义变了。
  • 树的先根遍历对应二叉树的先序遍历，树的后根遍历对应二叉树的中序遍历；森林的先序/中序也分别对应二叉树的先序/中序。这个对应关系下一节详细说。

树和森林的遍历

树的遍历主要有三种方式：先根遍历、后根遍历和层次遍历。注意树没有“中序遍历”这个说法，别和二叉树的中序搞混。

树的遍历

  • 先根遍历：先访问根节点，再依次先根遍历根节点的每一棵子树。
  • 后根遍历：先依次后根遍历根节点的每一棵子树，最后访问根节点。
  • 层次遍历：从根节点开始，从上到下、从左到右逐层访问每个节点。

用孩子兄弟表示法写先根和后根遍历，代码非常短：

void PreOrder(CSTree T) {
    if (T == NULL) return;
    visit(T);
    for (CSNode *p = T->firstchild; p != NULL; p = p->nextbrother)
        PreOrder(p);
}

void PostOrder(CSTree T) {
    if (T == NULL) return;
    for (CSNode *p = T->firstchild; p != NULL; p = p->nextbrother)
        PostOrder(p);
    visit(T);
}

层次遍历就是套一个队列：

#include <queue>
using namespace std;

void LevelOrder(CSTree T) {
    if (T == nullptr) return;
    queue<CSNode*> q;
    q.push(T);
    while (!q.empty()) {
        CSNode *p = q.front();
        q.pop();
        visit(p);
        for (CSNode *c = p->firstchild; c != nullptr; c = c->nextbrother)
            q.push(c);
    }
}

例子：还是树$A(B,C,D)$，其中$B(E,F)$，$D(G)$：

        A
      / | \
     B  C  D
    / \    |
   E   F   G
  • 先根遍历：$A, B, E, F, C, D, G$
  • 后根遍历：$E, F, B, C, G, D, A$
  • 层次遍历：$A, B, C, D, E, F, G$

森林的遍历

  • 先序遍历：依次对森林中的每棵树进行先根遍历。
  • 中序遍历：依次对森林中的每棵树进行后根遍历。
  • 注意：森林的“中序遍历”有的书叫“后序遍历”，王道教材叫中序遍历，本质就是依次对每棵树做后根遍历。

例子：森林里有两棵树，$T_1$是$A(B,C)$，$T_2$是$D(E)$。

  • $T_1$先根：$A, B, C$；后根：$B, C, A$。
  • $T_2$先根：$D, E$；后根：$E, D$。
  • 森林先序遍历：$A, B, C, D, E$。
  • 森林中序遍历：$B, C, A, E, D$。

转换成的二叉树是A.left = B, A.right = D, B.right = C, D.left = E：

  • 二叉树先序遍历：$A, B, C, D, E$。
  • 二叉树中序遍历：$B, C, A, E, D$。

正好和森林的先序、中序一致，这就是对应关系的由来。

遍历的对应关系

树/森林 二叉树
树的先根遍历 先序遍历
树的后根遍历 中序遍历
森林的先序遍历 先序遍历
森林的中序遍历 中序遍历
树的层次遍历 没有直接对应
  • 树的先根遍历 = 对应二叉树的先序遍历。
  • 树的后根遍历 = 对应二叉树的中序遍历。
  • 森林的先序遍历 = 对应二叉树的先序遍历。
  • 森林的中序遍历 = 对应二叉树的中序遍历。
  • 树的层次遍历就是普通的$\mathrm{BFS}$，和转换后的二叉树层次遍历不是一回事，别混。
  • 树没有中序遍历，森林没有后序遍历（王道叫中序），这两个说法不要自己发明。

树和二叉树的应用

树和二叉树的应用里，王道主要讲两个：哈夫曼树和哈夫曼编码、并查集。哈夫曼树是“带权路径长度最短”的二叉树，哈夫曼编码是它的经典应用；并查集则是用双亲表示法存森林，专门处理“合并集合、查询所属集合”的问题。

哈夫曼树和哈夫曼编码

哈夫曼树是树和二叉树应用里最常考的一个，选择题、大题都可能出。它的核心思想很朴素：让权值大的叶子离根近一点，权值小的离根远一点，这样带权路径长度最小。

带权路径长度

  • 节点的路径长度：从根节点到该节点经过的边数。
  • 节点的带权路径长度：该节点的路径长度 × 节点的权值。
  • 树的带权路径长度（$\mathrm{WPL}$）：所有叶节点的带权路径长度之和。
$$ WPL = \sum_{i=1}^{n} w_i l_i $$

其中$w_i$是第$i$个叶节点的权值，$l_i$是它到根节点的路径长度。

  • 哈夫曼树：在含有$n$个带权叶节点的二叉树中，$\mathrm{WPL}$最小的那棵，也叫最优二叉树。
  • 注意：$\mathrm{WPL}$只算叶节点，内部节点不算。这是最容易错的地方。

构造哈夫曼树

  • 贪心策略：
    1. 把$n$个权值看成$n$棵只有根节点的二叉树，组成森林$F$。
    2. 从$F$中选出两棵根节点权值最小的二叉树，作为左右子树构造一棵新二叉树，新根节点的权值为两棵子树根节点权值之和。
    3. 从$F$中删除这两棵树，把新树加入$F$。
    4. 重复$2$、$3$，直到$F$中只剩一棵二叉树。
  • 例子：权值$\lbrace 1, 2, 3, 4 \rbrace$。
    • 选$1, 2$，合并成$3$；此时$F = \lbrace 3, 3, 4 \rbrace$。
    • 选两个$3$，合并成$6$；此时$F = \lbrace 4, 6 \rbrace$。
    • 选$4, 6$，合并成$10$；此时$F = \lbrace 10 \rbrace$。
          10
         /  \
        4    6
            / \
           3   3
              / \
             1   2
  • $\mathrm{WPL}$：$4 \times 1 + 3 \times 2 + 1 \times 3 + 2 \times 3 = 4 + 6 + 3 + 6 = 19$。
  • 注意：权值相同的节点谁左谁右、先合并哪一个，可能得到不同的树形，但$\mathrm{WPL}$都是最小的，而且相等。

哈夫曼树的性质

  • 每个初始节点最终都是叶节点，权值越小，离根越远。
  • 哈夫曼树中没有度为$1$的节点，每个非叶节点都有两个左右孩子。
  • $n$个叶节点的哈夫曼树共有$2n-1$个节点，其中$n-1$个非叶节点。
  • 如果题目给出哈夫曼树的节点总数$N$，可以反推叶节点数：$n = \frac{N+1}{2}$。
  • 哈夫曼树不唯一（左右子树交换、权值相同的节点合并顺序不同都可能得到不同树形），但$\mathrm{WPL}$唯一且最小。
  • 权值越大的叶子一般离根越近，但不要死记“严格按权值排序”，因为树形还受合并顺序影响。

构造哈夫曼树的代码

王道用一维数组存节点：$1 \sim n$存叶节点，$n+1 \sim 2n-1$存新产生的内部节点，parent = 0表示这个节点还没有被合并。下面用vector存节点，用priority_queue（小根堆）每次取两个权值最小的节点。

#include <functional>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct HTNode
{
	int weight;	// 权值
	int parent, lchild, rchild;	// 双亲、左孩子、右孩子下标
};

// 构造哈夫曼树
void CreateHuffmanTree(vector<HTNode>& HT, const vector<int>& w)
{
	// HT 从下标 1 开始存，w 是 0 起的叶节点权值
	int n = static_cast<int>(w.size());
	if (n <= 1)
	{
		return;
	}
	// n 个叶子的哈夫曼树共有 2n-1 个节点
	int m = 2 * n - 1;
	// 0 号下标不用：1~n 放叶子，n+1~m 放内部节点
	HT.assign(m + 1, {0, 0, 0, 0});
	// 初始化叶子节点的权值
	for (int i = 1; i <= n; i++)
	{
		HT[i].weight = w[i - 1];
	}
	// 小根堆里存 (权值, 节点下标)，每次取两个最小的
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	// 先把所有叶子节点入堆
	for (int i = 1; i <= n; i++)
	{
		pq.push({HT[i].weight, i});
	}
	// 不断合并，直到只剩一个根节点
	for (int i = n + 1; i <= m; i++)
	{
		// 取出两个权值最小的节点
		pair<int, int> x = pq.top();
		pq.pop();
		pair<int, int> y = pq.top();
		pq.pop();
		// 两个最小节点的下标
		int s1 = x.second;
		int s2 = y.second;
		// 合并成新节点 i
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
		// 新节点重新入堆
		pq.push({HT[i].weight, i});
	}
}
  • priority_queue里存的是(weight, 下标)，每次弹出两个权值最小的节点，等价于王道Select的功能。
  • 这样建树的时间复杂度是$O(n \log n)$。王道教材给的是数组 + Select的$O(n^2)$写法，考试时两种都能写；如果题目没要求手写堆，用$\mathrm{STL}$更省事。

哈夫曼编码

  • 前缀编码：任何一个字符的编码都不是另一个字符编码的前缀。这样解码时不会出现歧义。
    • 例如0, 10, 110, 111是前缀编码；
    • 0, 01不是前缀编码，因为0是01的前缀。
  • 构造方法：以字符出现的频率（或权值）构造哈夫曼树，左分支记0，右分支记1；从根到叶子的路径就是该字符的哈夫曼编码。
  • 性质：哈夫曼编码一定是前缀编码，而且是最优前缀编码，平均码长最短。
  • 平均码长：
$$ \sum_{i=1}^{n} p_i l_i = \frac{WPL}{\sum_{i=1}^{n} w_i} $$

其中$p_i = \frac{w_i}{\sum w_j}$是第$i$个字符出现的频率。

例子：还是权值$\lbrace 1, 2, 3, 4 \rbrace$，对应字符$A, B, C, D$。按上面的哈夫曼树，左0右1：

字符 权值 编码
$A$ $1$ $110$
$B$ $2$ $111$
$C$ $3$ $10$
$D$ $4$ $0$
  • 平均码长：$\frac{1 \times 3 + 2 \times 3 + 3 \times 2 + 4 \times 1}{1+2+3+4} = \frac{19}{10} = 1.9$。
  • 如果固定长度编码，$4$个字符至少要$2$位，平均$2$位；哈夫曼编码省了$0.1$位。

哈夫曼编码的代码

从叶子往上找根，左孩子记0，右孩子记1。因为是从下往上，先把编码逆序压进string，最后reverse一下。HT用上一段建好的vector<HTNode>。

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

// 生成哈夫曼编码
void CreateHuffmanCode(const vector<HTNode>& HT, vector<string>& HC, int n)
{
	// 0 号不用，HC[1..n] 存放每个叶子的编码
	HC.assign(n + 1, "");
	for (int i = 1; i <= n; i++)
	{
		// 从叶子往根走，先把编码逆序压进 cd
		string cd;
		int c = i;	// 当前节点
		int f = HT[i].parent;	// 当前节点的双亲
		// 沿着双亲一路走到根
		while (f != 0)
		{
			// 左孩子记 0，右孩子记 1
			if (HT[f].lchild == c)
			{
				cd.push_back('0');
			}
			else
			{
				cd.push_back('1');
			}
			c = f;
			f = HT[f].parent;
		}
		// 从叶子到根得到的是逆序，翻转后才是最终编码
		reverse(cd.begin(), cd.end());
		HC[i] = cd;	// 保存第 i 个叶子的编码
	}
}
  • HC[0]空着，HC[1..n]依次对应前$n$个叶节点的哈夫曼编码。

哈夫曼编码的易错点

  • 哈夫曼编码不唯一：左右子树交换0/1，或者权值相同的节点合并顺序不同，都可能得到不同的编码；但平均码长/$\mathrm{WPL}$是最小的。
  • 哈夫曼编码一定是前缀编码，但前缀编码不一定是哈夫曼编码，也不一定最优。
  • 构造哈夫曼树时，每次选的是两个权值最小的节点，不是“一个最小、一个任意”。
  • 如果所有字符频率相同，哈夫曼编码会退化成接近固定长度的编码，压缩效果不明显。
  • 压缩比 = 原编码平均码长 ÷ 哈夫曼编码平均码长。

并查集

并查集是树的一种应用，本质是用双亲表示法存森林。它只支持两种操作：查找某个元素属于哪个集合（$\mathrm{Find}$），合并两个集合（$\mathrm{Union}$）。图论里的$\mathrm{Kruskal}$算法、连通性问题、等价类划分都会用到它。

存储结构

  • 用vector<int> S表示森林，下标就是节点编号，S[i]是节点$i$的双亲下标；根节点的S[i]为$-1$（如果按大小合并，根节点存集合大小的负值）。
  • 每个集合是一棵树，树的根就是集合的代表元。
  • 例子：集合$\lbrace 0,1,2,3 \rbrace$和$\lbrace 4,5 \rbrace$，让$0$当第一个集合的根，$4$当第二个集合的根：
      0          4
    / | \        |
   1  2  3       5

对应的S数组：

下标 $0$ $1$ $2$ $3$ $4$ $5$
$S$ -$1$ $0$ $0$ $0$ -$1$ $4$
  • 注意：根节点的S[i]是负数，非根节点的S[i]是双亲下标。并查集的森林不关心孩子顺序，只关心双亲关系，所以用双亲表示法最合适。

基本操作

  • 初始化：每个元素自成一个集合，S[i] = -1。
#include <vector>
using namespace std;

// 初始化：n 个元素各自成一个集合
void Initial(vector<int>& S, int n)
{
	// 每个元素自成一个集合，根节点存 -1
	S.assign(n, -1);
}
  • 查找：顺着parent一路往上，直到根节点。
// 查找 x 所在集合的根
int Find(const vector<int>& S, int x)
{
	// 非根节点的 S[x] 是双亲下标，根节点的 S[x] 为负数
	while (S[x] >= 0)
	{
		x = S[x];
	}
	return x;	// 根节点下标
}

时间复杂度是$O(h)$，$h$是树高。最坏情况下树退化成一条链，$O(n)$。

  • 合并：把一个根挂到另一个根下面。
// 合并两个集合：把 Root2 挂到 Root1 下面
void Union(vector<int>& S, int Root1, int Root2)
{
	// 同一个集合不用合并
	if (Root1 == Root2)
	{
		return;
	}
	S[Root2] = Root1;	// Root2 的双亲指向 Root1
}

注意：Union的参数必须是两个集合的根，不是任意元素；如果给的是任意元素，要先Find找到根。随意合并可能让树越来越高，最坏$O(n)$，所以需要优化。

优化一：按大小合并

  • 思路：根节点的S[root]存集合大小的负值，合并时让小树挂到大树下，避免树高增长过快。
  • 代码：
#include <utility>
#include <vector>
using namespace std;

// 按集合大小合并：小树挂到大树下面
void UnionBySize(vector<int>& S, int Root1, int Root2)
{
	// 同一个集合不用合并
	if (Root1 == Root2)
	{
		return;
	}
	// 负数，绝对值大的集合更大
	if (S[Root1] > S[Root2])
	{
		swap(Root1, Root2);	// 保证 Root1 是较大的集合
	}
	S[Root1] += S[Root2];	// 更新集合大小（负数相加）
	S[Root2] = Root1;	// Root2 挂到 Root1 下面
}
  • 这样树高不会超过$O(\log n)$，所以Find和Union最坏是$O(\log n)$。
  • 也可以按秩合并（用树高作为合并依据），效果类似；王道主要讲按大小合并。

优化二：路径压缩

  • 思路：在Find的时候，把查找路径上的所有节点直接挂到根节点下，下次再找就快了。
  • 代码：
// 带路径压缩的查找
int FindWithCompression(vector<int>& S, int x)
{
	int root = x;
	// 先一路往上找到根
	while (S[root] >= 0)
	{
		root = S[root];
	}
	// 再把路径上的节点直接挂到根下面
	while (x != root)
	{
		int parent = S[x];	// 先保存原来的双亲，防止断链
		S[x] = root;
		x = parent;
	}
	return root;	// 返回根节点
}
  • 路径压缩不改变集合的划分，只改变树的结构；如果根节点存的是集合大小的负值，压缩后根节点的值不变。
  • 只用一个优化也能改善，但按大小合并 + 路径压缩一起用，单次操作的均摊时间复杂度是$O(\alpha(n))$，其中$\alpha$是反阿克曼函数，增长极慢，可以近似看成$O(1)$。

并查集的应用

  • 判断连通性：对每条边做Union，最后看有几个根；或者判断两个点是否在同一个集合。
  • $\mathrm{Kruskal}$最小生成树：按边权排序，每次选一条边，如果两个端点不在同一集合，就加入$\mathrm{MST}$并Union；否则跳过（会成环）。
  • 等价类划分：把等价的元素合并。
  • 连通块计数：初始化$n$个集合，每合并一次，集合数减一。

常见考法与易错点

  • 给定S[]数组，画出对应的森林；或者给定森林，写出S[]。
  • 给定一系列Union/Find操作，写出最终的S[]或Find的返回值。
  • 根节点的特征是S[i] < 0；非根节点是S[i] >= 0。
  • 集合的个数 = S[]中负数的个数。
  • 如果题目说根节点的parent为$-1$，那就不能用负数大小判断集合大小；如果题目用“负的集合大小”，根节点的值可能是$-2,-3,\dots$。两种约定都行，看题目怎么定义。
  • 并查集不支持删除元素，也不支持把一个集合拆开；它只适合“只合不分”的场景。