Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/13.哈夫曼树.md

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

#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++

#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

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

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)