哈夫曼树及哈夫曼编码 算法python,权重待输入

好的，下面是用 Python 实现的哈夫曼树和哈夫曼编码算法：

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

def huffman_encoding(weights):
    nodes = [Node(weight=w) for w in weights]
    while len(nodes) > 1:
        nodes = sorted(nodes, key=lambda x: x.weight)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(weight=left.weight + right.weight, left=left, right=right)
        nodes.append(parent)
    root = nodes[0]

    def encode(node, code=''):
        if not node.left and not node.right:
            yield (node.weight, code)
        else:
            yield from encode(node.left, code + '0')
            yield from encode(node.right, code + '1')

    codes = dict(encode(root))
    encoded = ''.join(codes[w] for w in weights)
    return encoded, codes

def huffman_decoding(encoded, codes):
    rev_codes = {v: k for k, v in codes.items()}
    code = ''
    decoded = []
    for bit in encoded:
        code += bit
        if code in rev_codes:
            decoded.append(rev_codes[code])
            code = ''
    return decoded

其中，`Node` 类表示哈夫曼树的一个节点，`huffman_encoding` 函数接受一个权重列表作为输入，返回编码后的二进制字符串和对应的编码表，`huffman_decoding` 函数接受编码后的二进制字符串和编码表作为输入，返回解码后的权重列表。

你可以使用以下代码来测试：

weights = list(map(int, input().split()))
encoded, codes = huffman_encoding(weights)
print('Encoded:', encoded)
print('Codes:', codes)
decoded = huffman_decoding(encoded, codes)
print('Decoded:', decoded)

在运行时，你需要输入一个空格隔开的权重列表，例如：

3 1 4 1 5 9 2 6 5 3 5

输出将包括编码后的二进制字符串和对应的编码表，以及解码后的权重列表。