哈夫曼编码运用到了哪种数据结构

哈夫曼编码运用到的数据结构为“树型结构”。在哈夫曼算法的支持下构造出一棵最优二叉树，我们把这类树命名为哈夫曼树。因此，准确地说，哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式。

本教程操作环境：windows7系统、Dell G3电脑。

哈夫曼编码运用到的数据结构为“树型结构”。

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

哈夫曼编码借助了数据结构当中的树型结构，在哈夫曼算法的支持下构造出一棵最优二叉树，我们把这类树命名为哈夫曼树。因此，准确地说，哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式，它的本身有着非常广泛的应用。

哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

想要查阅更多相关文章，请访问PHP中文网！！

Atas ialah kandungan terperinci 哈夫曼编码运用到了哪种数据结构. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!