Python实现霍夫曼树

Python实现霍夫曼树Python 实现霍夫曼树 霍夫曼树是一种特殊的二叉树 是一种带权路径长度最短的二叉树 又称为最优二叉树 给定 N 个权值作为二叉树的 N 个叶节点的权值 构造一棵二叉树 若该二叉树的带权路径长度达到最小 则称该二叉树为霍夫曼树 霍夫曼树中权值越大的节点离根越近

大家好,我是讯享网,很高兴认识大家。

Python实现霍夫曼树

霍夫曼树是一种特殊的二叉树,是一种带权路径长度最短的二叉树,又称为最优二叉树。

给定 N 个权值作为二叉树的 N 个叶节点的权值,构造一棵二叉树,若该二叉树的带权路径长度达到最小,则称该二叉树为霍夫曼树。

霍夫曼树中权值越大的节点离根越近。

霍夫曼树主要应用于信息编码和数据压缩领域,是现代压缩算法的基础。

一、霍夫曼树的相关术语

霍夫曼树要满足带权路径长度最小,那就要知道什么是权值?什么是路径?什么是带权路径长度?

1. 路径

在一棵树中,从一个节点往下可以到达子节点或子孙节点的通路,称为路径。


讯享网

2. 节点的权值

在具体的应用场景中,二叉树的每个节点对应着具体的业务含义,每个节点有不同的权重,节点的权重值被称为节点的权值。

如下图中节点C的权值为5。

3. 节点的路径长度

根节点处于二叉树的第1层,则二叉树中第L层的节点的路径长度为 L-1 。

如上图中节点 F 处于二叉树的第三层,则 F 的路径长度为 3-1 = 2 。

节点的路径长度也可以这么理解,如果每个节点到达它的子节点的路径记为一个路径单元,则从根节点开始,到达某节点的路径单元数称为该节点的路径长度。

4. 节点的带权路径长度

节点的权值与节点的路径长度的乘积称为该节点的带权路径长度。

如上图中节点 D 的权值为 18、路径长度为 2,则节点 D 的带权路径长度为 18*2 = 36。

5. 树的带权路径长度

树的所有叶节点的带权路径长度之和,称为树的带权路径长度,记为WPL(Weighted Path Length of Tree)。

如上图中的二叉树的带权路径长度为 WPL = 18*2 + 7*2 + 6*2 + 17*2 = 96

二、霍夫曼树的构造过程

给定 N 个权值作为二叉树的 N 个叶节点的权值,构造一棵二叉树,可以构建出多种不同结构的二叉树,不同结构的二叉树的带权路径长度不一定相等。只有当二叉树的带权路径长度最小时,二叉树才是霍夫曼树。

如给定 3,5,7,13 四个权值作为叶节点的权值,构造四个叶节点的二叉树可以有很多种不同的结构,下面例举出了其中两种,左边的二叉树的带权路径长度为 3*3 + 5*2 + 7*2 + 13*2 = 59,右边的二叉树的带权路径长度为 13*1 + 7*2 + 3*3 + 5*3 = 51。根据霍夫曼树的特性,权值越大的节点离根越近,也就是说权值越大的节点路径越短,下图中右边的二叉树就是一棵霍夫曼树,树的带权路径长度已经达到了最小。

那么,怎么根据给定的叶节点权值构建一棵霍夫曼树呢?在构造霍夫曼树前,先推导一些霍夫曼树的一般属性。

1. 要保证构造出来的二叉树是霍夫曼树,就要让权值大的节点的路径尽量短,反过来,权值小的节点就只能处于二叉树的更高层,把路径短的位置让给权值大的节点。从局部看,只要保证每个节点的路径都不大于权值比它小的节点即可,所以可以使用贪婪算法。

2. 霍夫曼树中不会存在只有一个子节点的节点。假设霍夫曼树中存在只有一个子节点的节点,如果删除该节点,它的子树中的所有叶节点的路径长度都可以减1,可以构造出带权路径长度更小的二叉树,这与霍夫曼树的定义矛盾,所以假设不成立。

3. 如果霍夫曼树只有两个叶节点,则两个叶节点的路径相等,都为 1。

根据这些属性,开始构造霍夫曼树,步骤如下:

1. 将有 N 个叶节点的树看成 N 棵树的森林(每棵树仅有一个根节点)。

以 3,5,7,13 为例。

2. 从森林中选出根节点权值最小的两棵树,分别作为新树的左右子树(这样构造新树满足霍夫曼树),且新树的根节点权值为其左右子树根结点的权值之和。然后将被合并的两棵树从森林中删除,将新树添加到森林中。

从中选出最小的 3 和 5,合并成一棵霍夫曼树,然后将新树添加到森林中。

3. 重复步骤 2 ,直到森林中只剩一棵树为止,最后的树即为霍夫曼树。

为了保证霍夫曼树的结构唯一,本文中每次合并时都将根节点权值小的树作为左子树,根节点权值大的树作为右子树。这个可以自己定,因为只要树的带权路径长度达到了最小,不管什么结构,都是霍夫曼树,霍夫曼树不是唯一的。

继续选出最小的 7 和 8,合并。

最终得到的霍夫曼树结构如下。

现在验证一下,树的带权路径长度为 WPL = 13*1 + 7*2 + 3*3 + 5*3 = 51,权值越大的节点路径越短,所以这是一棵霍夫曼树。

三、Python实现霍夫曼树

1. 代码准备

