Python描述数据结构学习之哈夫曼树篇

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])

 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)

 def HuffmanEncode(self, Root):
  TreeNode = self.nodes[:]
  code_result = []
  for index in range(len(TreeNode)):
   temp = TreeNode[index]
   code_leaf = [temp.data]
   code = ''
   while temp is not Root:
    if temp.parent.lchild is temp:
     # 左分支
     code = '0' + code
    else:
     # 右分支
     code = '1' + code
    temp = temp.parent
   code_leaf.append(code)
   code_result.append(code_leaf)
  return code_result

if __name__ == '__main__':
 tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)])
 huf_tree = tree_obj.CreateHuffmanTree()
 huf_code = tree_obj.HuffmanEncode(huf_tree)
 for index in range(len(huf_code)):
  print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))