一、树

1、树（Tree）的定义

树是n（n≥0）个结点的有限集合：
若 n=0，称为空树。
若 n>0：
有且仅有一个根结点（Root）。
其余结点可分为 m 个互不相交的有限集合 T₁、T₂…Tₘ，每个集合本身也是一棵树，称为子树。

层次化的非线性数据结构，由节点和边组成，有且仅有一个根节点，子节点互不相交。

2.树的特点

子树个数不限（0、1、2、3… 都可以）。
子树没有左右顺序之分（无序）。
根结点无前驱，其他结点有且仅有一个父结点。
无环、无交叉。

二、二叉树

1.二叉树的定义

二叉树是 n（n≥0）个结点的有限集合：
或为空树
或由一个根结点 + 左子树 + 右子树组成
左、右子树本身也是二叉树

每个节点最多有两个子节点（左孩子、右孩子），左右有序不可互换。

2.二叉树的特点

每个结点最多有 2 棵子树（0、1、2 个）。
子树严格分左右，次序不能互换（有序树）。
即使只有一棵子树，也要区分是左孩子还是右孩子。
是最简单、最常用的树形结构。

3.树和二叉树的区别

项目	普通树（Tree）	二叉树（Binary Tree）
子树个数	不限，可以任意多	最多 2 个（0/1/2）
左右顺序	无序，子树不分左右	有序，严格分左、右
空树	允许	允许
单结点子树	不区分左右	必须区分左 / 右
结构种类	随度变化极多	固定 5 种基本形态
存储结构	孩子兄弟表示法等	二叉链表、顺序存储
遍历方式	先根、后根	前、中、后、层序

4.二叉树的重要性质

第 i 层最多 2ⁱ⁻¹ 个结点。
深度为 k 的二叉树最多 2ᵏ - 1 个结点。
叶子结点数 n₀ = 度为 2 的结点数 n₂ + 1
n₀ = n₂ + 1
具有 n 个结点的完全二叉树深度：
⌊log₂n⌋ + 1
完全二叉树父子下标关系（从 1 开始）：
左孩子：2i
右孩子：2i+1
父结点：⌊i/2⌋

5.总结

树：结点可以有任意多个孩子，不分左右。
二叉树：结点最多两个孩子，严格分左右。
二叉树是有序树，普通树是无序树。

三、三种遍历二叉树的方式

前序：根 → 左 → 右
中序：左 → 根 → 右（BST 升序）
后序：左 → 右 → 根
层序：按层遍历（用队列）

1.二叉树节点结构体：

#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构
typedef struct TreeNode {
    int data;               // 数据域
    struct TreeNode *left;  // 左孩子
    struct TreeNode *right; // 右孩子
} TreeNode, *BiTree;

2.创建一个新节点

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

3.四种遍历（递归版，最易理解）

// 前序遍历：根 → 左 → 右
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历：左 → 根 → 右
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

// 后序遍历：左 → 右 → 根
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

// 层序遍历（用队列）
void levelOrder(TreeNode* root) {
    if (root == NULL) return;

    TreeNode* queue[100]; // 简单队列
    int front = 0, rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        TreeNode* cur = queue[front++];
        printf("%d ", cur->data);

        if (cur->left)  queue[rear++] = cur->left;
        if (cur->right) queue[rear++] = cur->right;
    }
}

4.完整 main 测试

int main() {
    // 构建一棵二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前序: "); preOrder(root); printf("\n");
    printf("中序: "); inOrder(root); printf("\n");
    printf("后序: "); postOrder(root); printf("\n");
    printf("层序: "); levelOrder(root); printf("\n");

    return 0;
}

四、满二叉树与完全二叉树与平衡二叉树的区别

1.时间复杂度对比

