1、以前没有考虑各个元素的被查找概率，或者默认概率是相等的。
-》当时在树中查找的效率，与树的高度有关。
但，如果是已知被查找概率不同，那么查找效率还应当考虑元素的位置
-》同等高度，应尽量让高概率元素放在上面，使总的带权路径长度wsl最小。
2、典型例子：不定长编码问题
1）不定长编码，比定长编码节约空间
2）但需要避免二义性，避免0和01这样的“前缀码”
3）“前缀码“必须避免，怎么避免？编码时简单借助二叉树这种数据结构，只要字符都在叶节点上就能保证不会有二义性
4）但这样的二叉树很多，带权路径长度WSL有大有小，我们需要的是效率最高的一棵树——哈夫曼树——也就是其中WSL最小的。
3、哈夫曼树==最优二叉树
给定n个权值作为n个叶子结点，WSL最小的树。
4、给与权重不同的元素，如何去构造出哈夫曼树？
- 哈夫曼树就是权重小的放下面，所以从下往上构造
- 把每个元素看成1个现成的哈夫曼树，就有了n个树的集合；然后从中取出2个最小权重的树，合并成大树加入集合，然后再选2个最小权重的……不断的合并，合并，合并！
n个元素，合并进行n-1次。
建树中，选取最小多次发生，所以这个树的集合适合堆来实现：
-》先把所以元素的权重作为ElementType构造成最小堆，借助这个堆可以方便取出权重最小-》取出来构造新的哈夫曼树……
哈夫曼树和堆是两颗不同的树！堆只是辅助！
typedef struct TreeNode* HuffmanTree
struct TreeNode{
int weight;
HuffmnanTree left,right;
}注意这个struct里面并没有真正的数据字段ElementType！
构造哈夫曼树
HuffmnanTree reateHuffman(MinHeap H){
H=buildMinHeap(H)//H只是MinHeap类型，并不一定就已经是最小堆了哦
HuffmnanTree T；
int i;
for(i=1;i<H->size;i++){
T=(HuffmnanTree)malloc(sizeof(struct TreeNode));
T->left=deleteMin(H);//取出最小的子树
T->right=deleteMin(H);//取出第二小的的子树
T->weight=T->left->weight+T->right->weight;
insert(H,T);//合并成新树，加入堆
}
T=deleteMin(T);//循环结束后堆里只有1个树，就是最后一次合并产生的最大的树
return T；
}时间复杂度：O（NlogN）
5、哈夫曼树的特点：
1）有左儿子就有右儿子，建树过程决定的。
2）n个叶子节点，就有n-1个度为2的节点，总结的就是2n-1.
3）不分左右，哈夫曼树左右子树交换仍然是哈夫曼树。
4）哈夫曼树不唯一，但WSL都是一样的。（不过一种特定的生产算法肯定是唯一的）
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/31537575/viewspace-3141811/ ，如需转载，请注明出处，否则将追究法律责任。
