数据结构与算法实验

二叉树判别 & 哈夫曼编码/解码

苗夕远 · 数据结构与算法 · 第3次实验

一、实验概述

本实验包含两个独立任务，均由单一源文件 main.cpp 实现：

任务内容核心算法
任务1判别两棵二叉树是否相等递归比较二叉链表结构
任务2哈夫曼编码/解码贪心建树 + 回溯编码 + 遍历解码

二、开发环境

项目说明
语言标准C++ 98/03（兼容所有主流编译器）
编译器g++ (MinGW-w64) 4.9+ / Dev-C++ 自带 MinGW / VS 均可
编译命令g++ -o main.exe main.cpp
文件结构单文件项目，无外部依赖
注意：代码已对 Dev-C++ 做兼容处理——全部使用 C++98 语法，不依赖 -std=c++11。

三、任务1：判别两棵二叉树是否相等

3.1 数据结构与算法

采用二叉链表存储二叉树：

struct BiTNode {
    char data;              // 节点数据
    BiTNode *lchild, *rchild; // 左右孩子指针
};
typedef BiTNode* BiTree;

3.2 建树方法

以先序遍历 + # 表示空节点的字符串递归创建二叉树。

示例：字符串 "AB##C##" 对应的树结构：

        A
      /   \
     B     C
    / \   / \
   #   # #   #

递归建树逻辑：

  1. 读取当前字符，若为 # 或越界 → 设指针为 NULL，返回
  2. 否则创建新节点，存入字符
  3. 递归创建左子树
  4. 递归创建右子树

3.3 比较算法 — CmpTree

int CmpTree(BiTree T1, BiTree T2)
{
    if (T1 == NULL && T2 == NULL)  return 1;    // 两树皆空 → 相等
    if (T1 == NULL || T2 == NULL)  return 0;    // 一空一不空 → 不等
    if (T1->data != T2->data)     return 0;    // 根节点值不同 → 不等
    int left  = CmpTree(T1->lchild, T2->lchild);  // 递归左子树
    int right = CmpTree(T1->rchild, T2->rchild);  // 递归右子树
    return left && right;                          // 左右均等才全等
}

复杂度：O(min(N₁, N₂))，N 为节点数。采用先根遍历顺序递归。

3.4 测试用例

#树1树2预期
1AB##C##AB##C##相等
2AB##C##AD##C##不相等（数据不同）
3AB##C##ABC###不相等（结构不同）

四、任务2：哈夫曼编码/解码

4.1 数据结构与算法

使用顺序存储结构（一维数组）存储哈夫曼树节点：

struct HTNode {
    int weight;    // 权值（频率）
    int parent;    // 父节点下标（0 表示无父节点/根）
    int lchild;    // 左孩子下标（0 表示无孩子/叶子）
    int rchild;    // 右孩子下标
    char ch;       // 叶子节点对应的字符
};

数组 HT[1..2n-1]，下标 从 1 开始（0 号位置手动清零作哨兵）：

  • HT[1..n] — 叶子节点（n 为字符种类数）
  • HT[n+1..2n-1] — 内部节点
  • HT[2n-1] — 根节点

4.2 算法流程

步骤一：统计频率

遍历输入串，用 freq[26] 数组统计 a~z 各字符出现次数，同时转小写处理大写输入。

步骤二：Select — 选取两个最小权值

void Select(HTNode *HT, int sum, int &s1, int &s2)
{
    // 第一轮：找 parent==0 中 weight 最小的节点下标 → s1
    // 将 HT[s1].weight 临时设为 INT_MAX 避免重复选中
    // 第二轮：找 parent==0 中 weight 最小的节点下标 → s2
    // 恢复 HT[s1].weight
}

贪心策略：每次从未选过的节点中选出两个权值最小的，合并为新内部节点。

步骤三：构建哈夫曼树

for (i = n+1; i <= 2n-1; i++) {
    Select(HT, i-1, s1, s2);             // 选两个最小
    HT[i].weight = HT[s1].weight + HT[s2].weight;
    HT[i].lchild = s1;  HT[i].rchild = s2;
    HT[s1].parent = i;  HT[s2].parent = i;
}

步骤四：生成编码（回溯法）

对每个叶子节点，从该节点向上回溯到根：

  • 若当前节点是父节点的左孩子 → 编码前加 '0'
  • 若当前节点是父节点的右孩子 → 编码前加 '1'
  • 到达根时反转路径即得编码
// 示例：叶子节点 i=3，路径 3→5→8(root)
// 3 是 5 的左孩子 → "0"
// 5 是 8 的右孩子 → "10"
// 编码 = "10"

步骤五：解码（遍历法）

从根节点出发，逐位读取编码串：

  • 读 '0' → 走向左孩子
  • 读 '1' → 走向右孩子
  • 到达叶子节点（lchild==0 && rchild==0）→ 输出该字符，回到根
cur = root;                    // 从根开始
for each bit in encoded:
    cur = (bit=='0') ? HT[cur].lchild : HT[cur].rchild;
    if (cur is leaf):
        output HT[cur].ch;    // 输出字符
        cur = root;           // 回到根

