1 问题
给定n个权值作为n个叶子结点，构造一棵二叉树。若该树的带权路径长度达到最少，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。而根据哈夫曼树的定义，可以思考有关哈夫曼树的实现该如何进行，本次周博客将围绕哈夫曼树的实现展开讨论。
2 方法
- 创建一个结点
- 创建哈夫曼树
- 编码哈夫曼编码
- 调用
通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。
代码清单 1
| # 节点类 class Node(object): def __init__(self, name=None, value=None): self._name = name self._value = value self._left = None self._right = None # 哈夫曼树类 class HuffmanTree(object): # 根据Huffman树的思想：以叶子节点为基础，反向建立Huffman树 def __init__(self, char_weights): self.a = [Node(part[0], part[1]) for part in char_weights] # 根据输入的字符及其频数生成叶子节点 while len(self.a) != 1: self.a.sort(key=lambda node: node._value, reverse=True) c = Node(value=(self.a[-1]._value + self.a[-2]._value)) c._left = self.a.pop(-1) c._right = self.a.pop(-1) self.a.append(c) self.root = self.a[0] self.b = list(range(10)) # self.b用于保存每个叶子节点的Haffuman编码,range的值只需要不小于树的深度就行 # 用递归的思想生成编码 def pre(self, tree, length): node = tree if not node: return elif node._name: print(node._name + '的编码为:',end=" ") for i in range(length): print(self.b[i],end="") print() return self.b[length] = 0 self.pre(node._left, length + 1) self.b[length] = 1 self.pre(node._right, length + 1) # 生成哈夫曼编码 def get_code(self): self.pre(self.root, 0) if __name__ == '__main__': # 输入的是字符及其频数 char_weights = [('A', 27), ('B', 8), ('C', 15), ('D', 6), ('E', 30), ('F', 5)] tree = HuffmanTree(char_weights) tree.get_code() |
3 结语
针对有关哈夫曼树的实现的问题，提出本次博客所涉及的方法，通过本次Python实验，证明该方法是有效的，本此的方法还存在许多不足或考虑不周的地方，希望在接下来的学习过程中可以更好的掌握哈夫曼树。
