构造哈夫曼树生成哈夫曼编码
 
参考
 程序员小灰-漫画：什么是 “哈夫曼树” ？
 程序员小灰-漫画：“哈夫曼编码” 是什么鬼？
 
编写一个程序exp7-5.cpp，构造一棵哈夫曼树，
输出对应的哈夫曼编码和平均查找长度，
并对下表（表7.8）所示的数据进行验证。

表7.8 单词及出现的频度
单词	The	of	a	to	and	in	that	he	is	at	on	for	His	are	be
频度	1192	677	541	518	462	450	242	195	190	181	174	157	138	124	123
 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

struct TreeNode{
    int weight=0;
    string word;
    string huffmancode;
    struct TreeNode* lChild;
    struct TreeNode* rChild;
};

TreeNode *w_node[15];

class cmp{
    public:
    bool operator()(const TreeNode *n1,const TreeNode *n2)const{
        return n1->weight > n2->weight;
    }
};

//创建哈夫曼树
TreeNode* CreateHuffmanTree(int w[],string s[]){
    priority_queue<TreeNode*,vector<TreeNode*>,cmp > q;
    for(int i = 0;i < 15; i++){
        TreeNode* node = new TreeNode;
        node->lChild = node->rChild = NULL;
        node->weight = w[i];
        node->word = s[i];
        q.push(node);
        w_node[i] = node;  //记录下原本的点
    }
    
    while (q.size()>1)
    {
        TreeNode *parent = new TreeNode;
        parent->lChild = q.top();
        q.pop();
        parent->rChild = q.top();
        q.pop();
        parent->weight = parent->lChild->weight + parent->rChild->weight;
        q.push(parent);
    }
    return q.top();
}

//递归编码
void encode(TreeNode *node,string code){
    if(node==NULL)return;
    node->huffmancode = code;
    encode(node->lChild,code+'0');
    encode(node->rChild,code+'1');
}

//WPL
int getWPL(TreeNode *node,int depth){
    if(node->lChild==NULL&&node->rChild==NULL){
        return node->weight*depth;
    }
    return getWPL(node->lChild,depth+1)+getWPL(node->rChild,depth+1);
}

