哈夫曼树思维导图
哈夫曼树计算机术语详解
树图思维导图提供 哈夫曼树 在线思维导图免费制作，点击“编辑”按钮，可对 哈夫曼树 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0625342e4baf2241f2b9fc58d7c8f4e8
思维导图大纲
哈夫曼树思维导图模板大纲
概念
结点的带权路径长度 = 根到结点路径长度 (经过的边数)* 结点权值
树的带权路径长度（WPL） = 树中所有叶子节点的带权路径长度之和
哈夫曼（Huffman）树（赫夫曼树）（最优二叉树）：在含有给定的n个带权叶结点的二叉树中，WPL最小的二叉树
性质
n个初始结点，哈夫曼树有n个叶结点，高度必为n
权值越小到根的路径长度越大
哈夫曼树是一棵正则二叉树，哈夫曼树结点总数 = 2n - 1
没有度为1的结点
哈夫曼树不唯一，但是各树WPL必相同且最小
构造哈夫曼树
将这n个结点分别作为只含有1个节点的二叉树，形成森林F
从F中选择两个权值最小的树作为新节点的左右子树，并将新节点权值置为左右子树根节点权值之和
F中删除刚才选出的两棵树，并把新树加入F
重复上述操作，直到F中只有一棵树
哈夫曼编码
将字符频次作为字符结点权值，构造哈夫曼树，可得哈夫曼编码，用于数据压缩
平均压缩率 = 利用哈夫曼编码相比与其他长度编码的平均码长（WPL）减少了多少
固定长度编码：每个字符用相等长度二进制位表示
可变长度编码：允许不同字符用不等长二进制位表示
前缀编码：没有一个编码是另一个编码的前缀
举例说明，其实没有限制必须左0右1，每棵子树左右都可0可1，互相无关
补充
判断是否有前缀特性
初始只有根，左右指针空，依次读入编码C
对每个C从左至右扫描各位，根据当前位（0/1）沿指针（左/右）向下移动。遇到空就创建新节点，指向该节点并继续移动
移动过程可能遇到3种情况
非根叶结点：无前缀特性
处理C的所有位都未创建新节点：无
处理C的最后一个编码位创建了新节点：继续判断下一个编码
所有编码都通过验证：有
相关思维导图模板
树图思维导图提供 3A Unit 1 A Proper Job 在线思维导图免费制作，点击“编辑”按钮，可对 3A Unit 1 A Proper Job 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8d966446cda22e33b426cba15d3d981e
树图思维导图提供 说文解字戏美国总统大选 在线思维导图免费制作，点击“编辑”按钮，可对 说文解字戏美国总统大选 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：062e27e31bfd81ad6f3ed78f2a4c7de2
沪公网安备 31011502019485号
上海工商