哈夫曼树的构造与编码

哈夫曼树是一种特殊的二叉树，它的构造过程是根据给定的n个权值，构建n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。在森林中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上的权值之和。在森林F中删除这两颗树，同时将新得到的二叉树加入F中。重复上述步骤，直到F中只含一颗树时为止。这棵树便是哈夫曼树。

哈夫曼编码是一种前缀编码，它是根据字符出现的频率构造出的一种编码方式，使得出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码。哈夫曼编码的构造过程就是根据哈夫曼树来实现的。对于哈夫曼树上的每个叶子节点，从根节点到该叶子节点的路径上的编码就是该叶子节点对应的字符的哈夫曼编码。由于哈夫曼树的特殊性质，任意两个字符的哈夫曼编码的前缀都不会相同，因此哈夫曼编码是一种无歧义的编码方式。