# coding=utf-8 class Node(object): def __init__(self, data): self.data = data self.parent = None self.left_child = None self.right_child = None self.is_in_tree = False class HuffmanTree(object): """霍夫曼树""" def __init__(self): self.__root = None self.prefix_branch = '├' self.prefix_trunk = '|' self.prefix_leaf = '└' self.prefix_empty = '' self.prefix_left = '─L─' self.prefix_right = '─R─' def is_empty(self): return not self.__root @property def root(self): return self.__root @root.setter def root(self, value): self.__root = value if isinstance(value, Node) else Node(value) def show_tree(self): if self.is_empty(): print('空二叉树') return print('-' * 20) print(self.__root.data) self.__print_tree(self.__root) print('-' * 20) def __print_tree(self, node, prefix=None): if prefix is None: prefix, prefix_left_child = '', '' else: prefix = prefix.replace(self.prefix_branch, self.prefix_trunk) prefix = prefix.replace(self.prefix_leaf, self.prefix_empty) prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty) if self.has_child(node): if node.right_child is not None: print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data)) if self.has_child(node.right_child): self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ') else: print(prefix + self.prefix_branch + self.prefix_right) if node.left_child is not None: print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data)) if self.has_child(node.left_child): prefix_left_child += ' ' self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child) else: print(prefix + self.prefix_leaf + self.prefix_left) def has_child(self, node): return node.left_child is not None or node.right_child is not None

讯享网

先创建一个节点类 Node,用于创建霍夫曼树的节点,这里要注意一点,因为在构造霍夫曼树时,要不断从一个森林中选根节点最小的两棵树进行合并,所以在节点里添加一个标志位,is_in_tree,如果为 True 则表示该树已经合并到霍夫曼树中了,不会重复取。

提前实现一个霍夫曼树的类 HuffmanTree ,先准备了一个按树形结构打印霍夫曼树的方法 show_tree() 。

下面根据霍夫曼树的构造过程,实现霍夫曼树的构造方法。

讯享网 def huffman(self, leavers): """构造霍夫曼树""" if len(leavers) <= 0: return if len(leavers) == 1: self.root = Node(leavers[0]) return woods = list() for i in range(len(leavers)): woods.append(Node(leavers[i])) while len(woods) < 2*len(leavers) - 1: node1, node2 = Node(float('inf')), Node(float('inf')) for j in range(len(woods)): if node1.data > node2.data: node1, node2 = node2, node1 if woods[j].data < node1.data and woods[j].is_in_tree is False: node1, node2 = woods[j], node1 elif node1.data <= woods[j].data < node2.data and woods[j].is_in_tree is False: node2 = woods[j] parent_node = Node(node1.data + node2.data) woods.append(parent_node) parent_node.left_child, parent_node.right_child = node1, node2 self.root, node1.parent, node2.parent = parent_node, parent_node, parent_node node1.is_in_tree, node2.is_in_tree = True, True 

huffman(leavers): 构造霍夫曼树。构造霍夫曼树时会给定 N 个权值,如果 N<=0,则直接返回。如果 N=1,则直接将该权值作为根节点的权值,即可构建出霍夫曼树。如果 N>=2,则先将这 N 个权值作为根节点的权值构建一个包含 N 棵树的森林,再从森林中选根节点权值最小的两棵树进行合并,一直循环直到只剩一棵树。

在这个方法中,有以下几点需要注意,否则很容易出错:

1. 代码里为了方便处理,并没有将被合并的树从列表 woods 中删除(删除操作很麻烦,尤其权值相等时),而是通过修改根节点的标志位 is_in_tree,如果 is_in_tree 为 True,表示该树已经被合并了,不会重复取。

那怎么判断霍夫曼树已经构造完成了呢,当 woods 中只剩一棵树的根节点的标志位 is_in_tree 为 False 时,但是,这样不好判断,每次合并后都要判断一遍 woods 中的根节点标志位。根据前面分析的属性,使用贪婪算法,每次合并树时,新的树都是一棵局部的霍夫曼树,并且霍夫曼树中不会存在只有一个子节点的节点。在构造霍夫曼树的过程中,每个节点都作为一棵树的根节点被添加到森林 woods 中了,所以 woods 的长度等于霍夫曼树的节点数,当 woods 的长度达到霍夫曼树的节点总数时,霍夫曼树就构造完成。

霍夫曼树中除了叶节点,其他节点都有两个子节点,根据二叉树的特性,当叶节点数为 N 时,有两个子节点的节点数为 N+1,所以有 N 个叶节点的霍夫曼树的节点数为 2*N + 1 。

2. 为了获取到权值最小的两个根节点,提前声明了两个变量 node1 和 node2 ,这两个变量可以提前赋值为两个权值很大的节点,建议直接使用正无穷大 float('inf'),如果一开始赋值为 woods 中的第一个和第二个,当第一个或第二个值就是最小值时,可能会每次循环都取到相同的值。

3. 在寻找权值最小的两个根节点值时,如果当前节点 node 的权值小于 node1 的权值,node.data < node1.data ,则将 node1 赋值给 node2,将 node 赋值给 node1,如果当前节点 node 的权值大于等于 node1 的权值同时小于 node2 的权值,node1.data <= node.data < node2.data,则将 node 赋值给 node2。这里很容易忽略第二种情况。

if __name__ == '__main__': tree = HuffmanTree() leavers = [11, 5, 7, 13, 17, 11] tree.huffman(leavers) tree.show_tree()

运行结果:

讯享网-------------------- 64 ├─R─39 | ├─R─22 | | ├─R─11 | | └─L─11 | └─L─17 └─L─25 ├─R─13 └─L─12 ├─R─7 └─L─5 --------------------

给定的 N 个叶节点权值为 [11, 5, 7, 13, 17, 11] ,霍夫曼树结构如下图。

该霍夫曼树的带权路径长度为 WPL = 13*2 + 17*2 + 5*3 + 7*3 + 11*3 + 11*3 = 162 。

 

 

小讯
上一篇 2025-04-03 15:11
下一篇 2025-03-18 08:13

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82252.html