PTA 7-2哈夫曼编码python

以下是PTA 7-2哈夫曼编码的Python实现：

from heapq import heapify, heappush, heappop

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

    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1

    heap = [Node(f, c) for c, f in freq.items()]
    heapify(heap)

    while len(heap) > 1:
        left = heappop(heap)
        right = heappop(heap)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        heappush(heap, parent)

    root = heap[0]
    codes = {}
    stack = [(root, "")]
    while stack:
        node, code = stack.pop()
        if node.char:
            codes[node.char] = code
        if node.left:
            stack.append((node.left, code + "0"))
        if node.right:
            stack.append((node.right, code + "1"))

    encoded = "".join(codes[c] for c in s)
    return encoded, codes

def huffman_decoding(encoded, codes):
    decoded = ""
    i = 0
    while i < len(encoded):
        for c, code in codes.items():
            if encoded[i:i+len(code)] == code:
                decoded += c
                i += len(code)
                break
    return decoded

s = input().strip()
encoded, codes = huffman_encoding(s)
print(encoded)
print(huffman_decoding(encoded, codes))