特殊情况：n=1（单字符）

当输入串只有一个字符时（如 "aaaa"），n=1，m=1。此时：

  • 不构建内部节点，唯一节点即根也是叶子
  • 编码固定为 "0"
  • 解码直接将每个 '0' 替换为该字符

4.3 输出格式规范

每组数据输出 2n+3 行（n = 字符种类数）：

行号内容示例
1字符频度（ASCII升序，空格分隔）a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1
2 ~ 2n哈夫曼树节点终态（共 2n-1 行）2 12 0 0（weight parent lchild rchild）
2n+1哈夫曼编码表（ASCII升序）a:110 i:111 m:000 n:001 ...
2n+2编码后的二进制串000111110010100111101011110001
2n+3解码后的原字符串（小写）miaoxiyuan

4.4 完整示例

输入 "MiaoXiyuan" 的输出：

a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1         ← 频度 (n=8)
2 12 0 0                                   ┐
2 12 0 0                                   │
1 9 0 0                                    │
1 9 0 0                                    │
1 10 0 0                                   ├ 树节点终态
1 10 0 0                                   │ (共15行=2n-1)
1 11 0 0                                   │
1 11 0 0                                   │
2 13 3 4                                   │
2 13 5 6                                   │
2 14 7 8                                   │
4 14 1 2                                   │
4 15 9 10                                  │
6 15 11 12                                 ┘
10 0 13 14
a:110 i:111 m:000 n:001 o:010 u:011 x:100 y:101  ← 编码表
000111110010100111101011110001                    ← 编码串
miaoxiyuan                                       ← 解码串

五、使用方法

5.1 编译

Dev-C++：直接打开 main.cpp，点击"编译运行"（F11）。

命令行方式：

# 设置 g++ 路径（如 Dev-C++ 自带 MinGW）
set PATH=%PATH%;C:\Program Files (x86)\Dev-Cpp\MinGW64\bin

# 编译
g++ -o main.exe main.cpp

5.2 运行

方式一：直接运行（交互输入）

.\main.exe
# 任务1 结果自动输出
# 任务2：逐行输入字符串，输入 "0" 结束

方式二：管道输入（批量测试）

echo MiaoXiyuan > input.txt
echo 0 >> input.txt
main.exe < input.txt

5.3 输入规范

  • 任务1 无需输入，测试结果自动输出
  • 任务2 每行一个字符串，仅考虑 a~z（大写自动转小写）
  • 输入 "0" 结束程序
  • 允许多组数据连续输入，每组独立输出

六、程序结构

main.cpp
│
├── 任务1：二叉树判别
│   ├── struct BiTNode          — 二叉链表节点定义
│   ├── CreateBiTree()          — 先序建树（递归）
│   ├── CmpTree()               — 递归比较两树相等
│   ├── DestroyBiTree()         — 递归销毁、释放内存
│   └── runTask1()              — 驱动：含3组测试用例
│
├── 任务2：哈夫曼编码
│   ├── struct HTNode           — 哈夫曼树节点（顺序存储）
│   ├── Select()                — 贪心选取两个最小权值
│   ├── processHuffman()        — 核心流程：
│   │   ├── 统计频率
│   │   ├── 构建哈夫曼树（n→2n-1）
│   │   ├── 生成编码表（回溯）
│   │   ├── 编码字符串
│   │   └── 解码字符串
│   └── runTask2()              — 多行输入循环
│
└── int main()                  — 入口，依次执行任务1→任务2

函数调用关系图

main()
├── runTask1()
│   ├── CreateBiTree()          （建树1）
│   ├── CreateBiTree()          （建树2）
│   ├── CmpTree()               （比较）
│   │   ├── CmpTree()           （左子树递归）
│   │   └── CmpTree()           （右子树递归）
│   └── DestroyBiTree()         （销毁 ×2）
│
└── runTask2()
    └── while(getline)
        └── processHuffman(str)
            ├── 频率统计
            ├── Select()        （建树时选最小两个，调用 n-1 次）
            ├── 回溯编码
            └── 遍历解码

七、知识点详解

7.1 二叉树的存储结构 — 二叉链表

核心思想：每个节点包含三个域——数据域（data）、左指针域（lchild）和右指针域（rchild）。这种表示法也称为"左孩子右兄弟"表示法的简化版本（只保留孩子，不保留兄弟），是二叉树最常用的链式存储方式。

struct BiTNode {
    char data;                   // 数据域
    BiTNode *lchild, *rchild;    // 指针域：分别指向左子树和右子树
    // 当没有子树时，指针为 NULL
};
对比项二叉链表三叉链表顺序存储（数组）
节点结构data + lchild + rchilddata + lchild + rchild + parent仅 data，用下标关系隐含父子
空间效率2个指针/节点3个指针/节点0个指针，但可能浪费
查找父节点需从根遍历O(1)O(1)（i/2）
适用场景通用二叉树需频繁找父节点完全/满二叉树

在本实验中的应用：任务1 的 BiTNode 使用二叉链表存储任意形态的二叉树。由于需要频繁递归遍历左右子树且不需要查找父节点，二叉链表是最佳选择。创建和销毁均通过递归实现，天然匹配树的分形结构。

