常见应用：压缩，最基本的压缩编码的方法，使得总体的编码长度缩短，减少不必要的空间。
什么可以称为哈夫曼树？
公式判断：WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln）
Wi : 表示第i个叶子的节点权值
Li：表示第i个叶子节点到根节点的路径长度
路径长度：通俗点，就是叶子节点到根节点的线段条数
带权路径WPL最小的二叉树就叫做哈夫曼树，也叫最优二叉树。

哈夫曼树构建的步骤：
① 给定n个权值{w1,w2,w3,...,wn}构建只有一个节点的二叉树，从而得到n棵二叉树的集合 F = {T1,T2,T3,...,Tn}
② 选取最小、次小的二叉树分别做左子树和右子树，构建成一棵新的二叉树
③ 删除最小，次小的二叉树，将新的二叉树加入F中
④ 重复② ③ ，知道只剩下一个二叉树为止
哈夫曼树的构建，编码的实现代码
//节点对象
public class Node {
	String data;    //节点标识符
	double weight;
	boolean flag;	//标记是否被使用
	Node leftChild;
	Node rightChild;
	Node parent;
	
	public Node(String data,double weight){
		this.data = data;
		this.weight = weight;
		this.flag = false;
		this.leftChild = null;
		this.rightChild = null;
		this.parent = null;
	}
	
	public Node(String data, double weight, boolean flag, Node leftChild,
			Node rightChild, Node parent) {
		super();
		this.data = data;
		this.weight = weight;
		this.flag = flag;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
		this.parent = parent;
	}

	@Override
	public String toString() {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}
}
/**
 * @author Robert
 */
public class HaffumaTree {
	public static final char BASE = 'A';
	//哈夫曼树构建
	public static Node[] createTree(double[] in){
		int m = in.length*2 - 1;    //第i层有n个叶子节点，那么总的节点最多有2n-1(可以理解为最后一层的节点-1，就是这棵树除这一层，之前层所有节点之和)
		Node[] nodes = new Node[m + 1];
		//初始化结点数组
		for(int i=0;i<in.length;i++) {
			nodes[i] = new Node(String.valueOf(BASE)+i,in[i]);
		}
		for(int i=in.length;i<m;i++) {
			Node firstMin = getMinWeight(nodes, i-1);     //最小
			firstMin.flag = true;
			Node secondMin = getMinWeight(nodes, i-1);    //次小
			secondMin.flag = true;
			nodes[i] = new Node(String.valueOf(i + BASE),firstMin.weight+secondMin.weight); //父节点构建
			nodes[i].leftChild = firstMin;
			nodes[i].rightChild = secondMin;
			firstMin.parent = nodes[i];
			secondMin.parent = nodes[i];
		}
		return nodes;
	}
	
	//查找最小值，也可以使用先排序，然后直接选取前两个元素。
	public static Node getMinWeight(Node[] nodes,int endIndex){
		Node minNode = nodes[endIndex];
		for(int i=0;i<endIndex;i++) {
			if(!nodes[i].flag && nodes[i].weight<minNode.weight){
				minNode = nodes[i];
			}
		}
		return minNode;
	}
	
	//哈弗曼编码，从叶子结点开始
	public static int[][] haffumanCode(Node[] nodes,int n){
		int[][] haffumanCode = new int[n][n];
		for(int i=0;i<n;i++){
			//不知道有多少位，所以选择逆向存储
			int start = n-1;
			Node now = nodes[i];
			Node pa = now.parent;
			for(;pa!=null;now=pa,pa=pa.parent){
				if(pa.leftChild.equals(now)){
					haffumanCode[i][start--] = 0;
				} else {
					haffumanCode[i][start--] = 1;
				}
			}
			//做结尾的标识，方便后续输出
			haffumanCode[i][start--] = -1;
		}
		return haffumanCode;
	}
	
	public static void main(String[] args) {
		double[] w = {7,5,2,4};
		//创建哈夫曼树
		Node[] tree = createTree(w);
		//得到哈夫曼编码
		int[][] code = haffumanCode(tree, w.length);
		System.out.println("==============");
		for(int i=0;i<w.length;i++) {
			System.out.print(tree[i].data + ":");
			for(int j=0;j<code[i].length;j++) {
				if(code[i][j] == -1) {
					for(int k=j+1;k<code[i].length;k++) {
						System.out.print(code[i][k]);
					}
					break;
				}
			}
			System.out.println();
		}
	}
}

