构建哈夫曼树输入字符串输出对应哈夫曼编码

好的，构建哈夫曼树的步骤如下：

1. 统计字符串中每个字符出现的频率，并按照频率从小到大排序。
2. 选取频率最小的两个字符作为叶子节点，构建一棵二叉树。其中较小频率的字符作为左子节点，较大频率的字符作为右子节点。并将它们的频率相加，作为父节点的频率。
3. 将新生成的父节点插入到频率数组中，并将数组按照频率从小到大重新排序。
4. 重复步骤2和3，直到只剩下一个节点，即根节点。

得到哈夫曼树之后，对于每个叶子节点，从该节点到根节点的路径上，如果向左走则标记为0，向右走则标记为1。这样就得到了每个字符的哈夫曼编码。

下面是一个示例：

假设字符串为 "abacabadabacaba"，则字符出现频率为：

| 字符 | a | b | c | d |
| ---- | - | - | - | - |
| 频率 | 8 | 4 | 2 | 2 |

按频率排序后为：c、d、b、a。

首先选取频率最小的两个字符 c 和 d，构建一棵二叉树：

   4
  / \
 c   d

然后插入新的父节点，重新排序：

| 节点 | c | d | 4 |
| ---- | - | - | - |
| 频率 | 2 | 2 | 4 |

接着选取频率最小的两个节点 c 和 d，构建一棵新的二叉树：

    8
   / \
  4   4
 / \
c   d

插入新节点，重新排序：

| 节点 | b | c | d | 4 | 8 |
| ---- | - | - | - | - | - |
| 频率 | 4 | 2 | 2 | 4 | 8 |

再次选取频率最小的两个节点 b 和 c，构建新的二叉树：

     12
    /  \
   4    8
  / \
 c   d

插入新节点，重新排序：

| 节点 | a | b | c | d | 4 | 8 | 12 |
| ---- | - | - | - | - | -- | -- | -- |
| 频率 | 8 | 4 | 2 | 2 | 4 | 8 | 16 |

最后选取频率最小的两个节点 a 和 b，构建最终的哈夫曼树：

     16
    /  \
   8    8
  / \
 a   b
     |
     4
    / \
   c   d

从根节点到每个叶子节点的路径上，向左走标记为0，向右走标记为1，得到字符的哈夫曼编码为：

| 字符 | a | b | c | d |
| ---- | - | - | - | - |
| 编码 | 0 | 10 | 110 | 111 |

希望这个例子能够帮助你理解哈夫曼编码的构建过程。