树与二叉树

5.1 树的基本概念

树（Tree）是 n（n ≥ 0）个结点的有限集合。n=0 时称为空树。对任意非空树：

有且仅有一个根结点。
除根结点外，其余结点可分为 m（m ≥ 0）个互不相交的子树。

基本术语：

度（degree）：一个结点拥有的子树个数。
叶子（leaf）：度为 0 的结点。
分支结点：度不为 0 的结点。
孩子与双亲：结点的子树的根称为该结点的孩子，该结点是孩子的双亲。
兄弟：同一双亲的孩子之间互称兄弟。
祖先：从根到该结点路径上的所有结点。
子孙：以某结点为根的子树中的所有结点。
层次：根为第 1 层，根的孩子为第 2 层，以此类推。
深度：树中结点的最大层数。
高度：从叶子到根的距离。有时高度和深度混用，但在 408 中深度 = 高度。

树的性质：

树中结点数等于所有结点的度数之和加 1。
度为 m 的树第 i 层最多有 m^(i-1) 个结点（i ≥ 1）。
高度为 h 的 m 叉树最多有 (m^h - 1)/(m - 1) 个结点。
具有 n 个结点的 m 叉树的最小高度为 ⌈log_m(n(m-1)+1)⌉。

💡 记忆技巧：树的定义是递归的——一棵树的子树还是树。这也决定了树的很多算法天然适合用递归实现。

5.2 二叉树

二叉树的定义

二叉树是每个结点至多有两个子树的有序树，左右子树不能颠倒。二叉树的子树有左右之分。

特殊的二叉树：

类型	定义	特点
满二叉树	所有分支结点的度都为 2，且所有叶子在同一层	结点数 2^h - 1
完全二叉树	最后两层可以有叶子，且叶子从左到右排列	可以用数组完美存储
二叉排序树	左子树所有结点 < 根 < 右子树所有结点	BST，中序有序
平衡二叉树	左右子树高度差不超过 1	AVL，查找效率高

二叉树的重要性质

叶子结点数 = 度为 2 的结点数 + 1：n₀ = n₂ + 1。
二叉树的第 i 层最多有 2^(i-1) 个结点（i ≥ 1）。
深度为 h 的二叉树最多有 2^h - 1 个结点。
具有 n 个结点的完全二叉树的深度 ⌊log₂n⌋ + 1。
完全二叉树的顺序编号：结点 i 的双亲为 ⌊i/2⌋，左孩子为 2i，右孩子为 2i+1（从 1 开始编号）。

二叉树的存储结构

顺序存储：用一维数组，适合完全二叉树。结点 i 存放在下标 i 处。 链式存储：每个结点包含数据域、左孩子指针、右孩子指针（有时还有双亲指针）。

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

n 个结点的二叉树有 2n 个指针域，其中 n+1 个是空指针（可用于构建线索二叉树）。

5.3 二叉树的遍历

递归遍历

遍历方式	访问顺序	递归规律
前序遍历	根 → 左 → 右	根左右
中序遍历	左 → 根 → 右	左根右
后序遍历	左 → 右 → 根	左右根
层序遍历	从上到下、从左到右	使用队列

前序遍历：

void PreOrder(BiTree T) {
    if (T) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

中序遍历：

void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

后序遍历：

void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

遍历示例：

         A
       /   \
      B     C
     / \   / \
    D   E F   G

前序：A B D E C F G
中序：D B E A F C G
后序：D E B F G C A
层序：A B C D E F G

非递归遍历（借助栈）

非递归中序遍历：

1. 从根结点开始，沿左子树不断入栈，直到最左下角。
2. 弹出栈顶结点并访问。
3. 对其右子树重复步骤1。
4. 重复直到栈空且当前指针为空。

void InOrderNonRec(BiTree T) {
    Stack S; InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}

非递归前序遍历：

void PreOrderNonRec(BiTree T) {
    Stack S; InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            visit(p);
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

非递归后序遍历（最复杂）：需要两个栈或一个栈加一个标志变量，因为根结点最后访问。先访问左子树再右子树最后根。

层序遍历（借助队列）

void LevelOrder(BiTree T) {
    Queue Q; InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild) EnQueue(Q, p->lchild);
        if (p->rchild) EnQueue(Q, p->rchild);
    }
}

层序遍历的时间复杂度 O(n)，空间复杂度 O(n)。

遍历的应用：

前序遍历：表达式树的前缀表示（波兰式）。
中序遍历：表达式树的中缀表示，BST 排序输出。
后序遍历：表达式树的后缀表示（逆波兰式），求树的高度。
层序遍历：求树的宽度（最宽层结点数）。

由遍历序列确定二叉树

已知序列组合	是否唯一确定	方法
前序 + 中序	是	前序第一个为根，在中序中划分左右子树
后序 + 中序	是	后序最后一个为根，在中序中划分左右子树
层序 + 中序	是	层序第一个为根，在中序中划分左右子树
前序 + 后序	否	无法区分左右子树边界

解题方法（以前序+中序为例）：

前序序列的第一个元素是根结点。
在中序序列中找到该根结点，左边为左子树中序序列，右边为右子树中序序列。
前序序列中，根结点之后与左子树中序序列等长的部分是左子树前序序列，剩余是右子树前序序列。
对左右子树递归执行上述步骤。

📌 408考点提示：由遍历序列确定二叉树是经典题型，几乎每年都有涉及。需要能根据任意两种遍历序列（前+中或后+中）还原出二叉树，并写出另一种遍历序列。

5.4 线索二叉树