int main(){
    int weight[] = {1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
    string s[] = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
    TreeNode *root = CreateHuffmanTree(weight,s);
    encode(root,"");
    for(int i=0;i<15;i++){
        cout<<w_node[i]->word<<":"<<w_node[i]->huffmancode<<endl;
    }
    cout<<"平均查找长度:"<<getWPL(root,0);
    system("pause");
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 50
#define MAX 32767
   /* int 8位整数*/
typedef struct{
    char c;                       /* 字符;  */
    int w;                        /* 字符权值;  */
    char *code;                   /*字符的Huffman编码;  */
}HuffmanCode[MaxSize];

typedef struct{
    int weight;                   /* 权值;  */
    int lchild,rchild,parent;
}HTNode,HuffmanTree[MaxSize];

/* ================================================================================  */
void CreateHuffmanTree(HuffmanTree HT,int length,HuffmanCode hc);        /* 生成Huffman树;  */
void SelectHTNode(HuffmanTree HT,int n,int *min1,int *min2);    /* 查找最小和次小序号;  */
void HuffmanCoding1(HuffmanTree HT,int n,HuffmanCode hc);            /* 生成Huffman编码;  */

/* ================================================================================  */
int main()
{
    HuffmanTree HT;       /* Huffman树;  */
    HuffmanCode HC;       /* Huffman编码;  */

    int i,n;
    printf("--------HuffmanCode--------\n");
    printf("\nPlease input the number of char:");
    scanf("%d",&n);
    system("cls");
    printf("the number of char: %2d\n\n",n);
    printf("Input the char and its weight: (e.g.:  \"a16[enter]\" ): \n");
    for(i=1;i <= n;i++)
    {
        while(getchar() != '\n')    NULL;
        printf("No.%2d:  ",i);
        HC[i].c = getchar();
        scanf("%d",&HC[i].w);
    }
    CreateHuffmanTree(HT,n,HC);
    HuffmanCoding1(HT,n,HC);

    printf("\nOutput the Huffman Code:\n");
    for(i = 1;i<=n;i++)
    {
        printf("\n %c :",HC[i].c);
        puts(HC[i].code);
    }
/* 测试Huffman树结构;  */
    printf("\n\nOutput the structure of Huaffman tree:");system("pause");
    printf("\nHT[i]:\tweight\tparent\tLchild\tRchild\n");
    for(i = 1;i<2*n;i++)
    {
        if(i <= n)    printf("(%c)",HC[i].c);
        printf("%2d:\t %2d;\t%2d,\t %2d,\t %2d.\n", i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    }
    getch();
    return 0;
}


/* ================================================================================  */
void CreateHuffmanTree(HuffmanTree HT,int length,HuffmanCode HC)       /* Huffman树初始化;  */
{
    int i;
    int min1,min2;//最小的两个权值

    HT[0].weight = MAX;//哈夫曼树丛0开始储存权值
    
    /*先把叶子节点的双亲，左右变量全部赋值为0*/
    for(i = 1;i <= length;i++)
    {
        HT[i].weight = HC[i].w;//哈夫曼编码里的权值，赋值给哈夫曼树里面的权值
        HT[i].lchild = HT[i].rchild = HT[i].parent = 0;//双亲，左右子树全部赋值为0
    }
    
    /*整个树的节点数是2*length-1,刨去第0个，就是2*length
    上面一个循环已经把叶子的权值存放
    剩下的节点就是树里面非叶子节点，里面不存放权值，
    初始化的时候，这里先把左右、双亲变量赋值为0*/
    for(;i < 2*length;i++)            /* i初值 = length+1;  */
    {
        HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
    }

    for(i = length+1;i < 2*length;i++)
    {
        SelectHTNode(HT,i,&min1,&min2);
        HT[min1].parent = i;
        HT[min2].parent = i;
        HT[i].lchild = min1;
        HT[i].rchild = min2;
        HT[i].weight = HT[min1].weight + HT[min2].weight;
    }
}
/*==========================================================================*/
void SelectHTNode(HuffmanTree HT,int n,int *min1,int *min2) /* 查找最小和次小序号;  */
{
    int i;
    *min1 = *min2 = 0;
    for(i = 1;i < n;i++)
    {
        if(HT[i].parent == 0)
        {
           /* printf("\n i=%d,*min1=%d, HT[*min1].weight=%d",i,*min1,HT[*min1].weight);
            printf("\n i=%d,*min2=%d, HT[*min2].weight=%d",i,*min2,HT[*min2].weight);  */
            if(HT[*min1].weight >= HT[i].weight)
            {
                *min2 = *min1;
                *min1 = i;
              /*printf("\n i=%d: *min1=%d, *min2=%d ",i,*min1,*min2); */

            }
            else
                if(HT[*min2].weight > HT[i].weight)
                 {
                   *min2 = i;
                 /* printf("\n i=%d: *min1=%d, *min2=%d ",i,*min1,*min2);  */
                  }
        }
    }
}

/* 生成Huffman编码===============================================================  */
void HuffmanCoding1(HuffmanTree HT,int n,HuffmanCode HC)
{
  int i,start,c,f;
  char *cd;
  cd=(char * )malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
  cd[n-1]='\0';
  for(i=1;i<=n;i++)                      /* 逐个字符求Huffman编码,注意i从1开始 */
  {
    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].code =(char*) malloc((n-start)*sizeof(char));  /* 为第i个字符编码分配空间 */
     strcpy(HC[i].code,&cd[start]);   /* 从cd 复制到HC[i].code */

  }
  free(cd);

}
/* ================================================================================  */
 
 

 
#include <iostream>
using namespace std;
#define MAX 50
#define MAXNUM 60
typedef struct	//哈夫曼树结点结构
{
	char data;
	int weight;
	int parent;
	int lchild;
	int rchild;
}HuffNode;

typedef struct
{
	char cd[MAX];	//存放字符的编码
	int start;	//编码的起始位置
}HuffCode;

void Select(HuffNode huffTree[], int k, int& i1, int& i2) {
	/*选择根结点权值最小的两个结点。*/
	int i, j;
	for (i = 0; i < k; i++)
		if (huffTree[i].parent == -1) { i1 = i; break; }
	for (j = i + 1; j < k; j++)
		if (huffTree[j].parent == -1) { i2 = j; break; }
	for (i = 0; i < k; i++)
		if ((huffTree[i].parent == -1) && (huffTree[i].weight < huffTree[i1].weight) && (i2 != i))
		{
			i1 = i;
		}
	for (j = 0; j < k; j++)
		if ((huffTree[j].parent == -1) && (huffTree[j].weight < huffTree[i2].weight) && (i1 != j))
		{
			i2 = j;
		}
}

void HuffmanTree(HuffNode huffTree[], int n) {
	/*此处完成构造哈夫曼树huffTree []*/
	int i, k;
	// 初始化
	for (i = 0; i < 2 * n - 1; i++)
	{
		huffTree[i].parent = -1;
		huffTree[i].lchild = -1;
		huffTree[i].rchild = -1;
	}

	#if 0
	for (k = n; k < 2 * n - 1; k++) {
		int i1, i2;
		Select(huffTree, k, i1, i2);
		/* 在 huffTree [0] ~ huffTree [k-1] 的范围内选择两个parent为-1且
		weight最小的结点，其序号分别赋值给i1、i2返回 */
		huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
		huffTree[i1].parent = k; huffTree[i2].parent = k;
		huffTree[k].lchild = i1; huffTree[k].rchild = i2;
	}
	#else
		//优化算法	
		/*
			// 基本思想：先排序，然后每次前面在顺序取权值，k+1和后面新增的比较，
			// 如果前面k+1比后面小，取前面k 和 k+1，且取完相加等到新的 i_12，
			// 如果后面的比k+1小，则取k 和 后面的 i_12-1 相加得到新的i_12

			1. 排序
			2. 依次选2个相加得到最小权值
				2.1 判断k++是否 大于等于n，如果是则退出
		*/
	// 排序
	HuffNode temp;
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			if (huffTree[i].weight > huffTree[j].weight)
			{
				temp = huffTree[i];
				huffTree[i] = huffTree[j];
				huffTree[j] = temp;
			}
		}
	}

	int i1, i2;
	// i1, i2 之和的下标
	int i_12 = n - 1;
	for (k = 0; k < n ; k++) {
		i_12++;
		i1 = k;

		// 如果i_12存在，判断 i_12 与 k+1 的权值大小
		if (huffTree[i_12 - 1].weight < huffTree[k + 1].weight && huffTree[i_12 - 1].lchild != -1)
			i2 = i_12 - 1;
		else
		{
			// index 的权值大于 i1+1, 选择小的权值
			i2 = ++k;

			if (i2 >= n)
			{
				// 表示i1 是最后一个值，与i_12进行相加,得到最终值
				i2 = i_12 - 1;
				huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
				huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
				huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;

				break;
			}
			else
			{
				// 第一次只有1个权值和
				if (k > 2)
				{
					huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
					huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
					huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;

					i1 = i_12;
					i2 = i_12 - 1;
					i_12++;
				}
			}
		}

		huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
		huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
		huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;
	}
	#endif
}


