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

今天说下最后一种树，大家可否知道，文件压缩程序里面的核心结构，核心算法是什么？或许你知 道，他就运用了赫夫曼树。

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

一  概念

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

1： 结点的权

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

2： 路径

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

3： 路径长度

一 个路径上的分支数量。

4： 树的路径长度

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

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

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

6:   树的带权路径长度

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

二： 构建赫夫曼树

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

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