赫夫曼树

Q：什么是赫夫曼树（也叫最优二叉树，有点像得到最优解的贪心法）？

A：带权路径长度最小的二叉树

Q：如何构造一棵赫夫曼树？

A：1.将给定的n个权值构成n棵二叉树的集合，集合内的每棵二叉树都只有一个带权的根节点

      2.从集合内取出最小的两个根节点，作为左孩子和右孩子，两个节点权值之和作为父节点的权值，将这棵新得到的二叉树放入1中的集合内，删除这两个最小的根节点。

      3.重复2操作直到最后只剩下唯一一棵树为止

相关笔试题：

来源

    解题思路：

        1.统计输入的字母：M（2个）T（3）E（2）C（1）A（1）H（1）-（2）

        2.将字母个数作为权值，画出赫夫曼树，父节点到左孩子之间设为编码0，到右孩子之间设为1，那么计算可得出，编码后字符串的长度为非叶子节点权值之和