7.2 递归先序遍历与建树

先序遍历序列的定义：根节点 → 左子树（先序）→ 右子树（先序）。这是三种深度优先遍历（先序/中序/后序）中最直观的一种，也是本实验建树所选用的方式。

"#" 占位符的作用：单独的先序序列无法唯一确定一棵二叉树（例如 "AB" 可能是 A->left=B 也可能是 A->right=B）。引入 # 表示空节点后，序列就包含了完整的结构信息，可以唯一还原整棵树。这种表示法也称为"扩展先序遍历"。

递归建树的过程（以 "AB##C##" 为例）：

步骤读取字符操作递归深度
1A创建根节点 A，递归建左子树0→1
2B创建节点 B，递归建左子树1→2
3#B的左孩子为NULL，返回，递归建B的右子树2
4#B的右孩子为NULL，返回，回到A层2→1
5C创建节点 C 作为A的右孩子，递归建左子树1→2
6#C的左孩子为NULL，返回2
7#C的右孩子为NULL，返回，建树完成2→1→0

时间复杂度：O(L)，L 为序列长度（每个字符读一次，每个节点创建一次）。空间复杂度：O(H)，H 为树高（递归调用栈深度）。

7.3 递归遍历思想在 CmpTree 中的应用

CmpTree 本质上是一种"同步先序遍历"：同时遍历两棵树，在每一个对应位置比较节点。

递归三要素分析：

  1. 终止条件（Base Case）：
    • 两节点都为空 → 该子树相等（return 1）
    • 仅一个为空 → 结构不同，不等（return 0）
    • 节点值不同 → 数据不同，不等（return 0）
  2. 递归关系（Recurrence）：两棵树相等 ⟺ 根相等 ∧ 左子树相等 ∧ 右子树相等
  3. 返回值传递：自底向上传播——叶子层的比较结果逐层向上做 AND 运算，最终汇聚到根

递归树示意（测试1：两棵相同树 "AB##C##" vs "AB##C##"）：

CmpTree(A1,A2)
├── data 'A'=='A' ✓
├── CmpTree(B1,B2)
│   ├── data 'B'=='B' ✓
│   ├── CmpTree(NULL,NULL) → 1
│   └── CmpTree(NULL,NULL) → 1
│   └── return 1 && 1 = 1
├── CmpTree(C1,C2)
│   ├── data 'C'=='C' ✓
│   ├── CmpTree(NULL,NULL) → 1
│   └── CmpTree(NULL,NULL) → 1
│   └── return 1 && 1 = 1
└── return 1 && 1 = 1  → 两树相等

最重要的一点：此递归本质上是分治法（Divide and Conquer）——将"整棵树是否相等"分解为"左子树是否相等"和"右子树是否相等"两个子问题，解决后合并结果。

7.4 二叉树的顺序存储结构

基本原理：将二叉树的节点按层序编号，存入数组。对于编号为 k 的节点：

  • 父节点：第 ⌊k/2⌋ 个位置
  • 左孩子：第 2k 个位置
  • 右孩子：第 2k+1 个位置

与链式存储的对比：

特性顺序存储链式存储
查找孩子O(1)（直接计算下标）O(1)（指针解引用）
查找父节点O(1)（下标÷2）O(N)（需从根遍历）
空间利用率仅对完全二叉树高效，否则大量浪费100%，无浪费
插入/删除需移动大量元素修改指针即可

在本实验中的应用：任务2 的哈夫曼树使用变体的顺序存储——通过显式的 parent/lchild/rchild 域存储下标而非依赖隐含公式 2k 和 2k+1。这是因为哈夫曼树不是完全二叉树，不能用公式固定关系。这种方式结合了顺序存储（数组随机访问）和链式存储（灵活连接）的优点：

  • parent = 0 表示该节点无父节点（即根）
  • lchild = 0 / rchild = 0 表示无左/右孩子（即叶子）
  • 数组下标本身即是"节点编号"，通过编号引用节点，避免了指针操作

7.5 哈夫曼树的构造算法

哈夫曼树（最优二叉树）是一类带权路径长度（WPL）最短的二叉树，常用于数据压缩。

带权路径长度（WPL）公式：

WPL = Σ (叶子节点的权值 × 叶子到根的路径长度)

构造算法（5步法）：

  1. 初始化：将 n 个字符及其权值构造成 n 棵单节点二叉树，形成森林 F
  2. 选取：从 F 中选出两棵根节点权值最小的树（Select 操作）
  3. 合并：以这两棵树作为左右子树，构造一棵新树，新树根的权值为两子树权值之和
  4. 放回：将新树放回森林 F
  5. 重复：重复步骤 2-4，直到 F 中只剩一棵树，即为哈夫曼树

以输入 "abc" 为例的完整构造过程（n=3, m=5）：