操作	完全二叉树	满二叉树	平衡二叉树（AVL）
查找（最坏）	O(n)（退化为链表时），平均 O(logn)	O(logn)（树高固定为 log2​(n+1)）	稳定 O(logn)（自平衡保证）
插入（最坏）	O(n)（链表形态），平均 O(logn)	O(logn)	O(logn)（含旋转操作）
删除（最坏）	O(n)（链表形态），平均 O(logn)	O(logn)	O(logn)（含旋转操作）
遍历	O(n)（所有二叉树遍历时间复杂度均为 O(n)）	O(n)	O(n)

2.核心定义和结构对比

对比维度	完全二叉树 (Complete Binary Tree)	满二叉树 (Full Binary Tree)	平衡二叉树 (AVL 树，Balanced Binary Tree)
标准定义	除最后一层外，其余所有层节点完全填满；最后一层节点严格靠左对齐，无中间空缺	二叉树中所有层的节点都完全填满，无任何空缺，所有叶子节点都在同一层（最底层）	任意节点的左右子树高度差（平衡因子）的绝对值 ≤ 1，且左右子树均为平衡二叉树
节点数与深度关系	深度为 h 时，节点数 n 满足：2h−1≤n≤2h−1	深度为 h 时，节点数固定为 n=2h−1	深度 h≈1.44log2​(n+2)，节点数无固定公式，仅受平衡因子约束
叶子节点位置	仅出现在最后两层，最后一层节点靠左排列	所有叶子节点都在同一层（最底层）	可出现在任意层，无位置限制
非叶节点结构	最多只有最后一层的父节点可能只有左孩子，其余非叶节点都有两个孩子	所有非叶节点都有且仅有两个孩子，无度为 1 的节点	非叶节点可拥有 0、1、2 个孩子，仅需满足平衡因子约束
包含关系	满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树	是完全二叉树的特例	与前两者无包含关系：完全 / 满二叉树一定是平衡二叉树，但平衡二叉树不一定是完全 / 满二叉树
存储方式	支持数组顺序存储（层序编号连续，空间利用率高，堆的核心结构），也支持链式存储	支持数组顺序存储（无空间浪费），也支持链式存储	仅支持链式存储（结构不连续，无法用数组高效存储）

1. 完全二叉树

✅ 编号连续性：按层序（从上到下、从左到右）编号后，节点编号连续无跳跃，因此可直接用数组存储，父子节点下标关系固定：

1 基编号：节点 i的左孩子 2i，右孩子 2i+1，父节点 ⌊i/2⌋

0 基编号：节点 i的左孩子 2i+1，右孩子 2i+2，父节点 ⌊(i−1)/2⌋

✅ 深度计算：已知节点数 n，深度 h=⌊log 2n⌋+1
✅ 应用场景：堆排序、优先队列、完全二叉树的层序遍历 / 数组构建

2.满二叉树

✅ 节点数严格对应深度：深度 h的满二叉树，节点数固定为 2 （h−1），叶子节点数为 2 （h−1
 ），非叶节点数为 2 （h−1）−1。     （ ）中的内容为幂

✅ 叶子节点性质：叶子节点数 = 非叶节点数 + 1
✅ WPL 特性：是哈夫曼树的特例，带权路径长度（WPL）最优
✅ 应用场景：哈夫曼编码、满二叉树的遍历、完全二叉树的基准参考

3. 平衡二叉树（AVL 树）

✅ 平衡因子定义：节点的平衡因子 = 左子树高度 - 右子树高度，要求 ∣BF∣≤1
✅ 自平衡特性：插入 / 删除节点后，若破坏平衡，通过旋转操作（左旋、右旋、左右旋、右左旋） 恢复平衡
✅ 查找效率：查找时间复杂度稳定为 O(logn)，不会退化为链表的 O(n)
✅ 应用场景：高效查找、有序集合存储（如 C++ 的set/map底层早期实现）

3.应用场景总结

树类型	核心应用场景	优势
完全二叉树	堆排序、优先队列、完全二叉树数组存储	数组存储高效，父子关系固定，实现简单
满二叉树	哈夫曼编码、满二叉树遍历、完全二叉树基准	结构规整，WPL 最优，遍历效率高
平衡二叉树（AVL）	高效查找、有序集合存储、数据库索引	查找时间复杂度稳定 O(logn)，无链表退化风险

