赫夫曼树
2018-04-09 本文已影响0人
凉拌姨妈好吃
赫夫曼树
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，那么计算可得出，编码后字符串的长度为非叶子节点权值之和
