计算机考研 408 数据结构 哈夫曼

常用公式及概念

1. 树的带权路径长度：(其中wi为叶子结点权值, li为叶子结点到根结点的路径长度)
2. 加权平均长度： WPL/权值累加
3. WPL最小的二叉树为哈夫曼数
4. 哈夫曼树的构造
   1. 最小的两个构造二叉树，根节点为叶子节点权值之和
   2. 再找最小的两个(包括已经形成的根结点, 最小的两个可以相等)构造二叉树（左右随意）
   3. 节点个数为2n-1
   4. 没有度为1的节点（节点的度就是节点的叶子数)
5. 前缀编码：每一个字符的编码都不是另一个字符的前缀
6. 哈夫曼编码：遍历哈夫曼树，向左走时添加一个 0 位, 向右走时添加一个 1 位, 每个数据符号生成相应的 哈夫曼编码。