4.易错点

易错点与核心区分
1. 完全二叉树 vs 满二叉树
❌ 误区：“所有非叶节点都有两个孩子就是满二叉树” → 错误，完全二叉树也满足该条件（除最后一层父节点），但满二叉树要求所有层全满
✅ 核心区分：满二叉树是完全二叉树的 “极限状态”，完全二叉树是满二叉树的 “不完全版本”
2. 完全二叉树 vs 平衡二叉树
❌ 误区：“完全二叉树一定是平衡二叉树” → 正确！完全二叉树的左右子树高度差最多为 1，天然满足 AVL 树的平衡条件
✅ 反向不成立：平衡二叉树不一定是完全二叉树（如上述示例）
3. 满二叉树 vs 平衡二叉树
✅ 满二叉树一定是平衡二叉树（所有节点平衡因子为 0）
❌ 平衡二叉树不一定是满二叉树（结构可任意，仅需平衡因子约束）

五、哈夫曼树

1.定义

哈夫曼树 = 最优二叉树 = 带权路径长度 WPL 最小的二叉树
关键概念
权值：节点的数值（频率、概率、代价）
路径长度：从根到该节点经过的边数
带权路径长度 WPL：所有叶子节点的
权值 × 路径长度 之和
哈夫曼树就是让 WPL 最小 的二叉树。

2.构造规则

把所有叶子节点按权值从小到大排列
每次选两个权值最小的节点合并
新节点权值 = 两个子节点权值之和
把新节点放回集合，重新排序
重复直到只剩1 个根节点

3.核心特征

1.哈夫曼树没有度为 1 的节点
所有非叶子节点都有 2 个孩子
2.n 个叶子 → 总节点数 = 2n - 1
3.权值越大 → 离根越近（保证 WPL 最小）
4.哈夫曼树不唯一，但 WPL 一定唯一
5.是二叉树，但不一定是完全二叉树
6.哈夫曼树是前缀码树，解码无歧义

4.计算公式

5.哈夫曼树 vs 普通二叉树 vs 完全二叉树

特点	哈夫曼树	普通二叉树	完全二叉树
度为 1 节点	无	可有	最多 1 个
叶子数 n	总节点 = 2n-1	任意	任意
WPL	最小	不一定	不一定
结构	由权值决定	任意	严格层序靠左
用途	压缩编码	通用	堆、排序

6.易错点

1.哈夫曼树不是完全二叉树
2.哈夫曼树没有度为 1 的节点
3.哈夫曼编码是前缀码，不是等长码
3.结构不唯一，但 WPL 一定唯一
4.哈夫曼树是二叉树，不是普通树

7.哈夫曼树实现编码

1.哈夫曼树节点结构
权值 weight
左右孩子 lchild /rchild
字符（用于编码）c
2.最小堆（优先队列）：用于每次取两个最小权值节点
3.构造哈夫曼树：合并两个最小节点，循环到根
4.计算 WPL：递归遍历叶子求和
5.生成哈夫曼编码：递归遍历，左 0 右 1
6.主函数测试：输入权值 → 建树 → WPL → 编码输出

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ===================== 1. 哈夫曼树节点定义 =====================
typedef struct HuffmanNode {
    char ch;          // 字符（叶子才有）
    int weight;       // 权值（频率）
    int parent;       // 父节点下标（数组实现方便）
    int lchild, rchild;
} HuffmanNode;

// ===================== 2. 哈夫曼编码结构体 =====================
typedef struct HuffmanCode {
    char ch;          // 字符
    char code[100];   // 编码串（01串）
} HuffmanCode;

// ===================== 3. 选两个权值最小的节点（核心） =====================
// 在 0~n-1 中找 parent=-1 的两个最小节点
void selectMin(HuffmanNode* HT, int n, int* s1, int* s2) {
    int i;
    // 找第一个最小 s1
    *s1 = -1;
    for (i = 0; i < n; i++) {
        if (HT[i].parent == -1) {
            if (*s1 == -1 || HT[i].weight < HT[*s1].weight)
                *s1 = i;
        }
    }
    // 找第二个最小 s2
    *s2 = -1;
    for (i = 0; i < n; i++) {
        if (HT[i].parent == -1 && i != *s1) {
            if (*s2 == -1 || HT[i].weight < HT[*s2].weight)
                *s2 = i;
        }
    }
}

