算法速成（十三）树操作之赫夫曼树

算法速成（十三）树操作之赫夫曼树2014-04-28 csdn博客特种兵—AK47今天说下最后一种树，大家可否知道，文件压缩程序里面的核心结构，核心算法是什么？或许你知道，他就运用了赫夫曼树。

听说赫夫曼胜过了他的导师，被认为”青出于蓝而胜于蓝“，这句话也是我比较欣赏的，嘻嘻。

一概念

了解”赫夫曼树“之前，几个必须要知道的专业名词可要熟练记住啊。

1：结点的权

“权”就相当于“重要度” ，我们形象的用一个具体的数字来表示，然后通过数字的大小来决定谁重要，谁不重要。

2：路径

树中从“一个结点"到“另一个结点“之间的分支。

3：路径长度

一个路径上的分支数量。

4：树的路径长度

从树的根节点到每个节点的路径长度之和。

5：节点的带权路径路劲长度

其实也就是该节点到根结点的路径长度*该节点的权。

6: 树的带权路径长度

树中各个叶节点的路径长度*该叶节点的权的和，常用 WPL（Weight Path Length）表示。

二：构建赫夫曼树

上面说了那么多，肯定是为下面做铺垫，这里说赫夫曼树，肯定是要说赫夫曼树咋好咋好，赫夫曼树是一种最优二叉树,

因为他的WPL是最短的，何以见得？我们可以上图说话。