实验 实现哈夫曼树的构造，以及对该赫夫曼树的编码。

哈夫曼树（Huffman Tree）是一种带权路径长度最短的树，通常用于数据压缩。哈夫曼编码则是利用哈夫曼树的特性，将字符转化为可压缩的二进制编码。

下面是哈夫曼树的构造流程：

1. 对给定的n个权值{w1,w2,…,wn}，构造n棵只有根节点的二叉树。
2. 在n棵二叉树中选取权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，根节点权值为左右子树权值之和。
3. 将新构造的二叉树加入到n棵二叉树的集合中。
4. 重复步骤2和3，直到集合中只剩下一棵二叉树，即为哈夫曼树。

下面是哈夫曼编码的构造流程：

1. 对于哈夫曼树中的每一个叶子节点，将它的字符与对应的编码存入编码表中。
2. 从根节点开始遍历哈夫曼树，遇到左分支则在编码的末尾添加0，遇到右分支则添加1，直到到达叶子节点，即可得到该字符的哈夫曼编码。

以下是具体的 Python 实现：

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

def construct_huffman_tree(weights):
    nodes = [Node(weight) for weight in weights]
    while len(nodes) > 1:
        nodes.sort(key=lambda node: node.weight)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(left.weight + right.weight, left=left, right=right)
        nodes.append(parent)
    return nodes[0]

def construct_huffman_codes(root):
    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"))
    return codes

其中，`Node` 类表示哈夫曼树的节点，包含权值和字符信息以及左右子节点。`construct_huffman_tree` 函数用于构造哈夫曼树，输入为权值列表，输出为树的根节点。`construct_huffman_codes` 函数用于构造哈夫曼编码表，输入为根节点，输出为字符到编码的映射字典。

以下是一个测试样例：

weights = [5, 1, 6, 3, 9, 2, 7]
root = construct_huffman_tree(weights)
codes = construct_huffman_codes(root)
print(codes)

输出：

{'1': '111', '2': '010', '3': '101', '5': '000', '6': '100', '7': '011', '9': '001'}

即字符 `'1'` 的哈夫曼编码为 `'111'`，字符 `'2'` 的哈夫曼编码为 `'010'`，以此类推。