6.11哈夫曼树及其应用
将大文档进行压缩可以将其空间减少，简单来说，就是把我们要压缩的文本进行了重新的编码，以减少不必要的空间
赫夫曼编码 —— 一种最基本的压缩编码方法
6.11.1哈夫曼树的基本概念
路径长度
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
下图中的二叉树a中,根结点到结点D的路径长度就为4
二叉树中根结点到结点D的路径长度为2
树的路径长度就是从树根到每一结点的路径长度之和
二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20
二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16
完全二叉树是路径长度最短的二叉树
权
权(weight):也叫权重，从英文意思即可知道，将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度
从根节点到该节点的路径长度与该节点的权的乘积
树的带权路径长度
树中所有叶子结点的带权路径长度之和。
哈夫曼树:最优树
带权路径长度(WPL)最短的树
"带权路径长度最短”是在"度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。
哈夫曼树:最优二叉树
带权路径长度(WPL)最短的二叉树
因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法。
满二叉树不一定是哈夫曼树
具有相同带权结点的哈夫曼树并不唯一
6.11.2哈夫曼树的构造
1.先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即: A5,E10，B15，D30， C40。
2.取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，新结点的权值为两个叶子权值的和5+10=15。
3.将N1当做A与E,插入有序序列中，保持从小到大排列。即: N15, B15
4.重复步骤2。将N1与B作为一个新节点N2的两个子结点N2的权值=15+15=30
5.将N2当做N1与B,插入有序序列中，保持从小到大排列。即: N230，D30，C40
6.重复步骤2。将N2与D作为一个新节点N3的两个子结点。N3的权值=30+30=60
7.将N3当做N2与D,插入有序序列中，保持从小到大排列。即: C40，N360
8.重复步骤2。将C与N3作为一个新节点T的两个子结点由于T即是根结点,完成赫夫曼树的构造。
二叉树的带权路径长度WPL=40x1+30x2+15x3+10x4+5x4=205。与上面的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。
6.11.3哈夫曼编码
哈夫曼树的左分支代表0，右分支代表1，从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是哈夫曼编码
例题如下：
思路如下：
1、要传输的字符集D = {C，A，S，T，；}
字符出现的频率 w = {2,4,2,3,3}
2、把他们出现的频率作为权重，权重大的离根节点近，小的相反进行构造带权二叉树
3、用哈夫曼编码的思想左分支代表0，右分支代表1，每个子节点都是如此
4、最后从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码
6.12总结
知识点好多啊，连续写了两天
（1）概念回顾
最开始有树的定义，讲到了递归在树定义中的应用。
还有很多概念如：
子树、结点、度、叶子、分支结点、双亲、孩子、层次、深度、森林…理解记忆！！！
在写一遍易忘的概念：
**度：结点所拥有的子树的个数称为该结点的度(Degree); **
树中各结点度的最大值称为该树的度； 称度为m的树为m叉树。
深度：深度是指所有结点中最深的结点所在的层数。
层次：一个结点的层次直观上来说就是其所在的行，其中根结点层次为1（第一行），其子结点层次为2（第二行），以此类推，第1行的结点为1。
森林，指的是由 n（n>=2）棵互不相交的树组成的集合
（2）遍历的方式
遍历是二叉树最重要的一门学问，前序、中序、后序以及层序遍历不过
递归的实现比较高级！
（3）树、森林
树、森林看似复杂，其实它们都可以转化为简单的二叉树来处理，我们提供了树、森林与二叉树的互相转换的办法，这样就使得面对树和森林的数据结构时，编码实现成为了可能。
（4）二叉树的应用
哈夫曼树和哈夫曼编码
哈夫曼树也就是带权路径的二叉树
