文章结构：基本思路 + 代码实现

1. 基本思路：
   在根结点到叶子结点的路径上，从叶子结点开始依次逆向判断每个结点是左还是右孩子，根据判断结果将编码存储到数组中，直到当前结点没有双亲结点——即根结点。

2. 代码实现：

1）哈夫曼编码类型声明：

typedef struct
{
	int code[MaxSize];
	int start;
}HFCode;

2)实现算法：

void create_huffmancode(HFTree hft[], HFCode hfc[], int n0)
{
	int i, chd, prt;
	HFCode cd;
	for(i=0; i<n0; i++){
		chd = i;
		prt = hft[i].parent;
//哈夫曼树最长叶子编码位数为叶子数-1
		cd->start = n0-1;
		cd->code[cd->satrt+1] = '\0';
		while(prt != -1){
			if(chd == hft[i].lchild)
				cd->code[cd->start++] = 0;
			else
				cd->code[cd->start++] = 1;
			chd = prt;
			prt = hft[prt].parent;
		}
		cd->start++;
		hfc[i] = cd;
	}
}

通过 最小堆，来构建 哈夫曼树，再通过 遍历，借一个数组 来保存 路径 上的 编码。

#include<iostream>
using namespace std;
// 哈夫曼树节点 
typedef struct huff{
	int data;
	struct huff * left;
	struct huff * right;
}*huffman;

// 最小堆 
typedef struct zui_xiao_dui{
	huffman elements[10];
	int num;
}*min_heap;

// 创建 最小堆 
min_heap Create(int num){
 	min_heap H=new struct zui_xiao_dui;
// 	H->elements=new huffman[num+1];	// 从 下标为 1 的地方开始存放 
 	H->num=0;
//  这里 由于 H->elements[0]中的元素 指向的地方未初始化
//  所以切记 不可以 直接 H->elements[0]->data=-10;
	huffman temp=new struct huff;
 	H->elements[0]=temp;
	H->elements[0]->data=-10;		// 定义哨兵 , 这里放一个很小的数 
 	return H;
 } 
 
// 将 H中以 H->Data[p]为根的子堆调整为最大堆 
void PercDown( min_heap H, int p ){ 
    int Parent, Child;
    int X;
    X = H->elements[p]->data; 
	huffman temp=H->elements[p];	//  这里 注意 保存								
    for( Parent=p; Parent*2<=H->num; Parent=Child ) {
        Child = Parent * 2;
        if( (Child!=H->num) && (H->elements[Child]->data>H->elements[Child+1]->data) )
            Child++;  /* Child指向左右子结点的较小者 */
        if( X <= H->elements[Child]->data ) 
			break; 										//  找到了合适位置 
        else  											 
            H->elements[Parent] = H->elements[Child];			//  将那个较大值调上来, 之后在下一层继续找
    }
    H->elements[Parent] = temp;
}
void BuildHeap( min_heap H ){
    int i;
    for( i = H->num/2; i>0; i-- )
        PercDown( H, i );
}

// 取出 最小堆 的最小节点 
huffman DeleteMin(min_heap H){
	int parent,child;
	huffman MinItem,temp;
	MinItem=H->elements[1];			// 取出最小元素
	temp=H->elements[H->num--];	// 指向 最后一个元素 
	
	//寻找 temp 应该放置的地方: parent, 先放在 根节点, 然后 逐层的 寻找 合适的位置
	for(parent=1;parent*2<=H->num;parent=child){
		child=parent*2;
		if((child!=H->num)&&(H->elements[child]->data>H->elements[child+1]->data))
			child++;					//  找出 左右儿子 中 较小的一个 
		if(temp->data<=H->elements[child]->data)	//  如果 temp 比 这个位置的左右儿子 都大, 那 temp 放在这里就是合适的
			break;
		else
			H->elements[parent]=H->elements[child];
	}
	H->elements[parent]=temp;
	return MinItem;
}
// 向 堆中 插入元素
void Insert(min_heap H,huffman item){
// H->Elements[0] 已被 设置为 哨兵 
	int i;
	i=++H->num; 
	for(;H->elements[i/2]->data>item->data;i/=2){			//  将 比 item 大的 父节点元素 向下移 
		H->elements[i]=H->elements[i/2];	 
	}
	H->elements[i]=item;	// 找到要插入的位置 
}

