哈弗曼编码及译码

路径长度：从树的一个结点到另一个结点之间边的条数。

树的路径长度：从树根到每个叶子结点之间路径长度之和。

带权树的路径长度：每个叶子结点带有权值，树根到叶子结点的路径长度乘以该叶子结点的权值之和。

哈弗曼树：带权树的路径长度最小的树，又称作最小二叉树和最优二叉树。

哈夫曼树的构造过程：                                                                                                                                                                                 

1.      根据给定的n个带权的结点，构成含有n棵二叉树（每个结点是一棵树）的集合，该树的左右子树均为空。

2.      从含有n棵子树集合中找出两棵权值最小的树最为左右子树构成一个新的二叉树。

3.      从集合中删除这两棵权值最小的二叉树，将新的二叉树插入集合中。

4.      重复2和3步骤，知道最终只剩下一颗树为止，这棵树就是哈弗曼树。

哈弗曼树的应用：最优判定，哈弗曼编码。

前缀编码：字符设计长短不等的编码，且任一字符的编码都不是另一字符编码的前缀（比如0就是00的前缀）。

哈弗曼编码：一种二进制前缀编码。一棵二叉树左分支表示字符“0”，右分支表示字符“1”，从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。求哈弗曼编码就是求一棵哈弗曼树的过程。

由于哈弗曼树中没有度为1的结点二叉树，则一棵有n个叶子的哈弗曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。构成哈弗曼树后，编码是从叶子结点走出一条叶子结点到根的路径，而译码需从根结点出发走出一条从根到叶子的路径，这两个过程相反，左移编码或者译码时要注意调整二进制存储顺序。

一个字符串得到编码后，以二进制存储时需要额外存储这个字符串的字节数，因为在编码后的编码串转二进制时需要移位，没八个字节转为一个字节，若不满八个字节则需要用0补齐，所以在解码时为了去除掉补齐的0，需要原始字符的字节数，那么假如原始字符串大小为n，字符串编码后的二进制编码大小为m，那么实际二进制编码存储大小为m+1，压缩比就为（m+1）/n。

注意：哈弗曼编码在设计应用的时候需要注意的是编码端和译码端要有相同的字符频率表而且构造哈弗曼树的过程相同，否则没办法译码。

代码实现如下：

// 5.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include    
#include       
#include 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！