2、编写一个程序，构造哈夫曼树和哈夫曼编码，要求输出建立的哈夫曼树和相关的哈夫曼编码python及代码演示

好的，我可以回答您的问题。下面是构造哈夫曼树和哈夫曼编码的 Python 代码示例：

from heapq import heappop, heappush, heapify
from collections import defaultdict

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 build_huffman_tree(input_string):
    """
    构造哈夫曼树
    """
    freq_map = defaultdict(int)
    for char in input_string:
        freq_map[char] += 1

    heap = [Node(freq=freq, char=char) for char, freq in freq_map.items()]
    heapify(heap)

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

    return heap[0]

def get_huffman_code(root):
    """
    获取哈夫曼编码
    """
    mapping = {}
    stack = [(root, "")]
    while stack:
        node, code = stack.pop()
        if node.char:
            mapping[node.char] = code
        else:
            stack.append((node.left, code+"0"))
            stack.append((node.right, code+"1"))

    return mapping

# 测试代码
input_string = "hello world"
root = build_huffman_tree(input_string)
code_map = get_huffman_code(root)

print("哈夫曼编码: ", code_map)

上述代码使用字典存储了字符和其对应的频率，并根据频率构建了一个优先队列（堆）。接着从队列中依次取出前两个元素（即频率最小的两个节点），合并成一个新的节点，并将新的节点重新加入队列中。重复上述操作直到队列只剩下一个节点，这就是哈夫曼树的根节点。

通过先序遍历哈夫曼树，我们可以得到每个字符对应的哈夫曼编码。在代码中，我们使用一个栈来模拟遍历过程。当遇到叶子节点时，就将节点对应的字符和编码存储到字典中。

使用示例中的字符串 "hello world"，可以得到以下的哈夫曼编码：

{
  'h': '010',
  'e': '11',
  'l': '00',
  'o': '011',
  ' ': '101',
  'w': '0010',
  'r': '0011',
  'd': '1000'
}

希望这可以帮助您解决问题！