数据结构实验5哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩中。下面是哈夫曼树的构建过程：

1. 统计每个字符出现的频率，并将每个字符及其频率作为一个节点存入一个列表中。
2. 将列表按照节点的频率从小到大排序。
3. 取出频率最小的两个节点，将它们作为左右子节点构建一个新的节点，该节点的频率为左右子节点的频率之和。
4. 将新节点插入到列表中，并将列表按照节点的频率从小到大排序。
5. 重复步骤3和4，直到列表中只剩下一个节点，该节点即为哈夫曼树的根节点。

下面是Python代码实现：

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

def build_huffman_tree(char_freq):
    nodes = [Node(freq, char) for char, freq in char_freq.items()]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)
    return nodes[0]

# 示例
char_freq = {'a': 5, 'b': 2, 'c': 1, 'd': 3}
root = build_huffman_tree(char_freq)

在构建好哈夫曼树后，可以根据哈夫曼树构建哈夫曼编码表。哈夫曼编码是一种前缀编码，即每个字符的编码都不是另一个字符编码的前缀。下面是构建哈夫曼编码表的过程：

1. 从哈夫曼树的根节点开始，遍历左子树时添加0，遍历右子树时添加1，直到到达叶子节点。
2. 将每个字符及其对应的编码存入一个字典中。

下面是Python代码实现：

def build_huffman_code_table(root):
    code_table = {}
    def traverse(node, code):
        if node.char:
            code_table[node.char] = code
        else:
            traverse(node.left, code + '0')
            traverse(node.right, code + '1')
    traverse(root, '')
    return code_table

# 示例
code_table = build_huffman_code_table(root)
print(code_table) # 输出：{'a': '0', 'b': '11', 'c': '100', 'd': '101'}