数据结构—-哈夫曼树 目录 一、哈夫曼树的基本概念 二、哈夫曼树的算法 1，哈夫曼树的构造算法 2，哈夫曼树算法实现 三、哈夫曼的编码 1，哈夫曼的编码思想 2，哈夫曼编码的算法实现 3，文件的编码和译码 一、哈夫曼树的基本概念 哈夫曼树也叫最优二叉树。 
结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。反过来不成立。 
满二叉树不一定是哈夫曼树，权值越大离根越近。具有相同带权结点的哈夫曼树不唯一。 二、哈夫曼树的算法 1，哈夫曼树的构造算法 把n个结点看成n颗二叉树，每次选取权值最小的两个根结点构成新的树，新的根结点的权值为左右子树根结点之和，新根结点的权值和剩余的权值比较，再选出最小的两个结点，重复上述步骤，直到森林中只有一颗树。 
哈夫曼树只有度为0和2的结点。包含n个叶子结点（度为0）的哈夫曼树经过n-1次合并产生n-1个新结点（度为2），所以总共有2n-1个结点。 2，哈夫曼树算法实现 顺序存储：一维结构数组，2n-1个数组，定义2n大小的数组，只用1~2n-1，0空着。 
三、哈夫曼的编码 1，哈夫曼的编码思想 关键：要设计长度不等（出现频率高的长度更短，可以节约空间）的编码，任意字符不是其他字符的前缀（前缀编码） 哈夫曼树是前缀编码（没有一个叶子结点的祖先是别的叶子结点），且能保证字符编码总长度最短（因为哈夫曼树的带权路径长度最短）（最优前缀码）。 
2，哈夫曼编码的算法实现 从一维数组的叶子结点出发，找双亲结点，根据双亲结点的指针域确定是左孩子还是右孩子，并且标记为0或者为1，继续从该结点找其双亲结点，重复步骤直到双亲结点的parent域为0，说明到根结点了。每个叶子结点重复该步骤。 需要一个二维数组记录每个叶子结点的编码，数组第一列为叶子结点的字符，第二列为字符顺序i（i=1~n），第三列存放字符编码（一个字符串），（哈夫曼树最高n-1层，因此字符串长度为n，前n-1存放编号，n位置存放0，而且存放时从字符串的最后往前存放）。 
3，文件的编码和译码 
根据接收的字符频度表来构建哈夫曼树。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/45319.html