轮次当前森林中的树（按权值）选出的最小两个合并后
初始{a:1}, {b:1}, {c:1}——
第1轮 (i=4){a:1}, {b:1}, {c:1}s1=a(1), s2=b(1)新建 T₄ 权值=2，孩子={a,b}。森林：{c:1}, {T₄:2}
第2轮 (i=5){c:1}, {T₄:2}s1=c(1), s2=T₄(2)新建 T₅ 权值=3，孩子={c,T₄}。森林：{T₅:3}（唯一，即根）

最终得到的哈夫曼树：

         T₅(3)
        /     \
     c(1)     T₄(2)
             /     \
          a(1)    b(1)

算法复杂度：每次 Select 需扫描 O(n) 个节点，共进行 n-1 次合并，总时间复杂度 O(n²)。若使用小根堆（优先队列）优化 Select，可降至 O(n log n)。

空间复杂度：数组大小为 2n，即 O(n)。

7.6 贪心策略

贪心策略定义：在每一步选择中都采取当前状态下最优的选择（局部最优），期望通过一系列局部最优选择达到全局最优。

在哈夫曼编码中的应用：每次建树时，总是选择当前权值最小的两个节点合并。直觉上：权值大的字符应当离根更近（编码更短），节省总比特数。而每次让两个最小的先合并，恰好使得它们占据较深的位置（编码更长），而权值大的字符在后续合并中保持"轻量"，最终被放在靠近根的位置。

贪心正确性（直观理解）：假设存在一棵最优二叉树 T。设 a,b 是权值最小的两个叶子，则一定存在一棵最优树使得 a,b 是兄弟且深度最大。因为如果把最深位置的字符与 a 或 b 交换，WPL 不会增加（只会可能减少或不变）。这是哈夫曼编码最优性的数学基础。

贪心 vs 动态规划对比：

特性贪心动态规划
选择策略每步选局部最优考虑所有可能，选择全局最优
时间复杂度通常更低通常更高
适用范围需满足贪心选择性质需满足最优子结构
哈夫曼编码✓ 贪心选择性质成立也可解，但更复杂

7.7 回溯法生成哈夫曼编码

回溯法（Backtracking）定义：从目标状态出发，沿路径反向回到初始状态，记录沿途的决策。

在哈夫曼编码中的应用（自底向上）：

  1. 从叶子节点出发，沿 parent 指针向上回溯到根
  2. 每步判断当前节点是父节点的左孩子还是右孩子：
    • 左孩子 → 该步产生 '0'
    • 右孩子 → 该步产生 '1'
  3. 回溯到根时，得到的 '0'/'1' 序列为反向编码，反转后即为最终编码

以字符 'n' 在 "MiaoXiyuan" 中的编码生成为例：

节点 n 位于 HT[4]（叶子），回溯过程：
HT[4].parent = 9 → HT[4] 是 HT[9] 的右孩子 → 产生 '1'
HT[9].parent = 13 → HT[9] 是 HT[13] 的左孩子 → 产生 '0'
HT[13].parent = 15 → HT[13] 是 HT[15] 的左孩子 → 产生 '0'
到达根（parent=0），停止
反向序列：'1' → '0' → '0'
反转后：'0' → '0' → '1' = "001"  ← 最终编码

回溯法的优势在于不需要从根出发维护当前路径，每个叶子独立编码，逻辑清晰。

7.8 哈夫曼编码的前缀性

前缀码定义：在一个编码集合中，任何一个字符的编码都不是另一个字符编码的前缀（即开头部分）。

哈夫曼编码天然是前缀码的原因：

  • 在哈夫曼树中，所有字符都存储在叶子节点上
  • 内部节点不存储任何字符，只作为路径分支点
  • 因此从根到任何一个叶子节点的路径，不可能恰好"经过"另一个叶子
  • 换言之，没有一条根-to-叶路径是另一条路径的前缀

前缀性的关键意义——保证解码唯一性：

解码时，从根出发按位 0/1 向下走，到达叶子时输出字符并回到根。由于前缀性，到达某个叶子时不可能还在另一个字符编码的"半路"上，因此解码结果是唯一的。

// 以 "abc" 的编码串 "10110" 解码为例：
// 编码表：a=10, b=11, c=0

从根 T₅ 开始:
  '1' → 去 T₄
  '0' → 到达叶子 a，输出 'a'，回到根 T₅ ✓
       （此时不可能还在某个编码的半路，因为 a 的编码不是任何其他编码的前缀）

从根 T₅ 继续:
  '1' → 去 T₄
  '1' → 到达叶子 b，输出 'b'，回到根 T₅ ✓

从根 T₅ 继续:
  '0' → 到达叶子 c，输出 'c'，回到根 T₅ ✓

解码结果: "abc" ✓

非前缀码的反例：如果 a 的编码是 "1"，b 的编码是 "10"，那么读到 "10" 时无法判断应该解码为 "b" 还是先解码 "a"（因为 '1' 就返回 a 了）。哈夫曼编码通过"所有字符在叶子"的设计天然避免了这一问题。

7.9 内存管理 — 树的销毁

DestroyBiTree 采用后序遍历销毁：先递归销毁左子树，再递归销毁右子树，最后释放根节点。这是必要的——如果在释放根节点之前不先释放子树，将导致内存泄漏（子树节点无法再被访问）。