char* strcut(char* dest, char* src, int start)
{
	/*
		功能: 截取start 后面的字符串
	*/
	if (dest == NULL || src == NULL)
		return NULL;

	char* pdst = (char*)dest;
	char* psrc = (char*)src + start;

	if (start > 0)
	{		
		while (*psrc != '\0')
		{
			*pdst++ = *psrc++;
			if (*psrc == '\0')
			{
				*pdst = '\0';
				break;
			}
		}
	}
	else
	{
		dest = psrc;
	}

	return dest;
}


void Encoding(HuffNode ht[], HuffCode hcd[], int n)
{

	//此处完成哈夫曼编码以及输出哈夫曼编码


	// 计算 n 字符的 编码  左为0， 右为1
	// 每个叶子结点即为一个字符(数组前n个结点)
	

	// 从第一个结点开始找
	for (int i = 0; i < n; ++i)
	{
		//编码的起始位置
		hcd[i].start = n - 1;

		hcd[i].cd[hcd[i].start] = '\0';

		// c 表示当前结点
		int c = i;
		// f 表示当前结点的父结点
		int f = ht[i].parent;


		while (f != -1)	// 根结点退出循环
		{
			if (ht[f].lchild == c)
				// 当前孩子结点是当前父节点的左孩子，则编码0
				hcd[i].cd[--hcd[i].start] = '0';
			else
				// 当前孩子结点是当前父节点的左孩子，则编码1
				hcd[i].cd[--hcd[i].start] = '1';

			// 循环直到根结点
			c = f;
			f = ht[f].parent;
		}

		//hcd[i] = strcpy(hcd[i].cd, &cd[start])
		char* dest = new char[n - hcd[i].start];
		dest = strcut(dest, hcd[i].cd, hcd[i].start);

		cout << ht[i].data << ": " << dest << endl;

	}
	
}


