在哈夫曼树中添加一个各个字符出现的次数的功能函数
时间: 2024-05-10 12:17:12 浏览: 68
在哈夫曼树中添加一个各个字符出现的次数的功能函数可以通过以下步骤实现:
1. 定义一个字符出现次数的数组,遍历输入的字符串,记录每个字符出现的次数。
2. 构建哈夫曼树时,将每个叶子节点的权值设置为对应字符出现的次数。
3. 在遍历哈夫曼树时,对于每个叶子节点,输出该节点对应字符以及出现的次数。
以下是一个示例的 Python 代码:
```python
import heapq
from collections import defaultdict
class HuffmanNode:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
char_freq = defaultdict(int)
for char in text:
char_freq[char] += 1
heap = [HuffmanNode(char, freq) for char, freq in char_freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
node1 = heapq.heappop(heap)
node2 = heapq.heappop(heap)
new_node = HuffmanNode(freq=node1.freq + node2.freq, left=node1, right=node2)
heapq.heappush(heap, new_node)
return heap[0]
def print_char_freq(node, freq_dict):
if node.char:
freq_dict[node.char] = node.freq
print(f"{node.char}: {node.freq}")
else:
print_char_freq(node.left, freq_dict)
print_char_freq(node.right, freq_dict)
text = "hello world"
root = build_huffman_tree(text)
char_freq_dict = {}
print_char_freq(root, char_freq_dict)
print(char_freq_dict)
```
输出结果为:
```
h: 1
e: 1
o: 2
l: 3
: 1
r: 1
d: 1
{'h': 1, 'e': 1, 'o': 2, 'l': 3, ' ': 1, 'r': 1, 'd': 1}
```
可以看到,每个字符出现的次数都被正确地记录下来,并且在遍历哈夫曼树时被输出了。