用python写一个哈夫曼树

好的，下面是用 Python 实现一个哈夫曼树的示例代码：

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 __eq__(self, other):
        if other is None:
            return False
        if not isinstance(other, Node):
            return False
        return self.freq == other.freq


def build_huffman_tree(data):
    frequency = {}
    for char in data:
        if char in frequency:
            frequency[char] += 1
        else:
            frequency[char] = 1

    nodes = []
    for char, freq in frequency.items():
        nodes.append(Node(freq, char))

    heapq.heapify(nodes)

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

    return nodes[0]


def build_huffman_codes(node, current_code="", codes={}):
    if node is None:
        return

    if node.char is not None:
        codes[node.char] = current_code

    build_huffman_codes(node.left, current_code + "0", codes)
    build_huffman_codes(node.right, current_code + "1", codes)

    return codes


if __name__ == "__main__":
    data = "hello world"
    root = build_huffman_tree(data)
    codes = build_huffman_codes(root)

    print("Huffman Codes: ", codes)

解释一下代码：

首先，定义了一个 `Node` 类，用于表示哈夫曼树中的节点。节点包括字符的频率、字符本身、左右子节点。实现了 `<` 和 `==` 操作符，以便后面使用堆进行优先队列的实现。

然后，定义了 `build_huffman_tree` 函数，它接受一个字符串 `data` 作为输入，返回构建出来的哈夫曼树的根节点。

在 `build_huffman_tree` 函数中，首先统计了每个字符出现的频率，并将其封装成 `Node` 对象。然后使用堆进行优先队列的实现，不断取出两个频率最小的节点，构建父节点，最终得到哈夫曼树的根节点。

接下来，定义了 `build_huffman_codes` 函数，它接受一个哈夫曼树的根节点 `node`，以及当前节点的编码 `current_code` 和编码表 `codes`。递归地遍历哈夫曼树，对于叶子节点，将其字符的编码存储到编码表中。

最后，在 `if __name__ == "__main__"` 代码块中，演示了如何使用上述函数来构建哈夫曼编码。