拓展阅读1 哈夫曼树-浙江高中信息技术知识点

浙江高中技术培优算法（陶小波） 99 拓展阅读 1 哈夫曼树 哈夫曼树，也被称为最优二叉树，是一种带权路径长度最短的二叉树。在哈夫曼树中，权值 较大的结点离根较近，从而使得整棵树的带权路径长度最小。带权路径长度是指树中所有叶 子结点的权值乘上其到根结点的路径长度之和。哈夫曼树在数据压缩等领域有着广泛的应用， 如哈夫曼编码就是基于哈夫曼树的一种数据压缩方法。 构建哈夫曼树的过程如下： 1.首先，将给定的 n个带有权值的结点组成一个结点集合。 2.从集合中选出权值最小的两个结点，构造一棵二叉树，其根结点的权值为这两个结 点 权值之和。 3.删除选出的两个结点，并将新构造的根结点加入到集合中。 4.重复步骤 2 和 3，直至集合中只剩下一个结点为止，这个结点就是哈夫曼树的根结点。 通过这样的构造过程，可以保证得到的哈夫曼树的带权路径长度是最小的。在实际应用中， 哈夫曼树能够有效地减少数据存储和传输的开销，提高数据处理的效率。 例如：有如下值 2，3，7，13，15，9，11 第一轮 先挑出最小的相邻两个根节点值(2,3)的节点，合并成一个父节点。图如下： 第二轮 再挑出最小的相邻两个根节点值(5,7)的节点，合并成一个父节点。图如下： 浙江高中技术培优算法（陶小波） 100 第三轮，再挑出最小的相邻两个根节点值(9,11)的节点，合并成一个父节点。图如下： 第四轮，再挑出最小的相邻两个根节点值(12,13)的节点，合并成一个父节点。图如下： 第五轮，再挑出最小的相邻两个根节点值(15,20)的节点，合并成一个父节点。图如下： 浙江高中技术培优算法（陶小波） 101 最后，再将 25 和 35 合并成一个父节点。图如下： 代码如下： class HuffmanTreeNode(object): def __init__(self): self.data = '#' self.weight = -1 self.parent = None self.lchild = None self.rchild = None class HuffmanTree(object): def __init__(self, data_list): self.nodes = [] # 按权重从大到小进行排列 for val in data_list: newnode = HuffmanTreeNode() newnode.data = val[0] newnode.weight = val[1] self.nodes.append(newnode) self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True) print([(node.data, node.weight) for node in self.nodes]) 浙江高中技术培优算法（陶小波） 102 def CreateHuffmanTree(self): # 这里注意区分 # TreeNode = self.nodes[:] 变量 TreeNode, 这个相当于深拷贝, TreeNode 变化不 影响 nodes # TreeNode = self.nodes 指针 TreeNode 与 nodes 共享一个地址, 相当于浅拷贝, TreeNode 变化会影响 nodes TreeNode = self.nodes[:] if len(TreeNode) > 0: while len(TreeNode) > 1: letfTreeNode = TreeNode.pop() rightTreeNode = TreeNode.pop() newNode = HuffmanTreeNode() newNode.lchild = letfTreeNode newNode.rchild = rightTreeNode newNode.weight = letfTreeNode.weight + rightTreeNode.weight letfTreeNode.parent = newNode rightTreeNode.parent = newNode self.InsertTreeNode(TreeNode, newNode) return TreeNode[0] def InsertTreeNode(self, TreeNode, newNode): length = len(TreeNode) if length > 0: temp = length - 1 while temp >= 0: if newNode.weight < TreeNode[temp].weight: TreeNode.insert(temp+1, newNode) return True temp -= 1 TreeNode.insert(0, newNode)