int main()
{
	int n, i;
	HuffNode huffTree[MAXNUM];//创建huffTree类型的一维数组，用于存储哈夫曼树
	HuffCode hcd[MAXNUM];//创建hcd类型的一维数组，每个数组元素存储一个叶子结点的哈夫曼编码
	cout << "请输入字符个数" << endl;
	cin >> n;
	for (i = 0; i < n; i++)
	{
		cout << "输入第" << i + 1 << "个字符:";
		cin >> huffTree[i].data;
		cout << "输入第" << i + 1 << "个字符的权值:";
		cin >> huffTree[i].weight;
	}

	HuffmanTree(huffTree, n);//构造哈夫曼树

	Encoding(huffTree, hcd, n);//求得哈夫曼树huffTree的对应的哈夫曼编码，并输出每个叶子结点的哈夫曼编码

	return 0;
}

 
 
1.任务要求
 
将英文字符的统计概率作为权值。编程得出哈夫曼的码表；输入一段英文字符，利用码表对其编码、译码。
 
开发环境: VS2015（C++）
 
2.数据处理
 
数据归一化，使各英文字符概率之和为1。由于文献中各字符概率之和大于1，对数据进行归一化。将当前各字符概率值除以当前的概率之和，得出的结果保留小数点后5位，作为新的概率值（相当于权值，这步可以省略，不影响最后结果）。
 
                                                        
 
归一化后个字符概率如下图所示。经过检验，归一化之前的概率之和：1.2069；归一化后的概率之和：1.0000。
 
 
3.建立哈夫曼树
 
哈夫曼树（Huffman）即最优二叉树，它是在n个权重作为叶子结点的数值构成的二叉树中，选取并实现带权路径长度（WPL）最短的二叉树。要构造一棵最优二叉查找树就应在离根结点比较近的地方放置查找概率高的结点。
 
定义两个结构体，分别用于存储字符信息和哈夫曼树结点信息。 
 
typedef struct Alphabet
{	//字符结构体
	char data;//字符	
	double probability;//概率值
	char *code;//编码
} English;
 
节点信息结构体，用于生成哈夫曼树和实现译码操作。
 
typedef struct Node
{  //节点结构体
	double weight;//权值
	int id;//编号
	bool visit;//是否加入树中
	struct Node *right;//右子节点
	struct Node *left;//左子节点
	const English *point;//字符信息
} *HuffmanTree;
 
