特殊树

特殊树

完全二叉树的定义与基本性质、数组表示法；哈夫曼树的定义和构造、哈夫曼编码；二叉搜索树的定义和构造。

概念

完全二叉树：除最后一层外各层满，最后一层从左到右连续填；$n$ 个结点时可紧凑存入数组，下标 $i$ 的父为 $\lfloor i/2\rfloor$，左子 $2i$、右子 $2i+1$。哈夫曼树：带权路径长度最小的二叉树，构造时每次合并权值最小的两棵；用于变长编码，高频字符短码、低频长码，且任一编码不是另一编码前缀。二叉搜索树（BST）：左子树键值 $<$ 根 $<$ 右子树；中序遍历得有序序列。与 cspj.ds.tree：特殊树都是树，但加了形状或权值约束；与 cspj.ds.binary-tree：本叶不考一般遍历还原，而考完全二叉树计数/高度、哈夫曼带权路径长或编码长度、BST 插入查找性质。

CSP-J 常考

• cspj-r1-2019 第 8 题：给定二叉树形态，顺序存储（根下标 1）时数组最大下标至少为多少。
• cspj-r1-2020 第 12 题：61 个结点的完全二叉树高度（根高度为 1）。
• cspj-r1-2022 第 7 题：按字母频率构造哈夫曼编码，求某字母的编码位数。
• cspj-r1-2022 第 8 题：完全二叉树数组下标 9 的结点有兄弟且有两个孩子，求兄弟与右孩子下标。
• cspj-r1-2025 第 4 题：五个权值构造哈夫曼树，求带权路径长度（WPL）。

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

// 哈夫曼 WPL：每次取最小两权合并
int huffmanWpl(vector<int> w) {
    priority_queue<int, vector<int>, greater<int>> pq(w.begin(), w.end());
    int ans = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    return ans;
}

易错点

• 完全二叉树高度：$n$ 个结点时 $h=\lfloor\log_2 n\rfloor+1$（根高 1），与「满二叉树」层数公式不要混用。
• 哈夫曼构造：先合并最小两个，新结点权为两者之和；WPL 是各叶子权×深度之和，不是简单相加所有权值。
• 数组下标 9 的兄弟是 8 还是 10：同层相邻偶奇配对，$i$ 与 $i±1$ 互为兄弟（$i>1$）。
• BST 插入重复键、删除结点后的中序有序性——初赛若考，先画小例子再选。