编写一个程序，构造哈夫曼树和哈夫曼编码，要求输出建立的哈夫曼树和相关的哈夫曼编码

好的，我已经记录下了您的要求。以下是构造哈夫曼树和哈夫曼编码的程序示例：

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

def construct_huffman_tree(data):
    # 统计字符频率
    freq_dict = {}
    for char in data:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    # 将字符和频率封装成节点
    nodes = [Node(char, freq) for char, freq in freq_dict.items()]
    # 构造哈夫曼树
    while len(nodes) > 1:
        nodes.sort(key=lambda node: node.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(None, left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)
    # 返回根节点
    return nodes[0]

def construct_huffman_code(root):
    # 递归构造哈夫曼编码
    code_dict = {}
    def traverse(node, code):
        if node.char is not None:
            code_dict[node.char] = code
        if node.left is not None:
            traverse(node.left, code + '0')
        if node.right is not None:
            traverse(node.right, code + '1')
    traverse(root, '')
    return code_dict

if __name__ == '__main__':
    data = 'abacabad'
    root = construct_huffman_tree(data)
    code_dict = construct_huffman_code(root)
    for char, code in code_dict.items():
        print(f'Char: {char}, Code: {code}')

以上程序中，`Node`类表示哈夫曼树中的节点，包含字符、频率、左子树和右子树；`construct_huffman_tree`函数用于构造哈夫曼树，并返回根节点；`construct_huffman_code`函数用于根据哈夫曼树构造哈夫曼编码，并以字典形式返回字符和对应的编码。在最后的测试代码中，我们对字符串 `'abacabad'` 进行哈夫曼编码，然后输出字符和对应的编码。