# 13. 哈夫曼树

## 概念

**哈夫曼树（Huffman Tree）**，也叫**最优二叉树**，是一种**带权路径长度最短**的二叉树。

**WPL（带权路径长度，Weighted Path Length）**：树中所有**叶子结点**的权值与它到根的**路径长度（层数-1）**的乘积之和，即

```
WPL = Σ (w_i × l_i)
```

其中 w_i 是第 i 个叶子权值，l_i 是它的路径长度。哈夫曼树就是使 WPL 达到**最小**的二叉树。

**哈夫曼算法（构造过程）**：

1. 把所有权值看作 n 棵**只有根结点的树**（每棵是一棵树，根为权值，视为叶子）；
2. **每次取两棵权值最小的树**合并，生成一个新结点作为它们的父结点，新结点权值 = 两者之和；
3. 把新树放回集合；
4. 重复步骤 2~3，直到只剩一棵树，即得到哈夫曼树。

**哈夫曼编码**：给哈夫曼树中的**左分支标 0、右分支标 1**，从根到某个叶子的路径上的 0/1 序列，就是该叶子权值对应的**哈夫曼编码**。

- **前缀编码**：因为每个字符都是叶子结点，任何字符的编码都**不会是另一个字符编码的前缀**，因此可以无歧义地从二进制串中解码。
- **为什么能压缩**：哈夫曼编码让**出现频率高（权值大）的字符编码短、频率低的编码长**，平均码长最短，从而压缩数据量。WPL 最小 ⇔ 平均编码长度最小。

**适用场景**：数据压缩（ZIP、JPEG 等）、无损编码、最优判定树、最优归并顺序等。

## 核心操作

- **建哈夫曼树**：用**最小堆（优先队列）**反复取出权值最小的两个结点合并，新结点权值为两子树权值和，再压回堆，直到堆中只剩一个结点。也可用排序每次取最小两个，但用最小堆更高效。
- **生成哈夫曼编码**：对建好的哈夫曼树做**前序遍历**（根-左-右），左走记 0、右走记 1，到达叶子时记录该叶子的编码。

## 复杂度分析

| 操作                       | 时间复杂度 | 空间复杂度                     |
| -------------------------- | ---------- | ------------------------------ |
| 建哈夫曼树                 | O(n log n) | O(n)                           |
| 生成哈夫曼编码（前序遍历） | O(n)       | O(n)（编码表）+ O(树高) 递归栈 |

**为什么**：建树需要做 n-1 次合并，每次从最小堆中取出两个最小元素并插入一个新元素，堆操作各为 O(log n)，故总 O(n log n)。若用"每次排序取最小两个"则更慢（O(n²)）。生成编码是遍历整棵树，访问 n 个叶子，为 O(n)；编码表存储 n 个叶子编码，总长度 O(n log n) 量级。空间主要用于存储 n 个结点与最小堆，为 O(n)。

## 语言实现

下面是 4 种语言的完整实现，均演示：给定一组权值（如字符出现频率），用**最小堆/优先队列**构建哈夫曼树，并用前序遍历生成并输出每个权值的哈夫曼编码。

### C

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

// 哈夫曼树结点
typedef struct HTNode {
    int weight;            // 权值
    char code[64];         // 编码（仅在叶子使用）
    struct HTNode *left, *right;
} HTNode;

// 最小堆（按权值排序）
typedef struct {
    HTNode **data;
    int size, cap;
} MinHeap;

MinHeap *createHeap(int cap) {
    MinHeap *h = (MinHeap *)malloc(sizeof(MinHeap));
    h->data = (HTNode **)malloc(sizeof(HTNode *) * cap);
    h->size = 0;
    h->cap = cap;
    return h;
}

void swap(HTNode **a, HTNode **b) { HTNode *t = *a; *a = *b; *b = t; }

void siftDown(MinHeap *h, int i) {
    int smallest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < h->size && h->data[l]->weight < h->data[smallest]->weight) smallest = l;
    if (r < h->size && h->data[r]->weight < h->data[smallest]->weight) smallest = r;
    if (smallest != i) {
        swap(&h->data[i], &h->data[smallest]);
        siftDown(h, smallest);
    }
}

void siftUp(MinHeap *h, int i) {
    while (i > 0 && h->data[(i - 1) / 2]->weight > h->data[i]->weight) {
        swap(&h->data[(i - 1) / 2], &h->data[i]);
        i = (i - 1) / 2;
    }
}

void push(MinHeap *h, HTNode *node) {
    h->data[h->size] = node;
    siftUp(h, h->size);
    h->size++;
}

HTNode *pop(MinHeap *h) {
    HTNode *top = h->data[0];
    h->data[0] = h->data[h->size - 1];
    h->size--;
    siftDown(h, 0);
    return top;
}

HTNode *newNode(int w) {
    HTNode *n = (HTNode *)malloc(sizeof(HTNode));
    n->weight = w;
    n->left = n->right = NULL;
    n->code[0] = '\0';
    return n;
}