// 建立 哈夫曼 树 
huffman huffman_build(min_heap H){
	huffman T;
	BuildHeap(H);			//  调整为最小堆 	       O(n) 复杂度 
	int count=H->num;
	for(int i=1;i<count;i++){			// Size-1 次 合并
		T=new struct huff;
		T->left=DeleteMin(H);	//  从堆中 取出两个 最小的 
		T->left->data;
		T->right=DeleteMin(H);
		T->right->data;
		T->data=T->left->data+T->right->data;
		Insert(H,T); 	// 构建形成的新的节点插入到堆里 
	}
	T=DeleteMin(H);
	return T;
}

// len 是 路径长
// bian_ma 数组里放的是 编码
void Mid_order(huffman L, int (&bian_ma)[10],int &len){
	if(L){
		if(L->left==NULL&&L->right==NULL){
			cout<<L->data<<ends;
			for(int j=0;j<len;j++){
				cout<<bian_ma[j];
			}
			cout<<'\n';
			len--;
			return;
		}
		bian_ma[len++]=0;
		Mid_order(L->left,bian_ma,len);
		bian_ma[len++]=1;
		Mid_order(L->right,bian_ma,len);
		len-=1;
	}
}

int main(){
	int num;
	cin>>num; // 元素个数
	min_heap P=Create(num);				// 建 堆
	for(int i=1;i<num+1;i++){
		huffman jie_dian =new struct huff;
		cin>>jie_dian->data;
		jie_dian->left=jie_dian->right=NULL;
		P->elements[i]=jie_dian;
		P->num++;
	}
	huffman L=huffman_build(P);			// 建 哈夫曼树
	static int bian_ma[10]={0};
	static int len=0;
	Mid_order(L,bian_ma,len);			//  遍历

}

哈夫曼树

1. 什么是哈夫曼树

2. 创建哈夫曼树

2.1 创建树节点TreeNode

//树的节点
public class TreeNode {
    /**
     * 值
     * 左右孩子
     */
    private int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {

    }

    public TreeNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

}

2.2 构建哈夫曼树

  首先，需要一个list来储存所有要被创建的节点，这里我是用LinkedList来实现List接口。创建完毕，就要对这个list初始化。
构建步骤：

• 创建list，以及根节点root，对list进行初始化。
• 对list进行升序排序，目的是为了找出value最小的两个节点。（我这里为了方便，用的选择排序，可以试试手撕快排）
• 取出list最小的两个节点，然后创建父节点，再子父相连 。（一定要子父相连）
• 最后，初始化根节点。
• (后面中序遍历是为了测试建树是否正确）

//哈夫曼树
public class HfmTree {

    public TreeNode root = new TreeNode();
    public List<TreeNode> list = new LinkedList<>();

    public HfmTree() {
    }

    public HfmTree(int[] value) {
        for(int val:value){
            list.add(new TreeNode(val));
        }
    }

    //排序
    public void sort(){
        for(int i=0; i<list.size()-1; i++)
            for(int j=i+1; j<list.size(); j++){
                if(list.get(i).getValue() > list.get(j).getValue()){
                    TreeNode node = list.get(i);
                    list.set(i,list.get(j));
                    list.set(j,node);
                }
            }
    }

    public void creatTree() {
        while(list.size() > 1) {
            //排序
            sort();
            //取最小的两个
            TreeNode left = list.remove(0);
            TreeNode right = list.remove(0);

            TreeNode node = new TreeNode(left.getValue() + right.getValue());
            //建立子父联系
            node.left = left;
            node.right = right;
            //新节点加入List中
            list.add(node);

        }
        //把根节点初始化
        root = list.remove(0);
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if(root != null) {
            if(root.left != null) {
                inOrder(root.left);
            }
            System.out.print(root.getValue()+" ");
            if(root.right != null) {
                inOrder(root.right);
            }
        }
    }
}

2.3 测试

代码如下：

public class TestHfmTree {

    public static void main(String[] args) {

        int[] value = {1,6,5,8,4};
        //初始化
        HfmTree hfmTree = new HfmTree(value);
        //构建hfm树
        hfmTree.creatTree();
        //中序遍历
        hfmTree.inOrder(hfmTree.root);
    }
}

输出结果：

“手动建树”：

中序遍历：5 10 1 5 4 24 6 14 8，与输出相同，说明哈夫曼树构建正确。