哈夫曼树的实现python

哈夫曼树（Huffman Tree）又称最优二叉树（Optimal Binary Tree），是一种带权路径长度最短的二叉树。哈夫曼树通常用于数据压缩，即将一些字符按照出现频率进行编码，使编码后的数据占用空间更小。

哈夫曼树的构造过程类似于贪心算法，即每次选择权值最小的两个节点进行合并，直至所有节点合并完成。

下面介绍一种常见的哈夫曼树构造算法：

1. 将待构造哈夫曼树的节点按权值从小到大排序，依次存放在一个列表中；

2. 从列表中选择权值最小的两个节点，将它们合并为一个新节点，并将这个新节点的权值设为两个合并的节点的权值之和；

3. 将新节点插入到列表中，并保持列表的有序性；

4. 重复步骤2和3，直至列表中仅剩一个节点，即为哈夫曼树的根节点。

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

```python

class Node:

def __init__(self, val, weight=None):

self.val = val

self.weight = weight

self.left = None

self.right = None

class HuffmanTree:

def __init__(self, freq_dict):

self.freq_dict = freq_dict

def _build_tree(self):

nodes = [Node(val=k,weight=v) for k,v in self.freq_dict.items()]

while len(nodes) > 1:

nodes.sort(key=lambda x:x.weight)

left_node = nodes.pop(0)

right_node = nodes.pop(0)

new_node = Node(None, weight=left_node.weight+right_node.weight)

new_node.left, new_node.right = left_node, right_node

nodes.append(new_node)

return nodes[0]

def _traverse_tree(self, node, code='', code_dict={}):

if node is None:

return code_dict

if node.val is not None:

code_dict[node.val] = code

code_dict = self._traverse_tree(node.left, code+'0', code_dict)

code_dict = self._traverse_tree(node.right, code+'1', code_dict)

return code_dict

def encode(self, data):

root = self._build_tree()

code_dict = self._traverse_tree(root)

encoded_data = ''

for char in data:

encoded_data += code_dict[char]

return encoded_data

def decode(self, encoded_data):

root = self._build_tree()

node = root

decoded_data = ''

for bit in encoded_data:

if bit == '0':

node = node.left

else:

node = node.right

if node.val is not None:

decoded_data += node.val

node = root

return decoded_data

```

上述代码中，`Node`类表示哈夫曼树的节点，包括节点值（在本例中与字符相对应）和节点权值；`HuffmanTree`类实现了哈夫曼树的构造、编码和解码方法。构造方法以一个字典为输入，字典中记录每个字符出现的频率；编码方法以一个字符串为输入，返回对该字符串进行哈夫曼编码后的二进制字符串；解码方法以一个二进制字符串为输入，返回解码后的原始字符串。

下面是一个使用哈夫曼树压缩字符串的示例：

```python

if __name__ == '__main__':

data = 'hello world'

freq_dict = {}

for char in data:

if char in freq_dict:

freq_dict[char] += 1

else:

freq_dict[char] = 1

huffman_tree = HuffmanTree(freq_dict)

encoded_data = huffman_tree.encode(data)

print('Encoded data:', encoded_data)

decoded_data = huffman_tree.decode(encoded_data)

print('Decoded data:', decoded_data)

```

在上述示例中，输入的字符串为`hello world`，首先统计每个字符出现的频率，然后使用`HuffmanTree`类进行哈夫曼编码，并输出编码后的二进制字符串和解码后的原始字符串。可以看到，编码后的字符串比原始字符串短很多，达到了压缩的效果。

总结一下，哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。Python中可以使用类的方式实现哈夫曼树的构造、编码和解码方法，并通过字典存储字符的出现频率实现字符串的压缩和解压缩。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/