// 建哈夫曼树
HTNode *buildHuffman(int *w, int n) {
    MinHeap *h = createHeap(n * 2);
    for (int i = 0; i < n; i++) push(h, newNode(w[i]));

    while (h->size > 1) {
        HTNode *a = pop(h);
        HTNode *b = pop(h);
        HTNode *parent = newNode(a->weight + b->weight);
        parent->left = a;
        parent->right = b;
        push(h, parent);
    }
    return pop(h);
}

// 前序遍历生成哈夫曼编码：左0 右1
void generateCodes(HTNode *node, char *path, int depth) {
    if (!node) return;
    // 叶子：记录编码并输出
    if (!node->left && !node->right) {
        path[depth] = '\0';
        strcpy(node->code, path);
        printf("权值 %d -> 编码 %s\n", node->weight, path);
        return;
    }
    path[depth] = '0';
    generateCodes(node->left, path, depth + 1);
    path[depth] = '1';
    generateCodes(node->right, path, depth + 1);
}

int main() {
    int weights[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("权值: ");
    for (int i = 0; i < n; i++) printf("%d ", weights[i]);
    printf("\n");

    HTNode *root = buildHuffman(weights, n);
    char path[64];
    printf("哈夫曼编码:\n");
    generateCodes(root, path, 0);
    return 0;
}
```

### C++

```C++
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

// 哈夫曼树结点
struct Node {
    int weight;
    string code;
    Node *left, *right;
    Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// 比较器：最小堆
struct Compare {
    bool operator()(Node *a, Node *b) { return a->weight > b->weight; }
};

// 建哈夫曼树
Node *buildHuffman(const vector<int>& weights) {
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int w : weights) pq.push(new Node(w));

    while (pq.size() > 1) {
        Node *a = pq.top(); pq.pop();
        Node *b = pq.top(); pq.pop();
        Node *parent = new Node(a->weight + b->weight);
        parent->left = a;
        parent->right = b;
        pq.push(parent);
    }
    return pq.top();
}

// 前序遍历生成编码
void generateCodes(Node *node, string path) {
    if (!node) return;
    if (!node->left && !node->right) {
        node->code = path;
        cout << "权值 " << node->weight << " -> 编码 " << path << endl;
        return;
    }
    generateCodes(node->left, path + "0");
    generateCodes(node->right, path + "1");
}

int main() {
    vector<int> weights = {5, 9, 12, 13, 16, 45};
    cout << "权值: ";
    for (int w : weights) cout << w << " ";
    cout << endl;

    Node *root = buildHuffman(weights);
    cout << "哈夫曼编码:" << endl;
    generateCodes(root, "");
    return 0;
}
```

### Java

```java
import java.util.PriorityQueue;

public class Huffman {

    // 结点
    static class Node {
        int weight;
        String code = "";
        Node left, right;
        Node(int w) { weight = w; }
    }

    // 建哈夫曼树：优先队列（最小堆）
    static Node buildHuffman(int[] weights) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        for (int w : weights) pq.offer(new Node(w));

        while (pq.size() > 1) {
            Node a = pq.poll();
            Node b = pq.poll();
            Node parent = new Node(a.weight + b.weight);
            parent.left = a;
            parent.right = b;
            pq.offer(parent);
        }
        return pq.poll();
    }

    // 前序遍历生成编码：左0 右1
    static void generateCodes(Node node, String path) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            node.code = path;
            System.out.println("权值 " + node.weight + " -> 编码 " + path);
            return;
        }
        generateCodes(node.left, path + "0");
        generateCodes(node.right, path + "1");
    }

    public static void main(String[] args) {
        int[] weights = {5, 9, 12, 13, 16, 45};
        System.out.print("权值: ");
        for (int w : weights) System.out.print(w + " ");
        System.out.println();

        Node root = buildHuffman(weights);
        System.out.println("哈夫曼编码:");
        generateCodes(root, "");
    }
}
```

### Python

```python
import heapq
from collections import namedtuple


class Node:
    """哈夫曼树结点"""
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right
        self.code = ""


def build_huffman(weights):
    """用最小堆构建哈夫曼树，返回根结点"""
    # 用 (weight, 自增序号) 避免两个相等权值比较结点时报错
    counter = 0
    heap = []
    for w in weights:
        heapq.heappush(heap, (w, counter, Node(w)))
        counter += 1

    while len(heap) > 1:
        _, _, a = heapq.heappop(heap)
        _, _, b = heapq.heappop(heap)
        parent = Node(a.weight + b.weight, a, b)
        heapq.heappush(heap, (parent.weight, counter, parent))
        counter += 1
    return heap[0][2]


def generate_codes(node, path=""):
    """前序遍历生成哈夫曼编码：左0 右1"""
    if node is None:
        return
    if node.left is None and node.right is None:
        node.code = path
        print(f"权值 {node.weight} -> 编码 {path}")
        return
    generate_codes(node.left, path + "0")
    generate_codes(node.right, path + "1")


if __name__ == "__main__":
    weights = [5, 9, 12, 13, 16, 45]
    print("权值:", weights)

    root = build_huffman(weights)
    print("哈夫曼编码:")
    generate_codes(root)
```