一个哈夫曼树如果存在n个待编码的叶子节点，一定存在n-1个非叶子节点。节点总数为2n-1个[2]。
 
首先初始化所有节点，分配存储空间。定义0-26号节点为叶子节点，point指针按照概率值的大小依次指向字符结构体元素。27-52号节点非叶子节点，point指针指向NULL，左右子节点也为NULL。
 
然后，进行n-1次循环建立哈夫曼树。首先在结构体数组中找出当前权值最小的两个节点（当新生成的节点权值和叶子节点相同时，选择之前的叶子节点），返回它们的位置到minP数组中。再将这两节点合成新的节点，用两者的概率之和合成新节点的权值。
 
生成树的关键代码如下所示。
 
for (i = N; i < total; ++i){
	FindLittleNode(HT, i - N);//找出当前概率值最小的两个节点
	(*HT)[i].left = (struct Node *)(*HT + minP[0]);
	(*HT)[i].right = (struct Node *)(*HT + minP[1]);
	(*HT)[i].weight = (*HT + minP[0])->weight + (*HT + minP[1])->weight;
	(*HT)[i].point = NULL;
	printf("%2d \t %.4f \t %2d \t %.4f \t %4d \t\t %.4f\n", minP[0], (*HT + minP[0])->weight, minP[1], (*HT + minP[1])->weight, i,(*HT)[i].weight);
	cout << endl;
}
 
寻找最小概率值节点，核心代码如下所示。一次遍历，选出将当前未被加入树中的两个最小节点。得出它们的位置信息。
 
for (int i = n + 1; i < n + N; i++){
		if ((*tree)[i].visit){
			continue;
		}
		if ((*tree + i)->weight < min1){
			min2 = min1;
			minP[1] = minP[0];
			//将最小数值及位置赋值到min1和minP[0]中
			min1 = (*tree + i)->weight;
			minP[0] = i;
		}else if ((*tree + i)->weight < min2){
			//次小值节点信息
min2 = (*tree + i)->weight;
			minP[1] = i;
		}
}
 
4.生成哈夫曼码表
 
在哈夫曼树创建完成后，利用递归算法进行前序遍历。在遍历过程中，将得出的编码序列存储在字符结构体中。
 
如果左节点存在，编码序列末尾添加0；如果右节点存在，编码序列末尾添加1；如果节点为叶子节点，将当前遍历得出的编码序列复制到字符结构体的编码信息中。关键代码如下所示。
 
void enCode(HuffmanTree HT, string code, English *en){
	if (HT){
		if (HT->point != NULL){
			(en + HT->id)->code = (char *)malloc(sizeof(char) * code.length());
			strcpy((en + HT->id)->code, code.c_str());
		}
		enCode(HT->left, code + "0", en);
		enCode(HT->right, code + "1", en);
	}
}
 
5.编码
 
在生成码表的时候已将字符编码信息保存至字符结构体中。根据输入的英文序列遍历一次即可得出，程序如下所示。
 
首先将字符结构体按照字符ASCII值排序（升序）。
读取需要编码是英文字符序列，逐一判断。如果是空格符，取结构体数组的第一个编码；否则，取字符结构体数组第n位的编码。
将读取的编码逐一加入新的string对象中，可得到编码的01序列。
string AfterEncode(English *en, string str){
	string res;
	string::iterator it = str.begin();
	while (it != str.end()){
		if (*it == ' '){
			res += en->code;
		}else{
			res += (en + (*it) - 64)->code;
		}
		++it;
	}
	return res;
}
 
将生成的01序列，按照bit来存储传输可以显著降低原英文序列的大小。
 
6.译码
 
经过编码后的英文字符序列变为了‘0’‘1’序列，将得出的序列根据哈夫曼树遍历一次即可解出原始英文序列。程序流程如下图所示。
 
