哈夫曼树数据结构课程设计

针对哈夫曼树数据结构的课程设计，主要包括以下几个步骤：

1. 统计每个字符出现的次数，构建哈夫曼树

# 定义节点类
class Node:
    def __init__(self, value, freq):
        self.value = value
        self.freq = freq
        self.left = None
        self.right = None

# 构建哈夫曼树
def build_huffman_tree(char_freq):
    nodes = [Node(key, value) for key, value in char_freq.items()]
    while len(nodes) > 1:
        nodes = sorted(nodes, key=lambda x: x.freq)
        left_node = nodes.pop(0)
        right_node = nodes.pop(0)
        new_node = Node(None, left_node.freq + right_node.freq)
        new_node.left = left_node
        new_node.right = right_node
        nodes.append(new_node)
    return nodes[0]

2. 计算每个字符的哈夫曼编码

# 计算哈夫曼编码
def get_huffman_code(root):
    huffman_code = {}
    def dfs(node, code):
        if node.value:
            huffman_code[node.value] = code
            return
        dfs(node.left, code + '0')
        dfs(node.right, code + '1')

    dfs(root, '')
    return huffman_code

3. 对字符串进行编码和译码

# 编码
def encode_string(string, huffman_code):
    encoded_string = ''
    for char in string:
        encoded_string += huffman_code[char]
    return encoded_string

# 译码
def decode_string(encoded_string, root):
    decoded_string = ''
    node = root
    for bit in encoded_string:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if node.value:
            decoded_string += node.value
            node = root
    return decoded_string