生成哈夫曼树 python

生成哈夫曼树是一种常用的数据结构和算法，用于实现数据的压缩和编码。下面是生成哈夫曼树的基本步骤：

1. 统计字符频率：遍历待编码的文本或数据，统计每个字符出现的频率。

2. 构建叶子节点：将每个字符及其频率作为一个叶子节点。

3. 构建哈夫曼树：从频率最低的两个节点开始，合并它们并创建一个新的父节点，该父节点的频率为两个子节点的频率之和。将新的父节点插入到节点集合中，并删除原来的两个子节点。重复这个过程，直到只剩下一个根节点。

4. 生成编码表：从根节点开始，遍历哈夫曼树的路径，左子树为0，右子树为1，将每个字符对应的编码保存在编码表中。

5. 进行编码：根据生成的编码表，将原始文本或数据中的每个字符替换为对应的编码。

6. 进行解码：使用生成的哈夫曼树和编码表，将编码后的数据逐个解码为原始字符。

下面是一个简单的Python代码示例来生成哈夫曼树：

import heapq
from collections import defaultdict

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

def build_huffman_tree(text):
    # 统计字符频率
    freq_dict = defaultdict(int)
    for char in text:
        freq_dict[char] += 1

    # 构建叶子节点
    nodes = []
    for char, freq in freq_dict.items():
        nodes.append(Node(char, freq))

    # 构建哈夫曼树
    heapq.heapify(nodes)
    while len(nodes) > 1:
        left_node = heapq.heappop(nodes)
        right_node = heapq.heappop(nodes)
        parent_node = Node(None, left_node.freq + right_node.freq)
        parent_node.left = left_node
        parent_node.right = right_node
        heapq.heappush(nodes, parent_node)

    return nodes

# 示例用法
text = "hello world"
huffman_tree = build_huffman_tree(text)