首先判断当前编码序列是0还是1。若为0，访问左节点；若为1，访问右节点。以此进行遍历，直到访问到叶子节点。再回到根节点进行下一编码序列的解码。
 
 
string AfterDecCode(HuffmanTree HT, string encstr){
	string decstr;
	HuffmanTree p;
	p = HT + 52;//指向根节点
	string::iterator it = encstr.begin();
	while (it != encstr.end()){
		if (*it == '0')
			p = p->left;
		if (*it == '1')
			p = p->right;
		if (p->point != NULL){
			decstr += p->point->data;//回到根节点
			p = HT + 2 * N - 2;}
		++it;
	}
return decstr;}
 
7.结果展示
 
7.1建树过程
 
 
7.2 哈夫曼树结构
 
 
7.3 码表
 
 
7.4 编译码过程
 
自己定义输入一段英文字符序列（不含空格以外的其它符号），程序会自动将输入的序列转换为大写字符。
 
 
首先，程序会自动打印出编码后的01序列；然后根据该01序列译码得出原始的英文序列
 
 
8.  程序示例
 
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <malloc.h>
#include <bitset>
using namespace std;

#define N 27
#define _MAX INFINITY

int main()
{
	English en[27] = { { ' ', 0.2 },{ 'A', 0.063, },{ 'B', 0.0105 },{ 'C', 0.023 },{ 'D', 0.035 },{ 'E', 0.105 },{ 'F', 0.225 },
	{ 'G', 0.011 },{ 'H', 0.047 },{ 'I', 0.055 },{ 'J', 0.001 },{ 'K', 0.003, },{ 'L', 0.029 },{ 'M', 0.021 },{ 'N', 0.059 },
	{ 'O', 0.0654 },{ 'P', 0.0175 },{ 'Q', 0.001 },{ 'R', 0.054 },{ 'S', 0.052 },{ 'T', 0.072 },{ 'U', 0.0225 },
	{ 'V', 0.008 },{ 'W', 0.012 },{ 'X', 0.002 },{ 'Y', 0.012 },{ 'Z', 0.001 }
	};
	//数据归一化，使概率和为1
	double sum = 0;
	for (int i = 0; i < N; ++i) {
		sum += en[i].probability;
	}
	cout << "概率之和： " << sum << endl;
	
	for (int i = 0; i < N; ++i) {
		en[i].probability = en[i].probability / sum;
		en[i].probability = (int)(en[i].probability * 100000 + 0.5)*1.0/ 100000.0;
	}
	sum = 0;
	for (int i = 0; i < N; ++i) {
		sum += en[i].probability;
	}
	printf("归一化后，概率之和：%.4f\n", sum);


	//英文字符排序
	sort(en, en + N, compare1);
	//输出英文字符信息
	//for (char i = 0; i < 27; ++i) {
	//	cout << en[i].data << "  " << en[i].probability << endl;
	//}
	HuffmanTree Tree;
	
	CreateHuffmanTree(&Tree, en);

	cout << "生成哈夫曼树结构如下：" << endl;
	PrintHuffmanTree(Tree + 52);
	cout <<"哈夫曼码表如下"<< endl;
	enCode(Tree + 52, "", en);

	cout << "输入一段英文字符" << endl;
	string myWords, encString, decString;
	getline(std::cin, myWords, '\n');//读取到换行符才停止

	transform(myWords.begin(), myWords.end(), myWords.begin(), ::toupper);
	cout << "输入字符如下(大写)：" << endl;
	cout << myWords << endl;
	//按照字符ASCII值排序
	sort(en, en + N, compare2);
	//输出英文字符码表信息
	cout << "字符\t权重\t编码" << endl;
	for (char i = 0; i < N; ++i)
	{
		cout << en[i].data << "\t" << en[i].probability << "\t" << en[i].code << endl;
	}
	cout << "编码之后：" << endl;
	encString = AfterEncode(en, myWords);

	cout << encString << endl;

	sort(en, en + N, compare1);
	cout << "解码之后：" << endl;
	decString = AfterDecCode(Tree, encString);
	cout << decString << endl;
	system("pause");
	return 0;
}