// ===================== 4. 构造哈夫曼树 =====================
// n: 叶子数
void createHuffmanTree(HuffmanNode* HT, int n, int* weights, char* chars) {
    if (n <= 1) return;

    int totalNodes = 2 * n - 1;  // 总节点数固定：叶子n → 2n-1

    // 初始化所有节点
    for (int i = 0; i < totalNodes; i++) {
        HT[i].parent = HT[i].lchild = HT[i].rchild = -1;
        HT[i].weight = 0;
        HT[i].ch = 0;
    }

    // 初始化叶子节点（前n个）
    for (int i = 0; i < n; i++) {
        HT[i].weight = weights[i];
        HT[i].ch = chars[i];
    }

    // 开始合并 n-1 次
    for (int i = n; i < totalNodes; i++) {
        int s1, s2;
        selectMin(HT, i, &s1, &s2);  // 选两个最小

        // 建立父子关系
        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;
    }
}

// ===================== 5. 计算 WPL（递归） =====================
// index: 当前节点下标
// depth: 当前深度（路径长度）
int calcWPL(HuffmanNode* HT, int index, int depth) {
    // 叶子节点：weight * depth
    if (HT[index].lchild == -1 && HT[index].rchild == -1)
        return HT[index].weight * depth;

    // 非叶子：递归左右
    int leftWPL = calcWPL(HT, HT[index].lchild, depth + 1);
    int rightWPL = calcWPL(HT, HT[index].rchild, depth + 1);

    return leftWPL + rightWPL;
}

// ===================== 6. 生成哈夫曼编码（递归） =====================
void createHuffmanCode(HuffmanNode* HT, HuffmanCode* HC, int n) {
    char temp[100];  // 临时存编码
    temp[0] = '\0';

    // 对每个叶子生成编码
    for (int i = 0; i < n; i++) {
        int cur = i;
        int len = 0;
        int p = HT[cur].parent;

        // 从叶子回溯到根
        while (p != -1) {
            if (HT[p].lchild == cur)
                temp[len++] = '0';
            else
                temp[len++] = '1';
            cur = p;
            p = HT[cur].parent;
        }
        temp[len] = '\0';

        // 反转（因为回溯是逆序）
        strrev(temp);

        // 存入编码表
        HC[i].ch = HT[i].ch;
        strcpy(HC[i].code, temp);
    }
}

// ===================== 7. 打印编码 =====================
void printHuffmanCode(HuffmanCode* HC, int n) {
    printf("\n=== 哈夫曼编码表 ===\n");
    for (int i = 0; i < n; i++) {
        printf("%c : %s\n", HC[i].ch, HC[i].code);
    }
}

// ===================== 主函数测试 =====================
int main() {
    // 测试数据：5 个字符 + 权值
    int n = 5;
    char chars[] = {'a', 'b', 'c', 'd', 'e'};
    int weights[] = {1, 2, 3, 4, 5};  // 权值

    // 开辟哈夫曼树空间：2n-1 个节点
    HuffmanNode* HT = (HuffmanNode*)malloc(sizeof(HuffmanNode) * (2 * n - 1));
    // 编码表
    HuffmanCode* HC = (HuffmanCode*)malloc(sizeof(HuffmanCode) * n);

    // 建树
    createHuffmanTree(HT, n, weights, chars);

    // 计算 WPL（根是最后一个节点：2n-2）
    int wpl = calcWPL(HT, 2 * n - 2, 0);
    printf("WPL = %d\n", wpl);

    // 生成编码
    createHuffmanCode(HT, HC, n);
    printHuffmanCode(HC, n);

    free(HT);
    free(HC);
    return 0;
}