void DestroyBiTree(BiTree &T) {
    if (T == NULL) return;          // 空树无需销毁
    DestroyBiTree(T->lchild);        // 先销毁左子树（递归）
    DestroyBiTree(T->rchild);        // 再销毁右子树（递归）
    delete T;                        // 最后销毁根节点
    T = NULL;                        // 避免野指针
}

任务2 的哈夫曼树使用 delete[] HT 一次性释放整个数组，因为所有节点在连续内存中，无需逐个释放。

八、示例实验详解

8.1 任务1：二叉树判别 — 三个测试用例详解

测试1：两棵完全相同的树

输入：树1 = "AB##C##"，树2 = "AB##C##"

    树1:                    树2:
       A                       A
      / \                     / \
     B   C                   B   C
    (叶子) (叶子)           (叶子) (叶子)

比较过程（CmpTree 递归展开）：

  1. CmpTree(A₁, A₂)：data 'A'=='A' ✓，递归比较左右子树
  2. CmpTree(B₁, B₂)：data 'B'=='B' ✓，左右子树均为 NULL，返回 1
  3. CmpTree(C₁, C₂)：data 'C'=='C' ✓，左右子树均为 NULL，返回 1
  4. 根层 left=1, right=1，return 1 && 1 = 1 → 相等

程序输出：测试1: 先序序列 "AB##C##" 和 "AB##C##" -> 相等 ✓正确

测试2：数据不同的两棵树

输入：树1 = "AB##C##"，树2 = "AD##C##"

    树1:                    树2:
       A                       A
      / \                     / \
     B   C                   D   C
    (叶子) (叶子)           (叶子) (叶子)

比较过程：

  1. CmpTree(A₁, A₂)：data 'A'=='A' ✓，递归比较左右子树
  2. CmpTree(B₁, D₁)："B" ≠ "D"，直接返回 0！
  3. 根层 left=0，return 0 → 不相等（数据不同）

关键观察：一旦发现节点值不同，立即返回 0 并逐层向上传递，不再继续比较——这是短路求值在递归中的应用。

程序输出：测试2: 先序序列 "AB##C##" 和 "AD##C##" -> 不相等 ✓正确

测试3：结构不同的两棵树

输入：树1 = "AB##C##"，树2 = "ABC###"

先分析两棵树的形状：

字符串先序还原过程树结构
树1AB##C##A→B(左)→NULL(左B)→NULL(右B)→C(右A)→NULL(左C)→NULL(右C)A 有左右孩子 B 和 C，B、C 是叶子
树2ABC###A→B(左)→C(左B)→NULL(左C)→NULL(右C)→NULL(右B)→NULL(右A)A→B→C 一路向左的斜树
    树1:                    树2:
       A                       A
      / \                     /
     B   C                   B
    (叶子) (叶子)           /
                           C
                          (叶子)

比较过程：

  1. CmpTree(A₁, A₂)：data 'A'=='A' ✓，递归比较左右子树
  2. CmpTree(B₁, B₂)：data 'B'=='B' ✓，递归比较B的子树的左右孩子
    • CmpTree(NULL(B₁左), C₁)：T₁==NULL 而 T₂!=NULL → 返回 0！
  3. B层 left=0，return 0 → 逐层传递到根 → 不相等（结构不同）

关键观察：树1中B是叶子（两个孩子=NULL），而树2中B有左孩子C。当一方为NULL另一方不为NULL时，立即判定结构不同。

程序输出：测试3: 先序序列 "AB##C##" 和 "ABC###" -> 不相等 ✓正确

8.2 任务2：哈夫曼编码/解码 — 完整示例

示例A：简单输入 "abc"（三个不同字符，各出现一次）

输入："abc" → n=3（字符种类数）

步骤1：统计字符频率

字符abc
频率111

输出第1行：a:1 b:1 c:1

步骤2：初始化叶子节点（HT[1..3]）

下标weightparentlchildrchildch说明
11000a叶子节点
21000b叶子节点
31000c叶子节点

步骤3：构建哈夫曼树（共 n-1 = 2 轮合并）

第1轮（生成内部节点 i=4）：

  • Select(HT, 3, s1, s2)：在 HT[1..3]（parent==0）中找权值最小的两个
  • min1=1（下标1→a），min2=1（下标2→b），选 s1=1, s2=2
  • 创建 HT[4]：weight=1+1=2，lchild=1(a)，rchild=2(b)
  • HT[1].parent=4，HT[2].parent=4（a,b 不再可选）

此时可选节点：HT[3](c,weight=1), HT[4](内部,weight=2)

第2轮（生成根节点 i=5）：

  • Select(HT, 4, s1, s2)：parent==0 的有 HT[3](1) 和 HT[4](2)
  • min1=1（下标3→c），min2=2（下标4），选 s1=3, s2=4
  • 创建 HT[5]：weight=1+2=3，lchild=3(c)，rchild=4(内部)
  • HT[3].parent=5，HT[4].parent=5
  • HT[5].parent=0 → 这是根节点！

