构建哈夫曼树及哈弗曼编码

哈夫曼树是一种用于数据压缩的树形结构，其中节点的权值代表着对应字符的出现频率，具有较高频率的字符离根节点较近，具有较低频率的字符离根节点较远。构建哈夫曼树的过程如下：

1. 将所有字符按照出现频率从小到大排序。
2. 选择两个权值最小的节点构成一棵新的树，新树的根节点权值为这两个节点的权值之和。
3. 将新树插入到原来的节点序列中，删除原来的两个节点，重复执行步骤2，直到只剩下一个节点为止。

构建完成后，对哈夫曼树进行编码即可实现压缩，编码规则如下：

1. 若节点为左子树，则编码为0，否则编码为1。
2. 遍历到叶子节点时，记录该节点的编码即可。

例如，对于字符串"ABAACBAD"，构建哈夫曼树的过程如下：

| 字符 | 频率 |
| ---- | ---- |
| A | 4 |
| B | 2 |
| C | 1 |
| D | 1 |

1. 将字符按照频率排序，得到C、D、B、A。
2. 选择C和D构成新树，根节点权值为2。
3. 将新树插入序列，得到B、A、2。
4. 选择B和2构成新树，根节点权值为4。
5. 将新树插入序列，得到A、4。
6. 选择A和4构成新树，根节点权值为8，得到最终的哈夫曼树。

编码规则如下：

| 字符 | 频率 | 编码 |
| ---- | ---- | ---- |
| A | 4 | 0 |
| B | 2 | 10 |
| C | 1 | 110 |
| D | 1 | 111 |

因此，"ABAACBAD"的压缩结果为"0101000011101011110"。