利用二叉树中的 n+1 个空指针，将其指向前驱或后继（"线索化"）。

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0 表示指针指向孩子，1 表示指向前驱/后继
} ThreadNode, *ThreadTree;

中序线索化的过程：在中序遍历过程中，设置 pre 指针指向当前访问结点的前驱结点，修改线索。

void InThread(ThreadTree &p, ThreadTree &pre) {
    if (p) {
        InThread(p->lchild, pre);
        if (p->lchild == NULL) { p->lchild = pre; p->ltag = 1; }
        if (pre && pre->rchild == NULL) { pre->rchild = p; pre->rtag = 1; }
        pre = p;
        InThread(p->rchild, pre);
    }
}

线索二叉树可以方便地找到前驱和后继，遍历无需递归或栈。

5.5 树和森林

树的存储结构

双亲表示法：用一维数组，每个结点存放数据和双亲的下标。

#define MAX_TREE_SIZE 100
typedef struct {
    ElemType data;
    int parent;
} PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
} PTree;

孩子表示法：每个结点用链表连接其所有孩子。

孩子兄弟表示法（二叉链表表示法）：最常用，每个结点存放第一个孩子和右兄弟指针。

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

树、森林与二叉树的转换

树 → 二叉树：使用孩子兄弟表示法，firstchild→lchild，nextsibling→rchild。
森林 → 二叉树：每棵树转为二叉树后，根结点依次作为右子树连接。

树和森林的遍历

遍历方式	树	森林
先根遍历	访问根 → 遍历子树	访问第一棵树的根 → 遍历其子树 → 遍历其余树
后根遍历	遍历子树 → 访问根	遍历第一棵树的子树 → 访问根 → 遍历其余树
层序遍历	从上到下、从左到右	从上到下、从左到右

树的后根遍历对应二叉树的中序遍历，树的先根遍历对应二叉树的前序遍历。

5.6 哈夫曼树与哈夫曼编码（重点）

哈夫曼树

定义：带权路径长度（WPL）最小的二叉树称为哈夫曼树（最优二叉树）。

带权路径长度：WPL = Σ(wᵢ × lᵢ)，其中 wᵢ 是第 i 个叶子结点的权值，lᵢ 是路径长度（边数）。

构造步骤：

将 n 个权值作为 n 棵只有根结点的二叉树组成森林 F。
在 F 中选取权值最小的两棵树作为左右子树构造新二叉树，新根权值为二者之和。
从 F 中删除这两棵，加入新树。
重复步骤 2、3，直到 F 只剩一棵树。

性质：

哈夫曼树没有度为 1 的结点。
n 个叶子结点的哈夫曼树共有 2n-1 个结点。
左右子树可以交换，所以哈夫曼树不唯一，但 WPL 唯一。

哈夫曼编码

用哈夫曼树构造前缀编码（任一编码不是另一编码的前缀）。
左分支标 0，右分支标 1（或相反）。
权值大的字符编码短，权值小的编码长，实现数据压缩。

💡 记忆技巧："小权值深，大权值浅"——哈夫曼编码的核心思想就是给高频字符短编码，低频字符长编码。

5.7 并查集

并查集（Disjoint Set Union, DSU）是一种树型数据结构，用于处理不相交集合的合并和查询。

基本操作：

Initial(S)：将每个元素初始化为一个独立集合。
Find(S, x)：查找元素 x 所属的集合（返回根结点）。
Union(S, x, y)：合并元素 x 和 y 所在的集合。

路径压缩：在 Find 操作中，将搜索路径上的结点都直接指向根结点，提升后续查找效率。

按秩合并：在 Union 操作中，将深度较小的树合并到深度较大的树上。

5.8 题型示例

例题1：已知一棵二叉树的前序遍历序列为 A B D G C E F H，中序遍历序列为 D G B A E C H F，求二叉树和后序遍历。

解：

前序第一个是根 A。
中序中 A 左边是左子树 D G B，右边是右子树 E C H F。
左子树前序 B D G，中序 D G B → B 是左子根，D 和 G 在 B 左边 → G 是 D 的右孩子。
右子树前序 C E F H，中序 E C H F → C 是右子根，E 是左孩子，H F 在右边。
H F 前序 F H，中序 H F → F 是 C 的右孩子，H 是 F 的左孩子。

后序遍历：G D B E H F C A

例题2：权值集合 {7, 5, 2, 4}，构造哈夫曼树并计算 WPL。

解：

取最小 2, 4 → 新 6。集合：{7, 5, 6}
取最小 5, 6 → 新 11。集合：{7, 11}
取最小 7, 11 → 新 18。集合：{18}

WPL = 2×3 + 4×3 + 5×2 + 7×1 = 6 + 12 + 10 + 7 = 35

例题3：一棵完全二叉树有 100 个结点，求叶子结点数。

解：完全二叉树性质：n₀ = n₂ + 1，n = n₀ + n₁ + n₂。完全二叉树中 n₁ 要么为 0 要么为 1。 n = n₂ + (n₂ + 1) + n₁ = 2n₂ + 1 + n₁ = 100 2n₂ = 99 - n₁，n₂ = (99 - n₁)/2 n₁ 只能为 1（使 n₂ 为整数），n₂ = 49，n₀ = 50。所以叶子结点数为 50。

本章总结

树是数据结构中最重要的非线性结构之一。二叉树遍历、哈夫曼树是 408 的必考内容。理解树的递归特性，熟练掌握递归遍历和非递归遍历的转换，以及由遍历序列重建二叉树的方法。哈夫曼编码的构造过程和 WPL 计算是计算题的主要题型。

树与二叉树