DS二叉树--赫夫曼树解码

赫夫曼树是一种特殊的二叉树，它的每个叶子节点都表示一个字符，并且每个字符对应的编码都是唯一的。赫夫曼树常用于数据压缩。

赫夫曼树的编码方式是按照前缀编码进行编码，即一个字符的编码不能是另一个字符编码的前缀。例如，如果字符 A 的编码是 10，那么字符 B 的编码不能是 1，因为这个编码是字符 A 的前缀。

赫夫曼树的解码方式是从根节点开始遍历树，根据编码的 0 或 1 分别选择左子树或右子树，直到到达叶子节点，找到对应的字符。

下面是一个赫夫曼树的例子：

        /\
       /  \
      /    \
     /\    /\
    /  \  /  \
   a   b  c   d

假设字符 a 的编码为 0，字符 b 的编码为 10，字符 c 的编码为 110，字符 d 的编码为 111。那么，编码串 010110111 可以被解码成字符串 "abcbd"。

具体的解码过程如下：

1. 从根节点开始遍历树，根据第一个字符 0，选择左子树。
2. 继续遍历左子树，根据第二个字符 1，选择右子树。
3. 继续遍历右子树，根据第三个字符 0，选择左子树。
4. 到达叶子节点，找到字符 a。
5. 回到根节点，根据第四个字符 1，选择右子树。
6. 继续遍历右子树，根据第五个字符 1，选择右子树。
7. 继续遍历右子树，根据第六个字符 0，选择左子树。
8. 到达叶子节点，找到字符 b。
9. 回到根节点，根据第七个字符 1，选择右子树。
10. 继续遍历右子树，根据第八个字符 1，选择右子树。
11. 到达叶子节点，找到字符 d。
12. 回到根节点，根据第九个字符 1，选择右子树。
13. 继续遍历右子树，根据第十个字符 1，选择右子树。
14. 到达叶子节点，找到字符 c。
15. 读取完所有的字符，解码完成。