哈夫曼树可视化：

           [5] w=3 (根)
           /      \
       [3]c(1)   [4] w=2
                /      \
            [1]a(1)  [2]b(1)

步骤4：输出树节点终态（HT[1..5]，共 2n-1=5 行，即第2~6行）

下标  weight parent lchild rchild   ← 格式
 1      1      4      0      0        a: 叶子，权1，父节点=4
 2      1      4      0      0        b: 叶子，权1，父节点=4
 3      1      5      0      0        c: 叶子，权1，父节点=5
 4      2      5      1      2        内部节点，权2，孩子=a(1)和b(2)
 5      3      0      3      4        根节点，权3，孩子=c(3)和内部(4)

步骤5：生成编码表（回溯法，第7行输出）

字符叶子下标回溯路径编码验证
a11→4(左/0)→5(右/1)→根
反转：1→0 = "10"		102 bits
b22→4(右/1)→5(右/1)→根
反转：1→1 = "11"		112 bits
c33→5(左/0)→根
反转：0 = "0"		01 bit

输出：a:10 b:11 c:0

步骤6：编码原始字符串（第8行输出）

"abc" → a(10) + b(11) + c(0) = 10110

步骤7：解码验证（第9行输出）

解码 "10110"：
'1'→[4] '0'→[1]=a (输出a,回根)
'1'→[4] '1'→[2]=b (输出b,回根)
'0'→[3]=c          (输出c,回根)
结果: "abc" ✓

完整输出（2n+3 = 2×3+3 = 9行）：

a:1 b:1 c:1           ← 第1行：字符频度
1 4 0 0              ← 第2行：HT[1] (a)
1 4 0 0              ← 第3行：HT[2] (b)
1 5 0 0              ← 第4行：HT[3] (c)
2 5 1 2              ← 第5行：HT[4] (内部节点)
3 0 3 4              ← 第6行：HT[5] (根)
a:10 b:11 c:0        ← 第7行：编码表
10110                ← 第8行：编码串
abc                  ← 第9行：解码还原

示例B：单字符输入 "aaaa"

这是一个边界情况：所有字符相同，n=1，m=1（没有内部节点）。

输出（2×1+3 = 5行）：

a:4                  ← 频度：a出现4次
4 0 0 0              ← 唯一的树节点：权=4，根（parent=0），叶子（lchild=rchild=0）
a:0                  ← 编码：固定为 "0"
0000                 ← 编码串：4个0对应4个a
aaaa                 ← 解码还原

关键代码逻辑：当 n=1 时，不执行合并循环（n+1 > m），直接走到编码生成。编码时 while(parent != 0) 不执行，code 为空，被特殊处理为 "0"（第182行）。解码时检测 m == 1，将每个 '0' 直接映射为唯一字符（第206-207行）。

示例C：复杂输入 "MiaoXiyuan"（大小写混合，含重复字符）

输入 "MiaoXiyuan" 展示了大写字母自动转小写的处理以及多个字符种类的完整编码过程。

频率统计（n=8种字符）：

原始输入: M i a o X i y u a n
转小写后: m i a o x i y u a n

a:2   i:2   m:1   n:1   o:1   u:1   x:1   y:1

合并过程概览（8个叶子 → 经过7轮合并 → 1个根）：

轮1 (i=9):  合并 m(1)+n(1) → 内部节点[9]  w=2
轮2 (i=10): 合并 o(1)+u(1) → 内部节点[10] w=2
轮3 (i=11): 合并 x(1)+y(1) → 内部节点[11] w=2
轮4 (i=12): 合并 a(2)+i(2) → 内部节点[12] w=4
轮5 (i=13): 合并 [9](2)+[10](2) → 内部节点[13] w=4
轮6 (i=14): 合并 [11](2)+[12](4) → 内部节点[14] w=6
轮7 (i=15): 合并 [13](4)+[14](6) → 根节点[15] w=10

最终哈夫曼树结构：

                         [15] w=10 (根)
                    /                    \
             [13] w=4                  [14] w=6
            /        \                /        \
      [9] w=2      [10] w=2     [11] w=2    [12] w=4
      /    \        /    \       /    \      /    \
   m(1)  n(1)   o(1)  u(1)   x(1)  y(1)  a(2)  i(2)

各字符编码验证：

字符权值回溯路径（下标→parent）反转得编码
m1[3]→[9](左/0)→[13](左/0)→[15](左/0)000
n1[4]→[9](右/1)→[13](左/0)→[15](左/0)001
o1[5]→[10](左/0)→[13](右/1)→[15](左/0)010
u1[6]→[10](右/1)→[13](右/1)→[15](左/0)011
x1[7]→[11](左/0)→[14](左/0)→[15](右/1)100
y1[8]→[11](右/1)→[14](左/0)→[15](右/1)101
a2[1]→[12](左/0)→[14](右/1)→[15](右/1)110
i2[2]→[12](右/1)→[14](右/1)→[15](右/1)111

编码结果：

"miaoxiyuan"
= m(000) + i(111) + a(110) + o(010) + x(100) + i(111) + y(101) + u(011) + a(110) + n(001)
= 000111110010100111101011110001

