掌握哈夫曼树、哈夫曼编码的概念和基本理论，设计实现哈夫曼编码。

哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于编码。哈夫曼编码（Huffman Coding）是一种编码方式，通过将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而达到压缩数据的目的。

哈夫曼树的构建过程如下：

1. 给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，则这棵二叉树被称为最优二叉树，也称为哈夫曼树。
2. 权值较小的节点离根较近。

哈夫曼编码的构建过程如下：

1. 统计每个字符出现的频率。
2. 根据字符出现频率构建哈夫曼树。
3. 左子树上的节点编码为0，右子树上的节点编码为1。
4. 从根节点开始遍历哈夫曼树，每经过一个节点就记录下对应的编码，直到叶子节点，得到该字符的哈夫曼编码。

下面是Python实现哈夫曼编码的示例代码：

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

def encode(s):
    # 统计字符出现频率
    freq = defaultdict(int)
    for c in s:
        freq[c] += 1

    # 构建哈夫曼树
    h = [[freq[c], c] for c in freq]
    heapify(h)
    while len(h) > 1:
        a = heappop(h)
        b = heappop(h)
        heappush(h, [a[0]+b[0], [a[1], b[1]]])

    # 构建字符编码表
    code = {}
    def build_code(node, prefix=""):
        if type(node) is str:
            code[node] = prefix
        else:
            build_code(node[0], prefix+"0")
            build_code(node[1], prefix+"1")
    build_code(h[0][1])

    # 编码字符串
    encoded = "".join(code[c] for c in s)

    return encoded, code

def decode(encoded, code):
    # 构建反向字符编码表
    decode = {v:k for k,v in code.items()}

    # 解码字符串
    current_code = ""
    decoded = ""
    for bit in encoded:
        current_code += bit
        if current_code in decode:
            decoded += decode[current_code]
            current_code = ""

    return decoded

使用示例：

s = "hello world!"
encoded, code = encode(s)
print("Encoded:", encoded)
print("Code:", code)
decoded = decode(encoded, code)
print("Decoded:", decoded)

输出结果：

Encoded: 1000111010011111111001000100001011011
Code: {' ': '10', '!': '11010', 'd': '1111', 'e': '001', 'h': '1100', 'l': '100', 'o': '011', 'r': '11011', 'w': '1110'}
Decoded: hello world!