给出创建哈夫曼树的测试代码
时间: 2023-12-13 19:57:14 浏览: 34
以下是一个简单的Python实现哈夫曼树的代码:
```python
import heapq
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 huffman_tree(data):
freq_dict = defaultdict(int)
for char in data:
freq_dict[char] += 1
heap = []
for char, freq in freq_dict.items():
heapq.heappush(heap, Node(freq, char))
while len(heap) > 1:
node1 = heapq.heappop(heap)
node2 = heapq.heappop(heap)
merged = Node(node1.freq + node2.freq)
merged.left = node1
merged.right = node2
heapq.heappush(heap, merged)
return heap[0]
root = huffman_tree("hello world")
```
在这个例子中,我们使用了一个字典 `freq_dict` 来记录每个字符在输入字符串中出现的频率。然后,我们使用 Python 的堆队列模块 `heapq` 来维护一个最小堆,其中每个节点都是 `Node` 对象。在哈夫曼树的构建过程中,我们每次从堆中弹出两个节点,将它们合并成一个新的节点,并将这个新节点插入回堆中。最后,堆中剩下的那个节点就是哈夫曼树的根节点。
需要注意的是,在这个例子中,我们使用了 Python 的默认比较函数 `__lt__` 来定义 `Node` 对象之间的大小关系。这个函数会根据节点的频率来进行比较。这里我们假设输入字符串只包含 ASCII 字符,因此可以用字符本身来表示叶子节点。如果要处理 Unicode 字符,需要修改代码以支持更多的字符集。