595 字
3 分钟
Tree Btree
树和二叉树的应用
哈夫曼树和哈夫曼码
在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权，从树的根结点到任意结点的路径长度与该结点上的权值的乘积，称为该结点的带权路径长。树中所有叶结点的带权路径长被称为该树的带权路径长（WPL）。
在含有 n 个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。
哈夫曼树的构造
从上述的构造过程中可以看出哈夫曼树具有一下特点：
- 每个初始结点最终都成了叶结点，且权值越小的结点到根结点的路径长度越大。
- 构造过程中新建了 n - 1 个分支结点，因此哈夫曼树的总结点数为 2n - 1。
- 每次构造都选择两棵树作为新结点的孩子，因此哈夫曼树不存在度为 1 的结点。
哈夫曼编码
在数据通讯中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制表示，则这种编码方式称为可变长度编码，其特点是对频率高的字符覆以短编码，频率低的字符则赋予长编码，从而使字符的平均长度减短，起到压缩数据的作用，哈夫曼编码正是一种被广泛应用而且有效的数据压缩编码。
若没有一个编码是另一个编码的前缀，则称为这样的编码为前缀编码。由哈夫曼树得到哈夫曼编码是很自然的过程，其权值正好对应它出现的次数，构造出对应的哈夫曼树，我们将字符的编码解释为从根至该字符路径上边界的标记的序列，0 表示转向左孩子，1 表示转向右孩子。
并查集
参考算法模块中的并查集。