每日算法之-哈夫曼树
概念: 哈夫曼树 (最优树) ---- 带权路径长度最短的树
“带权路径长度最短” 是在 "度相同"的树中比较而得的结果,因此有最优二叉树,最优三叉树之称等等。
哈夫曼算法口诀:
1.构造森林全是根; 2.选用两小造新树
3、删除两小添新人 4、重复2、3剩单根
例如 : 有4个节点 a,b,c,d 权值分别为7,5,2,4,构造哈夫曼树
1.构造森林全是根
以这4个节点建立一个森林,根节点为a,b,c,d ,权值为7,5,2,4
2.选用两小造新人
选择最小的权值的两个跟节点2,4构造一颗树
3.删除两小添新人
构造树的根节点为6,删除2,4,剩余的森林节点为7,5,6
4.重复2、3剩单根
继续重复2,3步骤,构造树