总结
① 在现实生活中，有时候哈夫曼树未必比某些二叉树要有优势。 
② 自己用List链表，快排方法构建出来的哈夫曼树，之后不知道怎么来求编码，无奈-.-！，最后还是回归到了数组。
能力有限，如果哪位同学知道，望告知一下。

哈夫曼树是构建哈夫曼编码的一种方法，构造方式如下：

如有队列 {a, b, c, d, e, f, g}

其权值为 {05, 24, 08, 17, 34, 04,13}

求对应a~g的Huffman编码。



 

 













注意一点的是，在构建的时候要把 小的数放左子树，大的放右子树，然后再构建。最后的结构为

a:0011  (编码长度为4)

b:01     (编码长度为2）

c:000   (编码长度为3)

d:101   (编码长度为3)

e:11     (编码长度为2)

f:0010  (编码长度为4)

g:100   (编码长度为3)

e:11     (编码长度为2)

简介
哈夫曼树是一种用来对字符进行编码的数据结构，可以根据字符的使用频率来决定字符的二进制表示，使得转化后的二进制序列尽可能短。

哈夫曼树的具体介绍见此博客用漫画介绍哈弗曼树
接下来介绍哈夫曼树的构造方法，假设给定n个字符及其对应的频率（出现次数），求出用哈夫曼编码后编码串的长度。

比如：
4 //字符个数
a 1
b 2
c 3
d 4

会返回19。（如果不知道怎么算请看上面链接的博客）
c++构造
方法一
首先可以想到用优先队列，将包含频率信息的节点加入队列，然后每次从队列中拿出两个最小的节点a和b，求出频率和，构造新的节点，其左右子节点分别指向a和b，将新节点加入队列。重复此过程直至队列中只剩一个节点。

在上面的步骤中我们模拟哈夫曼树的构造过程，确确实实地构造出一棵树来，接下来只需要由这棵树的根节点开始遍历，找到每个叶子节点，将它们的值（即频率）和深度（即编码长度）的乘积加起来，就是我们要的结果。

时间复杂度：O(nlogn)

ps:这个代码没有释放指针，但是这不是要点，所以忽略了。
#include<iostream>
#include<queue>
#include<unordered_map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct Node {
	long long val;
	Node* left, *right;
	Node(long long val) {
		this->val = val;
		left = NULL;
		right = NULL;
	}
};

struct cmp {
	bool operator()(const Node* a, const Node* b) const{
		return a->val > b->val;
	}
};

long long search(Node* root, long long level) { 
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) return root->val * level;
	return search(root->left, level + 1) + search(root->right, level + 1);
}
int main() {
	long long n;
	cin >> n;
    if (n == 0) {
    	cout << 0;
    	return 0;
    }
    long long arr[n];
    char c;
    for (long long i = 0; i < n; ++i) {
        cin >> c >> arr[i];
    }
    if (n == 1) {
    	cout << arr[0];
    	return 0;
    }
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (long long i = 0; i < n; ++i) {
    	//if (arr[i] <= 0) continue;
    	Node* t = new Node(arr[i]);
    	pq.push(t);
	}
	
	if (pq.size() == 1) {
		cout << pq.top()->val << endl;
		return 0;
	}
	Node* root;
    while(pq.size() > 1) {
        Node* a = pq.top();
        pq.pop();
        Node* b = pq.top();
        pq.pop();
        Node* sum = new Node(a->val + b->val);
        sum->left = a;
        sum->right = b;
        root = sum;
        pq.push(sum);
    }
    cout << search(root, 0) << endl;
}
    
    


方法二
如果不想用优先队列，不想自己写比较函数，可以怎样写呢？

注意到一个规律：每次从队列中拿出最小的两个节点按值相加，得到的新节点的值是递增的，假设我们只用普通的数组来存储最初的节点，并且用另一个数组来存储新增的节点，再用两个指针分别指向两个数组的下标，通过一定的控制（从左边数组拿或从右边数组拿）可以实现。具体请看代码。
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int n;
vector<long long> a[2];
int idx[2];

inline long long popleft(int i) {
	return a[i][idx[i]++];
}

inline long long getmin() {
	if (idx[0] >= (int)a[0].size()) {  
  		return popleft(1);
	}
 	if (idx[1] >= (int)a[1].size()) {
  		return popleft(0);
 	}
 	if (a[0][idx[0]] < a[1][idx[1]]) {
  		return popleft(0);
 	}
 	return popleft(1);
}