观察：权值为2的字符（a, i）获得3位编码，而权值为1的字符（m, n, o, u, x, y）也获得3位编码。这是因为在此频率分布下（2×2 + 6×1 = 10），树的结构使得所有叶子到根的深度都为3。这是哈夫曼树的一种特殊情况——当频率分布比较均匀时，编码长度也趋于均匀。

如果修改输入为 "aaabc"（a出现3次，b,c各1次），则a会获得更短的编码（如"0"），b和c获得较长的编码（如"10"和"11"）——这就体现了哈夫曼编码"高频短码、低频长码"的核心优势。

完整输出（2×8+3 = 19行）：

a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1           ← 第1行：频度 (n=8)
 2 12 0 0                                   ← 第2行：HT[1](a)
 2 12 0 0                                   ← 第3行：HT[2](i)
 1 9 0 0                                    ← 第4行：HT[3](m)
 1 9 0 0                                    ← 第5行：HT[4](n)
 1 10 0 0                                   ← 第6行：HT[5](o)
 1 10 0 0                                   ← 第7行：HT[6](u)
 1 11 0 0                                   ← 第8行：HT[7](x)
 1 11 0 0                                   ← 第9行：HT[8](y)
 2 13 3 4                                   ← 第10行：HT[9]  内部(m+n)
 2 13 5 6                                   ← 第11行：HT[10] 内部(o+u)
 2 14 7 8                                   ← 第12行：HT[11] 内部(x+y)
 4 14 1 2                                   ← 第13行：HT[12] 内部(a+i)
 4 15 9 10                                  ← 第14行：HT[13] 内部
 6 15 11 12                                 ← 第15行：HT[14] 内部
10 0 13 14                                  ← 第16行：HT[15] 根
a:110 i:111 m:000 n:001 o:010 u:011 x:100 y:101  ← 第17行：编码表
000111110010100111101011110001                    ← 第18行：编码串
miaoxiyuan                                       ← 第19行：解码串

示例D：均频输入 "aabbcc"（多个字符出现相同次数）

输入 "aabbcc"，a、b、c 各出现 2 次，频率完全相同。

输出：

a:2 b:2 c:2          ← 各出现2次，n=3
2 4 0 0              ← HT[1](a)
2 4 0 0              ← HT[2](b)
2 5 0 0              ← HT[3](c)
4 5 1 2              ← HT[4] 内部(a+b=4)
6 0 3 4              ← HT[5] 根(c+内部=6)
a:10 b:11 c:0        ← 编码：c最短（虽然频率相同，但合并顺序导致）
1010111100           ← 编码串
aabbcc               ← 解码还原

观察：虽然 a、b、c 频率都为 2，但 c 获得了最短的编码 "0"（1位），而 a 和 b 各获得 2 位编码 "10" 和 "11"。这是因为 Select 函数中选择的顺序影响了树的形态——当多个节点权值相同时，具体的择取决取决于数组遍历顺序。这并不影响哈夫曼树的最优性（WPL仍然是最小的），只是说明最优哈夫曼树不唯一。

验证 WPL：a(2×2) + b(2×2) + c(2×1) = 4+4+2 = 10。若改为 a=0, b=10, c=11（任意排列），WPL = 2×1 + 2×2 + 2×2 = 10，相同。说明不同形态的最优哈夫曼树的 WPL 是相等的。

九、结果解读指南

下面以中文详细解释程序输出的每一行含义，帮助理解实验结果。

9.1 任务1输出解读

=== 任务1：判别两棵二叉树是否相等 ===
测试1: 先序序列 "AB##C##" 和 "AB##C##" -> 相等 ✓正确
测试2: 先序序列 "AB##C##" 和 "AD##C##" -> 不相等 ✓正确
测试3: 先序序列 "AB##C##" 和 "ABC###" -> 不相等 ✓正确
输出字段含义判断依据
相等CmpTree() 返回1：根节点值相同 + 左子树结构/数据相同 + 右子树结构/数据相同两棵树的先序序列完全一致
不相等CmpTree() 返回0：某处发现节点值不同或结构不同（一边NULL一边非NULL）先序序列至少有一处差异
✓正确程序输出与预设的 expected 值一致result == tests[i].expected
✗错误程序输出与预设的 expected 值不一致（正常情况不应出现）说明代码存在bug

9.2 任务2输出逐行解读（以输入 "abc" 为例）

第1行：字符频度

a:1 b:1 c:1
格式字符:频率 字符:频率 ...
解释统计输入字符串中各字母的出现次数（仅统计 a-z，不区分大小写），按 ASCII 升序输出
计算方式遍历字符串，freq[ch-'a']++，然后按字母序输出非零项
用途这 n 个频度值就是哈夫曼树叶子节点的初始权值，也是后续建树的输入

第2 ~ 2n行：哈夫曼树节点终态

