树与二叉树

一、概念

1. 树的基本概念

树是一种非线性数据结构，由n（n≥0）个节点组成的有限集合，满足：

• 当n=0时，称为空树；
• 当n>0时，存在唯一一个称为**根（Root）**的节点，其余节点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵子树，称为根的子树。

核心术语：

• 节点的度：节点拥有的子树个数（二叉树中节点度最大为2）；
• 树的度：树中所有节点的最大度；
• 叶子节点（终端节点）：度为0的节点（无子女节点）；
• 非叶子节点（非终端节点）：度大于0的节点；
• 节点的层次：根节点为第1层，根的子女为第2层，依次类推；
• 树的深度（高度）：树中节点的最大层次；
• 有序树/无序树：子树之间有固定顺序的为有序树（二叉树是有序树，左右子树不可随意交换），无固定顺序的为无序树。

2. 二叉树的基本概念

二叉树是一种特殊的有序树，每个节点的度最多为2，即每个节点最多有左、右两个子树，分别称为左子树和右子树。

二叉树的常见分类：

• 满二叉树：深度为h的二叉树，有$2^h-1$个节点（每层节点数都达到最大值）；
• 完全二叉树：深度为h的二叉树，除第h层外，其余各层节点数均达最大值，且第h层的节点都连续集中在最左侧；
• 对称二叉树：交换树中所有节点的左右子树后，新树与原树的结构和节点权值完全一致；
• FBI树：由01串递归构建，节点分为B（全0串）、I（全1串）、F（既含0又含1串）三种类型；
• 哈夫曼树（最优二叉树/k叉最优树）：给定n个权值，构建一棵包含n个叶子节点的树，使得树的带权路径长度（WPL）最小，二叉哈夫曼树是最常见的类型，本题也扩展到k叉哈夫曼树。

3. 哈夫曼编码的基本概念

哈夫曼编码是一种基于哈夫曼树的前缀编码（任意编码互不成为对方的前缀），用于数据压缩，核心特点是：权值越大（出现次数越多）的节点，编码长度越短，从而实现总编码长度最小。

核心术语：

• 前缀编码：对于任意两个编码$s_i$和$s_j$（$i≠j$），$s_i$不是$s_j$的前缀，反之亦然（保证解码无歧义）；
• 带权路径长度（WPL）：树中所有叶子节点的权值乘以其到根节点的路径长度（路径上的边数，对应编码长度）之和，即$WPL=\sum_{i=1}^n w_i \times l_i$（$w_i$为叶子节点权值，$l_i$为路径长度）；
• 哈夫曼编码：从哈夫曼树的根节点出发，左分支标记为0（或1）、右分支标记为1（或0），叶子节点对应的路径字符串即为该节点的哈夫曼编码。

二、性质

1. 二叉树的通用性质

1. 若二叉树的根节点层次为1，则深度为h的二叉树，最多有$2^h-1$个节点（满二叉树）；
2. 对于任意一棵二叉树，若叶子节点数为$n_0$，度为2的节点数为$n_2$，则必有$n_0 = n_2 + 1$；
3. 完全二叉树的节点数为n，深度为$h=\lfloor log_2 n \rfloor + 1$（向下取整）；
4. 完全二叉树中，节点i（$1≤i≤n$）的子女节点规律：
   • 左子女：$2i$（若$2i≤n$，否则无左子女）；
   • 右子女：$2i+1$（若$2i+1≤n$，否则无右子女）；
   • 父节点：$\lfloor i/2 \rfloor$（若$i>1$，否则为根节点，无父节点）。

2. 哈夫曼树（二叉）的性质

1. 哈夫曼树中没有度为1的节点（只有叶子节点和度为2的节点），又称严格二叉树；
2. 给定n个叶子节点的权值，构建的二叉哈夫曼树共有$2n-1$个节点；
3. 哈夫曼树的带权路径长度是所有可能的二叉树中最小的，即最优二叉树；
4. 哈夫曼树不唯一，但带权路径长度的最小值唯一。

3. k叉哈夫曼树的性质

1. 为保证构建的k叉哈夫曼树的带权路径长度最小，需要满足**$(n-1) \% (k-1) = 0$**（n为叶子节点数）；
2. 若不满足上述条件，需要补充$(k-1) - (n-1) \% (k-1)$个权值为0的虚拟叶子节点，补充后节点总数满足合并规则；
3. k叉哈夫曼树中，非叶子节点的度均为k，最终树的节点总数为$n + 补充节点数 + \lfloor (n+补充节点数-1)/(k-1) \rfloor$。

三、遍历和应用

1. 二叉树的遍历（核心操作）

