什么是树？
树是一种数据结构，它是由n(n=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
二叉树
二叉树（Binarytree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
完全二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
满二叉树
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。
最优二叉树（哈夫曼树）
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
今天要说的是这个哈夫曼树。
一个经典例子就是，将学生的成绩分类成绩：≥90分:A，80～89分:B，70-79分:C，60-69分:D，＜60分:E。
正常的写法就是：
一个一个判断，60到90，大概的流程是这样↓
这样没问题，数据量少的话，但是如果像我们学校一届一万学生的，或者甚至有些更多的，那就可能会有性能上的问题。
如果学生的总成绩数据有条，则5％的数据需1次比较，15％的数据需2次比较，40％的数据需3次比较，40％的数据需4次比较，因此个数据比较的次数为：
(5％＋2×15％＋3×40％＋4×40％)＝次
那换一种树的结构会不会好点能，就是性能上得到优化的，次判断，甚至更少？
酱紫试试。
×(2×(5％＋15％＋40％)＋2×(30％+10％))＝次
诶，确实变少了，那有没有可能找到一棵最少次数的树呢？
哈夫曼：？？？
概念和术语：
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。
直接上构造方法和思路：
根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
在F中删除这两棵树,同时将新的二叉树加入F中.
重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)
以上述的学生分数为例（来认真的了）：
1、带权重的的每个根节点。
2、找到最小的两个节点，合起来，形成新的节点，
3、在新的节点堆里（第一行），拿到最小两个，重新又组成新的节点。
4、同上。
5、最后基本就是这么个情况了。
这！就是哈夫曼树！
这！就是最优二叉树！
计算一线现在的WLP是多少：
×(40%×1+30%×2+15%×3+(5%+10%)×4)＝次
wodetian！如此一换来换去的，就把原来的次的判断优化成了次，优化了大于三分之一，如此一来这东西的作用就出来了。不得不为这老哥直呼内行。
拓展（哈弗曼编码）：
该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
大二时的离散数学考过一个哈夫曼编码的例子，这个就不写了。
就是相当于这种↑，各个马为，A：0，D：10，B：，C：
思路就是哈夫曼树的差不多思路。
如果要输入ABBCBDDA要怎么构造树呢？
ABCD的权重分别是，A：0.25，B：0.，C：0.，D：0.25
按照上面的构造法，结果就是：
编码：A：，B：0，C：，D：10
电文（ABBCBDDA）：1001010
译码也很简单，就是根据编码的01数字逐个从树的顶往下走，直到叶子结点就是一个马，以此类推。
------------------------------------完--------------------------------------
何里玉之巴黎铁塔反转再反转
XUANXUAN丶