int main() {
 	cin >> n;
 	if (n == 0) {
  		cout << 0 << endl;
  		return 0;
 	}
 	long long t1, t2;
 	char c;
 	for (int i = 0; i < n; ++i) {
  		cin >> c >> t2;
  		a[0].push_back(t2);
	}
 	if (n == 1) {
  		cout << t2 << endl;
  		return 0;
 	}
 	sort(a[0].begin(), a[0].end());

 	long long ans = 0;
 	for (int i = 1; i < n; ++i) {
	  	t1 = getmin();
	  	t2 = getmin();
  		ans += t1 + t2;
  		a[1].push_back(t1 + t2);
 	}
 	cout << ans << endl;
 	return 0;
}

时间复杂度依然是O(nlogn）。

总体思路：先构建一棵最小生成树，然后左孩子给它标上‘0’，右孩子标上‘1’，然后从叶子节点追溯到根，存储到数组cd【】中。
构建最小生成树的方法：从权重中选择两个最小的，构成一棵树，并将新生成的权重加入之前的权重中HT【i】.weight中，直到构成一棵完整的二叉树。
话不多说，直接上代码。
#include "stdio.h"
#include "stdlib.h"
#include "string.h"


typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树

typedef char ** HuffmanCode;//动态分配数组存储哈夫曼编码

//不能出现TH[1]->parent的结构
void Select(HuffmanTree HT,int j,int *s1,int *s2)//j为结点的个数，s1为最小值的下标，s2为次小值的下标
{
    int cmin = 100,min = 100;
    int k = 1;
    while(k <= j)
    {
        if((HT[k]).parent == 0)
        {
            if(HT[k].weight < min)
            {
               min = HT[k].weight;
               *s1 = k;
            }
            else if(HT[k].weight >= min&&HT[k].weight <= cmin)
            {
              cmin = HT[k].weight;
              *s2 = k;
            }
        }
        k++;
    }
    HT[*s1].parent = 0;
    HT[*s2].parent = 0;
}


//w用来存放n个字符的权值（w > 0）,构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,int *w,int n)//HC使用三重指针的原因，将HC的值带出去
{
    HuffmanTree p;
    int s1,s2,m,i;//s1为最小数的下标，s2为次小数的下标
    int start,c,f;//start字符最开始的下标，c为
    char *cd;//用来存储哈夫曼编码
    if(n <= 1)
        return;
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
    for(p = HT,i = 1;i <= n;i++,w++)//给前n个结点赋初值,从1开始
    {
        p[i].weight = *w;
        p[i].lchild = 0;
        p[i].rchild = 0;
        p[i].parent = 0;
    }

    //建一棵哈夫曼树
    for(i = n + 1;i <= m;i++)
    {
       Select(HT,i - 1,&s1,&s2);//挑选出最小和次小元素，并用s1，s2带出
       HT[s1].parent = i;
       HT[s2].parent = i;
       HT[i].lchild = s1;
       HT[i].rchild = s2;
       HT[i].weight = HT[s1].weight + HT[s2].weight;
       HT[i].parent = 0;
    }
     //求哈夫曼编码
     (*HC) = (HuffmanCode)malloc((n + 1) * sizeof(char *));//分配n个字符编码的头指针向量
     cd = (char *)malloc(n * sizeof(char));//分配求编码的工作空间
     cd[n - 1] = '\0';
     for(i = 1;i <= n;i++)
     {
         start = n - 1;//编码结束的位置
         for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent) //从叶子到根逆向求编码
         {
             if(HT[f].lchild == c)
                cd[--start] = '0';
             else
                cd[--start] = '1';
          }
          (*HC)[i] = (char*)malloc((n-start) * sizeof(char));//为第i个字符编码分配空间
          strcpy((*HC)[i],&cd[start]);//此处不能传cd，因为下标不一定从0开始
     }
     free(cd);
}

int main()
{
   int w[] = {15,25,45,5,10};
   int n,i;
   HuffmanTree HT = NULL;
   HuffmanCode HC = NULL;
   n = sizeof(w)/sizeof(int);
   HuffmanCoding(HT,&HC,w,n);
   for(i = 1;i <= n;i++)
   {
       printf("%d的哈夫曼编码为:",w[i - 1]);
       printf("%s\n",HC[i]);
   }
    return 0;
}