1 4 0 0    ← HT[1]: 权值=1, 父节点=4, 左孩子=0(无), 右孩子=0(无) → 叶子a
1 4 0 0    ← HT[2]: 权值=1, 父节点=4, 左孩子=0(无), 右孩子=0(无) → 叶子b
1 5 0 0    ← HT[3]: 权值=1, 父节点=5, 左孩子=0(无), 右孩子=0(无) → 叶子c
2 5 1 2    ← HT[4]: 权值=2, 父节点=5, 左孩子=1(a), 右孩子=2(b) → 内部节点
3 0 3 4    ← HT[5]: 权值=3, 父节点=0(根), 左孩子=3(c), 右孩子=4(内部) → 根

每行四列的含义：

列号字段名含义特殊值的意义
1weight该节点的权值叶子=字符频度；内部=子节点权值和
2parent父节点下标0 = 该节点是根（无父节点）
3lchild左孩子下标0 = 无左孩子（即该节点是叶子，或内部但暂无左孩子）
4rchild右孩子下标0 = 无右孩子（同理）

如何从表格还原树结构：

  1. 找根节点：遍历所有行，找到 parent == 0 的那一行——该行就是根。对于 "abc"，HT[5] 的 parent=0，故下标5是根。
  2. 判断叶子：若某行的 lchild == 0 && rchild == 0，则该节点是叶子，存储了一个字符。
  3. 溯父链：顺着 parent 字段的值（下标）可向上找到父节点，用于生成编码。
  4. 溯子链：顺着 lchild/rchild 字段的值可向下找到孩子，用于解码。

例如从表格还原 "abc" 的树：

根 = HT[5]（parent=0）
HT[5]: lchild=3 → HT[3]=c(叶子), rchild=4 → HT[4](内部)
HT[4]: lchild=1 → HT[1]=a(叶子), rchild=2 → HT[2]=b(叶子)

树结构:
    [5]w=3
    /    \
 [3]c   [4]w=2
        /    \
     [1]a   [2]b

第2n+1行：哈夫曼编码表

a:10 b:11 c:0

含义：字符 → 对应的二进制编码（0/1串）。例如：

  • a:10 — 字符 a 的哈夫曼编码为 "10"（左-右）
  • b:11 — 字符 b 的哈夫曼编码为 "11"（右-右）
  • c:0 — 字符 c 的哈夫曼编码为 "0"（左）

可以看到较短编码（如c只有一个"0"）对应的字符在树中离根更近（路径短）。

第2n+2行：编码后的二进制串

10110

这是将输入字符串中每个字符替换为对应哈夫曼编码后拼接得到的结果。例如 "abc" → a的编码(10) + b的编码(11) + c的编码(0) = "10110"。

压缩效果分析（以 "MiaoXiyuan" 为例）：

  • 原字符串 10 字符 × 8 bit/char（ASCII）= 80 bits
  • 哈夫曼编码后：000111110010100111101011110001 = 30 bits
  • 压缩率：30/80 = 37.5%（节省 62.5% 的空间）

第2n+3行：解码还原的字符串

abc

这是将上一行的二进制编码串解码后得到的原始字符串（已转为小写，过滤非字母字符）。

正确性验证：如果这一行与原始输入字符串（转小写、去除非字母后）完全一致，说明编码→解码过程正确无误，哈夫曼树的编码表能够无损地表达原始信息。

9.3 如何快速核对结果

  1. 核对频度：频率之和应等于原始输入中字母的个数。例如 "MiaoXiyuan" 去掉非字母后共 10 个字母，频度之和 = 2+2+1+1+1+1+1+1 = 10 ✓
  2. 核对树节点数：输出的树节点终态行数应为 2n-1。例如 n=8，应有 15 行 ✓
  3. 核对 WPL：带权路径长度 = Σ(频度 × 编码长度)。对于 "MiaoXiyuan"：WPL = 2×3 + 2×3 + 1×3 + 1×3 + 1×3 + 1×3 + 1×3 + 1×3 = 30。编码串长度恰好等于 WPL ✓
  4. 核对编码前缀性：任意两个字符的编码，较短的那个不应是较长的前缀。例如 m=000, n=001, o=010 中，000 不是 001 和 010 的前缀 ✓
  5. 核对解码正确性：解码串应等于原始输入转小写后的字母串

十、代码实现注意事项

  1. 下标从 1 开始：哈夫曼树数组 HT[1..m] 的下标从 1 开始（0 号位置被手动清零作为哨兵），目的是使 parent==0 表示无父节点/根节点，代码直观。
  2. Select 函数中用 INT_MAX 做标记：找第一个最小值后，将其临时设为 INT_MAX 避免第二轮重复选中，选完第二个后再恢复。这是"标记法"的经典应用。
  3. n=1 的特殊处理：单字符输入时编码固定为 "0"，解码时直接将所有 '0' 替换为该字符。如果不做特殊处理，回溯编码的 while 循环不会执行，code 为空串，需要手动设 "0"。
  4. 大小写处理：代码通过 tolower() 将输入全部转为小写统计，但解码输出直接使用原始叶子节点的 ch（在第136-142行被赋予小写值），因此输出统一为小写。
  5. 非字母字符被忽略：频率统计和解码输出都跳过非 a-z 的字符，包括空格、标点、数字等。

数据结构与算法实验 © 2026  |  姓名：苗夕远