树与二叉树的应用¶
哈夫曼树与哈夫曼编码¶
哈夫曼树的定义¶
-
权: 树中结点赋予一个有着某种含义的数值，这个数值称为该结点的权
-
结点带权路径长度: 从根结点到该结点之间的路径长度与该结点的权的乘积
-
树的带权路径长度（WPL）: 树中所有叶子结点的带权路径长度之和，记作
\[ WPL = \sum_{i=1}^{n} w_i l_i \]其中 \(w_i\) 是第 \(i\) 个叶子结点的权，\(l_i\) 是第 \(i\) 个叶子结点的路径长度
哈夫曼树（Huffman Tree）又称最优二叉树，指带权路径长度最小的二叉树。
哈夫曼树的构造¶
-
将所有结点分别作为一棵仅含一个结点的二叉树，构成森林 \(F\)
-
构造一个新结点，从 \(F\) 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值设为左、右子树根结点权值之和
-
从 \(F\) 中删除这两棵树，并将新结点加入 \(F\)
-
重复步骤 2 和 3，直到 \(F\) 中只剩下一棵树为止
哈夫曼编码¶
将二进制表示为 \(01\) 串的字符序列转换为二进制 \(01\) 串，构造哈夫曼树，并规定左分支为 \(0\)，右分支为 \(1\)，则从根结点到叶子结点的路径上分支组成的 \(01\) 串便为该结点字符的编码。
