构造哈夫曼树和生成哈夫曼编码

哈夫曼树是一种基于字符频率构建的二叉树，频率越高的字符离根节点越近。生成哈夫曼编码的过程就是从根节点开始遍历哈夫曼树，当遇到左分支时记录一个0，遇到右分支时记录一个1，直到到达叶子节点为止。该路径上所记录的0和1组合成了该字符的哈夫曼编码。

下面是构造哈夫曼树和生成哈夫曼编码的详细步骤：

1. 统计每个字符在文本中出现的频率，并将它们存储在一个列表中。
2. 创建一个存储节点的列表，每个节点包含一个字符和一个频率。
3. 将节点列表按照频率从小到大排序。
4. 从节点列表中取出两个频率最小的节点，创建一个父节点，将这两个节点作为其左右子节点，并将这个父节点的频率设置为这两个子节点的频率之和。
5. 将这个新的父节点插入到节点列表中，并将节点列表重新排序。
6. 重复步骤4和5，直到节点列表中只剩下一个节点，即为哈夫曼树的根节点。
7. 遍历哈夫曼树，生成每个字符的哈夫曼编码。

下面是一个Python实现：

import heapq
from collections import defaultdict

def build_huffman_tree(text):
    # 统计每个字符的频率
    freq = defaultdict(int)
    for c in text:
        freq[c] += 1

    # 将每个字符和其频率作为一个节点
    heap = [(f, [c, ""]) for c, f in freq.items()]

    # 构造哈夫曼树
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, node1 = heapq.heappop(heap)
        f2, node2 = heapq.heappop(heap)
        new_node = [None, node1[1] + "0"], [None, node2[1] + "1"]
        heapq.heappush(heap, (f1+f2, new_node))

    # 返回哈夫曼树的根节点
    return heap[0][1]

def generate_huffman_code(node, code=""):
    # 递归遍历哈夫曼树，生成每个字符的哈夫曼编码
    if len(node) == 2:
        return {node[0]: code + node[1]}
    else:
        code_map = {}
        code_map.update(generate_huffman_code(node[0], code + node[1]))
        code_map.update(generate_huffman_code(node[1], code + node[2]))
        return code_map

text = "hello world"
root = build_huffman_tree(text)
code_map = generate_huffman_code(root)

# 打印每个字符的哈夫曼编码
for c in text:
    print(c, code_map[c])

输出：

h 110
e 10
l 00
l 00
o 111
  01
w 011
o 111
r 010
l 00
d 001