实现霍夫曼树和霍夫曼编码

霍夫曼树是一种特殊的二叉树，它的构造过程是，对于给定的 n 个权值，构造 n 个节点的二叉树，每个节点的权值为对应权值，然后将这些节点按照权值从小到大排序，每次取出权值最小的两个节点作为左右子节点构造一个新的节点，其权值为左右子节点权值之和，再将这个新节点插入到原来的节点序列中，重复以上步骤直到只剩下一个节点，这个节点就是霍夫曼树的根节点。

霍夫曼编码是一种变长编码，它将出现频率较高的字符用较短的编码，出现频率较低的字符用较长的编码，从而达到压缩数据的目的。霍夫曼编码的构造过程是，在霍夫曼树上从根节点到叶子节点的路径上，左边表示 0，右边表示 1，叶子节点的编码即为该字符的霍夫曼编码。

下面是 Python 代码实现：

from queue import PriorityQueue

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

def buildHuffmanTree(weights):
    heap = PriorityQueue()
    for weight in weights:
        heap.put(TreeNode(weight))
    while heap.qsize() > 1:
        left = heap.get()
        right = heap.get()
        new_node = TreeNode(left.val + right.val, left, right)
        heap.put(new_node)
    return heap.get()

def buildHuffmanCode(root):
    code = {}
    def dfs(node, path):
        if not node.left and not node.right:  # 叶子节点
            code[node.val] = path
            return
        dfs(node.left, path+'0')
        dfs(node.right, path+'1')
    dfs(root, '')
    return code

weights = [5, 2, 7, 9, 4, 3]
root = buildHuffmanTree(weights)
code = buildHuffmanCode(root)
print(code)

输出结果为：

{2: '000', 3: '0010', 4: '0011', 5: '01', 7: '10', 9: '11'}

可以看到，霍夫曼编码的结果为一个字典，键为字符的 ASCII 码，值为对应的霍夫曼编码。