Python实现哈夫曼树编码：原理、代码解析与完整流程

季宁

发布时间：2026-10-13| 5人浏览过

原创

本文详细解析Python中哈夫曼树的构建与编码过程。从树节点类定义、优先度队列管理，到字符频率统计、中序遍历生成编码表，最后实现字符串的编码与解码。通过逐段代码分析，帮助读者理解哈夫曼编码的核心逻辑与递归实现，适用于Python初学者及算法爱好者参考。

哈夫曼树原理与流程概述

哈夫曼树原理

遵循精简实用的原则，关于哈夫曼树的理论背景及具体构建方法，建议参考相关技术博客以获取更详尽的背景知识。

https://www.jb51.net/article/97396.htm

其大概流程

哈夫曼编码Python实现代码解析

哈夫曼编码代码

核心数据结构与队列管理


# 树节点类构建
class TreeNode(object):
  def __init__(self, data):
    self.val = data[0]
    self.priority = data[1]
    self.leftChild = None
    self.rightChild = None
    self.code = ""
# 创建树节点队列函数
def creatnodeQ(codes):
  q = []
  for code in codes:
    q.append(TreeNode(code))
  return q
# 为队列添加节点元素，并保证优先度从大到小排列
def addQ(queue, nodeNew):
  if len(queue) == 0:
    return [nodeNew]
  for i in range(len(queue)):
    if queue[i].priority >= nodeNew.priority:
      return queue[:i] + [nodeNew] + queue[i:]
  return queue + [nodeNew]
# 节点队列类定义
class nodeQeuen(object):

  def __init__(self, code):
    self.que = creatnodeQ(code)
    self.size = len(self.que)

  def addNode(self,node):
    self.que = addQ(self.que, node)
    self.size += 1

  def popNode(self):
    self.size -= 1
    return self.que.pop(0)
# 各个字符在字符串中出现的次数，即计算优先度
def freChar(string):
  d ={}
  for c in string:
    if not c in d:
      d[c] = 1
    else:
      d[c] += 1
  return sorted(d.items(),key=lambda x:x[1])
# 创建哈夫曼树
def creatHuffmanTree(nodeQ):
  while nodeQ.size != 1:
    node1 = nodeQ.popNode()
    node2 = nodeQ.popNode()
    r = TreeNode([None, node1.priority+node2.priority])
    r.leftChild = node1
    r.rightChild = node2
    nodeQ.addNode(r)
  return nodeQ.popNode()

codeDic1 = {}
codeDic2 = {}
# 由哈夫曼树得到哈夫曼编码表
def HuffmanCodeDic(head, x):
  global codeDic, codeList
  if head:
    HuffmanCodeDic(head.leftChild, x+'0')
    head.code += x
    if head.val:
      codeDic2[head.code] = head.val
      codeDic1[head.val] = head.code
    HuffmanCodeDic(head.rightChild, x+'1')
# 字符串编码
def TransEncode(string):
  global codeDic1
  transcode = ""
  for c in string:
    transcode += codeDic1[c]
  return transcode
# 字符串解码
def TransDecode(StringCode):
  global codeDic2
  code = ""
  ans = ""
  for ch in StringCode:
    code += ch
    if code in codeDic2:
      ans += codeDic2[code]
      code = ""
  return ans
# 举例
string = "AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA"
t = nodeQeuen(freChar(string))
tree = creatHuffmanTree(t)
HuffmanCodeDic(tree, '')
print(codeDic1,codeDic2)
a = TransEncode(string)
print(a)
aa = TransDecode(a)
print(aa)
print(string == aa)

接下来对代码进行分段解析。

1.树结点类的构建：

该类包含五个核心属性：节点的值、节点的优先度（权重）、左子节点、右子节点以及节点值的编码字符串。这些属性均为构建哈夫曼树所必需。

2.创建树结点队列函数：

针对所有字母节点，我们需要将其组织为一个队列，此处使用Python的list列表来实现队列功能。将所有树节点放入列表中，传入的参数应为已按优先度从小到大排序的元素列表。

3.为队列添加节点元素，并保证优先度从大到小排列：

当生成新的内部节点时，需将其插入列表中的合适位置，以确保队列始终保持按优先度从小到大排列的顺序。

4.结点队列类定义：

类初始化时接收一个列表作为参数，列表中的每个元素是由字母与优先度组成的元组。元组的第一个元素为字母，第二个元素为该字母在文本中出现的次数（即优先度）。

在类初始化过程中，调用“创建树结点队列函数”，将队列中的每个元素转换为对应的树节点对象。

该类还包含一个记录队列规模的属性，以及两个操作函数：添加节点函数和弹出节点函数。

添加节点函数直接调用前文定义的插入函数，输入参数为当前队列和新节点，同时队列规模加一。