遍历是指按一定顺序访问二叉树的所有节点，且每个节点仅被访问一次，核心分为深度优先遍历（DFS）和广度优先遍历（BFS，层次遍历），其中深度优先遍历又分为3种顺序：

（1）深度优先遍历（DFS）

• 前序遍历（根→左→右） 应用：构建二叉树、获取先序序列、FBI树构建前的节点遍历； 实战题：已知中序+后序求先序、二叉树前序遍历输出。

• 中序遍历（左→根→右） 应用：二叉树排序（二叉搜索树的中序遍历为有序序列）、判断对称二叉树的辅助遍历、已知前序+后序求可能的中序序列数； 实战题：已知前序+中序求后序、对称二叉树判断。

• 后序遍历（左→右→根） 应用：计算子树节点数、删除二叉树、FBI树后序遍历输出、哈夫曼树的带权路径长度计算； 实战题：FBI树后序遍历、二叉树后序遍历输出、寻找最大对称二叉子树。

（2）广度优先遍历（BFS，层次遍历）

• 遍历顺序：从上到下、从左到右依次访问每层节点；
• 应用：求树的深度、判断完全二叉树、层序输出二叉树节点；
• 实现方式：借助队列（先进先出）实现。

（3）遍历的实现方式

• 递归实现：代码简洁直观，适合小规模数据（n≤1e4），但递归深度过深（n≥1e5）会导致栈溢出；
• 非递归实现（迭代）：借助栈（DFS）或队列（BFS）手动模拟遍历过程，适合大规模数据（n≤1e6），无栈溢出风险；
• 实战题：1e6节点二叉树的前/中/后序遍历（必须用非递归实现）。

2. 核心应用场景

1. 二叉树的构建与序列转换

   • 场景：已知两种遍历序列（前序+中序、中序+后序），构建二叉树并求第三种序列；
   • 注意：前序+后序无法唯一确定中序序列，仅能求可能的中序序列数；
   • 实战题：前序+中序求后序、中序+后序求先序、前序+后序求中序可能数。

2. 对称二叉树的判断与最大子树查找

   • 场景：给定二叉树，寻找节点数最多的对称二叉子树；
   • 核心：对称判断（节点权值相等、左子树与右子树镜像对称）、子树节点数预计算；
   • 实战题：寻找最大对称二叉子树。

3. FBI树的构建与后序遍历

   • 场景：由01串递归构建FBI树，输出后序遍历序列；
   • 核心：串类型判断（B/I/F）、递归拆分左右子串、后序遍历拼接结果；
   • 实战题：FBI树后序遍历输出。

4. 哈夫曼树构建与哈夫曼编码

   • 场景：给定n个权值，构建k叉哈夫曼树，求最短总编码长度和最长编码的最短长度；
   • 核心：小根堆（优先队列）合并最小权值节点、补点规则、带权路径长度计算；
   • 实战题：k进制哈夫曼编码（最短总长度+最长编码最短长度）。

5. 大规模二叉树的高效处理

   • 场景：n≤1e6节点的二叉树遍历、子树节点数计算；
   • 核心：数组存储节点信息（左/右孩子、权值）、非递归遍历避免栈溢出、scanf/printf优化输入输出；
   • 实战题：1e6节点二叉树的前/中/后序遍历。

四、模版代码

1. 二叉树根据前序和中序求后序

// 递归函数：先序pre → 中序in → 生成后序序列
string post(string p, string i) {
    if (p.empty()) return ""; // 递归终止：空序列返回空
    char r = p[0]; // 根节点（简化root为r）
    int idx = i.find(r); // 根节点在中序中的索
    // 划分左右子树序列（极致精简变量名）
    string l_p = p.substr(1, idx);  // 左子树先序
    string l_i = i.substr(0, idx);  // 左子树中序
    string r_p = p.substr(idx+1);   // 右子树先序
    string r_i = i.substr(idx+1);   // 右子树中序
    // 后序：左→右→根，拼接结果
    return post(l_p, l_i) + post(r_p, r_i) + r;
}

2. 二叉树的非递归遍历模版（适配1e6节点）

