Question

二叉树实现符号不等长高效编码

Answer 1

二叉树中的最优二叉树（也就是哈夫曼树）可以实现符号不等长高效编码。

哈夫曼树（最优二叉树）：就是将二叉树的WPL降到最低（WPL最小的二叉树）。当用n个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则：权重越大的结点离树根越近。

哈夫曼树构造的编码中，最主要的是“如何选择两个最小的结点？”。可以利用堆来解决，把结点的权值构造成最小堆，从里面挑两个最小的。当然也可以用排序的方法来选择两个最小的结点，但是排序的方法效率不如堆。构建哈夫曼树时，首先需要确定树中结点的构成。

哈夫曼树的特点

1、没有度为1的结点。

2、n个叶子结点的哈夫曼树公有2n-1个结点。

3、哈夫曼树的任意非叶结点的左、右子树互换后，还是哈夫曼树。

4、同一组权值，可能存在不同构的哈夫曼树。