python数据结构学习笔记-树（下）-哈夫曼树与哈夫曼编码（1）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python数据结构学习笔记-树（下）-哈夫曼树与哈夫曼编码（1），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2207字，纯文字阅读大概需要4分钟。
内容图文
数据结构-树（下）-哈夫曼树与哈夫曼编码（基础知识）
哈夫曼树
带权路径长度（WPL）
二叉树中所有叶结点的带权路径长度之和，其中n为叶节点数，根节点要叶节点的长度为l：
WPL=k=1∑n?wk?lk?
哈夫曼树即最优二叉树，指WPL最小的二叉树。
哈夫曼树的每个节点的度为0或2.
哈夫曼树的构造
每次把权值最小的两颗二叉树合并（利用堆排序来选择权值的最小值）
def insert_data(heap, x):
if len(heap.data) > heap.maxsize: # 判断堆是否已满
print('Full')
else:
heap.size += 1
heap.data.append(x) # 先放在数组的最后
i = heap.size
while i:
if x < heap.data[i//2]: # 比较插入点与父节点的大小，比父节点小即与父节点交换
heap.data[i] = heap.data[i//2]
heap.data[i//2] = x
i //= 2
else:
break
return heap
def delete_data(heap):
if len(heap.data) == 1: # 判断堆是否已空
print('Empty')
else:
data = heap.data[1] # 根节点即最小值
temp = heap.data[heap.size] # 把最后一个元素提出
heap.data.pop()
heap.size -= 1
parent = 1
while parent*2 <= heap.size:
child = parent * 2
if child != heap.size and heap.data[child] > heap.data[child+1]:
child += 1
if temp < heap.data[child]:
break
else:
heap.data[parent] = heap.data[child]
parent = child
heap.data[parent] = temp
return data
class Heap:
def __init__(self):
self.size = 0 # 当前容量
self.maxsize = 0 # 堆的最大容量
self.data = [0] # 存储堆元素的数组
# 建立最小堆
min_heap = Heap()
min_heap.maxsize = 10
min_heap.data[0] = -10000 # 放一个比所有元素都小的值，做哨兵
weight = [1, 6, 5, 7, 8, 4, 9, 3, 10, 2] # 权重列表
for i in range(10):
insert_data(min_heap, weight[i])
print(min_heap.data)
tree = list()
for i in range(min_heap.maxsize):
node = dict(data=0, left=0, right=0)
node['left'] = delete_data(min_heap) # 取出最小的两个权重值（最小堆的根节点）
node['right'] = delete_data(min_heap)
if len(min_heap.data) == 1:
break
node['data'] = node['left'] + node['right'] # 权值相加为新的节点权值
tree.append(node)
insert_data(min_heap, node['data']) # 新权值与原权值一起重新排序
print(tree)哈夫曼编码
不等长编码，出现频率大的编码长度短，反之编码长度长。
需避免二义性：任何一个字符的编码都不是其他字符编码的前缀码。
因此可以使用二叉树：根节点的左右分支为0，1，而字符只在叶节点上。
内容总结
以上是互联网集市为您收集整理的python数据结构学习笔记-树（下）-哈夫曼树与哈夫曼编码（1）全部内容，希望文章能够帮你解决python数据结构学习笔记-树（下）-哈夫曼树与哈夫曼编码（1）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。