int lch[N], rch[N]; // lch[i]=节点i的左孩子，rch[i]=节点i的右孩子
int pre[N], in[N], post[N]; // 存储三种遍历结果
int cnt; // 遍历结果计数器
// 非递归前序遍历（根→左→右）
void pre_order(int root) {
    stack<int> st;
    st.push(root);
    cnt = 0;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        pre[++cnt] = u; // 存储当前节点
        // 栈先进后出，先压右孩子，再压左孩子，保证左孩子先处理
        if (rch[u]) st.push(rch[u]);
        if (lch[u]) st.push(lch[u]);
    }
}
// 非递归中序遍历（左→根→右）
void in_order(int root) {
    stack<int> st;
    int u = root;
    cnt = 0;
    while (u || !st.empty()) {
        // 先将所有左孩子压入栈
        while (u) {
            st.push(u);
            u = lch[u];
        }
        // 无左孩子，处理当前节点
        u = st.top();
        st.pop();
        in[++cnt] = u;
        // 处理右孩子
        u = rch[u];
    }
}
// 非递归后序遍历（左→右→根，双栈实现）
void post_order(int root) {
    stack<int> st1, st2;
    st1.push(root);
    cnt = 0;
    while (!st1.empty()) {
        int u = st1.top();
        st1.pop();
        st2.push(u); // 栈2接收节点
        // 栈1按「根→左→右」压入，栈2弹出即为「根→右→左」，最终反转即为后序
        if (lch[u]) st1.push(lch[u]);
        if (rch[u]) st1.push(rch[u]);
    }
    // 提取栈2结果，存入post数组
    while (!st2.empty()) {
        post[++cnt] = st2.top();
        st2.pop();
    }
}

3. 对称二叉树判断与最大子树查找模版

int n;      // 节点总数
int v[N];   // 节点权值
int l[N];   // 左孩子
int r[N];   // 右孩子
int s[N];   // 子树节点数
int m;      // 最大对称子树节点数
// 递归判断x和y是否对称（保留原代码核心逻辑，变量名精简）
bool dfs(int x, int y) {
    if (x == -1 && y == -1) return true;  // 均为空，对称
    if (x == -1 || y == -1) return false; // 一空一非空，不对称
    if (v[x] != v[y]) return false;       // 权值不等，不对称
    // 递归判断：x左 vs y右，x右 vs y左
    return dfs(l[x], r[y]) && dfs(r[x], l[y]);
}
// 递归计算子树节点数（保留原代码逻辑，变量名精简，结果存入s数组）
int calc_s(int x) {
    if (x == -1) return 0;                // 空节点，节点数0
    s[x] = calc_s(l[x]) + calc_s(r[x]) + 1; // 子树节点数=左+右+自身
    return s[x];
}

五、注意事项

1. 数据规模与溢出问题

   • 小规模数据（n≤1e4）：可使用递归遍历、cin/cout输入输出，变量类型使用int即可；
   • 大规模数据（n≥1e5）：必须使用非递归遍历、scanf/printf输入输出，避免超时和栈溢出；
   • 哈夫曼树问题：权值$w_i≤10^{11}$，总长度可能超过int范围，必须使用long long（64位整数）存储。

2. 二叉树遍历的细节

   • 递归遍历的终止条件：节点为-1（无孩子）时直接返回；
   • 非递归前序遍历：先压右孩子再压左孩子，保证左孩子先被访问；
   • 非递归后序遍历（双栈）：栈1按「根→左→右」压入，栈2接收后弹出即为「左→右→根」。

3. 哈夫曼树的补点规则

   • 仅当k>1时需要补点，k=1无实际编码意义；
   • 补点数量为$(k-1) - (n-1) \% (k-1)$，且需判断need != k-1，避免n=1时多余补点；
   • 虚拟节点权值为0，不影响总编码长度，仅用于保证每次合并k个节点。

4. 对称二叉树的判断细节

   • 单个节点必然是对称二叉树，初始化最大节点数为1；
   • 对称判断的核心：x的左孩子与y的右孩子对称且x的右孩子与y的左孩子对称；
   • 先预计算所有节点的子树节点数，避免重复计算，提升效率。

5. FBI树的构建细节

   • 串类型判断可提前终止遍历（既含0又含1时直接跳出循环），提升效率；
   • 递归拆分串时，按mid = len / 2等长拆分，左子串为[0, mid)，右子串为[mid, len)。

六、总结

1. 树与二叉树的核心：二叉树是有序树，遍历是所有操作的基础，递归遍历简洁、非递归遍历高效，需根据数据规模选择合适的实现方式。
2. 序列转换的关键：前序+中序、中序+后序可唯一确定二叉树，前序+后序仅能求中序序列的可能数，核心是通过根节点拆分左右子树。
3. 哈夫曼树的核心价值：实现最优前缀编码，二叉哈夫曼树无度为1的节点，k叉哈夫曼树需满足补点规则，通过小根堆合并最小权值节点实现最小带权路径长度。
4. 实战技巧：大规模数据优先使用数组存储、非递归遍历、scanf/printf；涉及权值和的问题优先使用long long避免溢出；对称判断、哈夫曼合并等核心逻辑可复用模版代码。

树与二叉树是数据结构的核心内容，哈夫曼编码是其重要应用场景，掌握上述知识点和模版代码，能够解决绝大多数相关实战题目，同时为后续学习二叉搜索树、平衡树等进阶内容打下坚实基础。