哈夫曼树的生成以及编码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<iostream>
using namespace std;

typedef int ELEMTYPE;
typedef struct HuffmanTree
{
	ELEMTYPE weight;
	char value;
	struct HuffmanTree* lchild;
	struct HuffmanTree* rchild;
}HuffmanNode;

// 构建哈夫曼树
HuffmanNode* createHuffmanTree(int* a,char* b,int n)
{
	int i, j;
	HuffmanNode **temp, *hufmTree;
	temp = (HuffmanNode **)malloc(n * sizeof(HuffmanNode));
	for (i = 0; i < n; ++i)     // 将数组a中的权值赋给结点中的weight
	{
		temp[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));
		temp[i]->weight = a[i];
		temp[i]->lchild = temp[i]->rchild = NULL;
		temp[i]->value = b[i];
	}

	for (i = 0; i < n - 1; ++i)       // n-1次合并
	{
		int small1 = -1, small2;      // small1、small2分别作为最小和次小权值的下标
		for (j = 0; j < n; ++j)         // 先将最小的两个下标赋给small1、small2（注意：对应权值未必最小）
		{
			if (temp[j] != NULL && small1 == -1)
			{
				small1 = j;
				continue;
			}
			else if (temp[j] != NULL)
			{
				small2 = j;
				break;
			}
		}
		if (small1 > small2)
		{
			int t = small1;
			small1 = small2;
			small2 = t;
		}
		for (j = small2; j < n; ++j)    // 比较权值，挪动small1和small2使之分别成为最小和次小权值的下标
		{
			if (temp[j] != NULL)
			{
				if (temp[j]->weight < temp[small1]->weight)
				{
					small2 = small1;
					small1 = j;
				}
				else if (temp[j]->weight < temp[small2]->weight)
				{
					small2 = j;
				}
			}
		}
		hufmTree = (HuffmanNode*)malloc(sizeof(HuffmanNode));
		hufmTree->weight = temp[small1]->weight + temp[small2]->weight;
		hufmTree->lchild = temp[small1];
		hufmTree->rchild = temp[small2];

		temp[small1] = hufmTree;
		temp[small2] = NULL;
	}
	return hufmTree;
}


// 递归进行哈夫曼编码
void HuffmanCode(HuffmanNode* hufmTree, int depth,int*code)      // depth是哈夫曼树的深度
{
	if (hufmTree)
	{
		if (hufmTree->lchild == NULL && hufmTree->rchild == NULL)
		{
			printf("%c的哈夫曼编码为 ",  hufmTree->value);
			int i;
			for (i = 0; i < depth; ++i)
			{
				printf("%d", code[i]);
			}
			printf("\n");
		}
		else
		{
			code[depth] = 0;
			HuffmanCode(hufmTree->lchild, depth + 1,code);
			code[depth] = 1;
			HuffmanCode(hufmTree->rchild, depth + 1,code);
		}
	}
}



int main()
{
	int i, n;
	char string[100];
	printf("请输入叶子结点的个数：\n");
	

	scanf("%d", &n);
	
	int* arr;
	arr = (int*)malloc(n * sizeof(ELEMTYPE));
	printf("请输入%d个叶子结点的权值及其各自代表的字符：\n", n);
	for (i = 0; i < n; ++i)
	{
		printf("第%d个",i+1); 
		scanf("%d", &arr[i]);
		scanf("%c", &string[i]);
	}
	HuffmanNode* hufmTree = NULL;
	hufmTree = createHuffmanTree(arr,string,n);
	int code[100];
	printf("\n各叶子结点的哈夫曼编码为：\n");
	HuffmanCode(hufmTree, 0,code);

	return 0;
}




注意输入时权值与字符之间不加符号，否则会将空格当作字符，可以加一个getchar（）来实现。
本文改编自

https://blog.csdn.net/F__shigang/article/details/65442550

删改了一些内容。

首先构造哈夫曼树结构体，初始化哈夫曼树的四个无符号整型域，输入文本，统计各个字符的权值，然后构建哈夫曼树，从根到叶子逆向求哈夫曼树的编码。



#include"stdio.h"
#include"string.h"
#include"malloc.h"
#include"iostream"
using namespace std;
typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffTree;
typedef  char  **HuffCode;


void Select(HuffTree &Ht, int m, int &S1, int &S2)     
{/*
 Select函数，每次从前面数据中选择2个权值(weight值)最小的，将 
最小的两个下标赋给s1,s2 

*/
    int j;
    S1 = 0;
    S2 = 0;
    for (j = 1; j <= m; j++)
    {
        if (Ht[j].parent == 0 && Ht[j].weight != 0)
        {
            if (Ht[j].weight<Ht[S1].weight)
                S1 = j;
        }
    }
    for (j = 1; j <= m; j++)
    {
        if (Ht[j].parent == 0 && j != S1&&Ht[j].weight != 0)
        {
            if (Ht[j].weight<Ht[S2].weight)
                S2 = j;
        }
    }

} 



void HuffmanCoding(HuffTree &Ht,HuffCode &Hc,int n){  //哈夫曼编码函数 
if(n<=1)return;
int m,i,s1, s2;
HuffTree p;
m =2*n-1; 
Ht = (HuffTree)malloc((m + 1) * sizeof(HTNode));
char ch[100];
for (p = Ht + 1, i = 1; i <= m; ++i, ++p) {     //初始化哈夫曼树各个值 
    p->weight = 0;
    p->parent = 0;
    p->lchild = 0;
    p->rchild = 0;
}
cin >> ch;                                   //读入一段文本 
for (int i = 0; ch[i] !='\0'; i++) {
    Ht[ch[i] - 'a'+1].weight++;               //当文本还没有结束时，统计各个字符的权值 
}
for(i=n+1;i<=m;++i){                         //建哈夫曼树 
    Select(Ht,i-1,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;
}

// 从叶子到根逆向求每个字符的哈夫曼编码 
Hc=(HuffCode)malloc((n+1)*sizeof(char*));
char * cd=(char*)malloc((n)*sizeof(char));
int c,f;
cd[n-1]='\0';                 //编码结束符 
int start;
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';
    }
    //cd[n-1]='\0';
    Hc[i]=(char *)malloc((n-start)*sizeof(char));
    strcpy(Hc[i],&cd[start]);
}
free(cd);

}

void show(HuffCode &Hc, int n)//输出哈夫曼编码  
{
    int i, k;
    cout<<"  输出哈夫曼编码:\n"; //输出哈夫曼编码  
    for (i = 1; i<=n; i++)
    {
            cout<< Hc[i];
            cout<<"\n"; 
    }

}




然后在主函数中调用，加入输入输出语句即可



#include"1.h"

using namespace std;

int main()
{
    HuffTree ht;
    HuffCode hc;
    int n;
    cout << "请输入文本";
    HuffmanCoding(ht,hc,26);
    show(hc,26);
    system("pause");
}

一、什么是哈夫曼树？

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。用一幅图来说明：



它们的带权路径长度分别为：

图a： WPL=5*2+7*2+2*2+13*2=54

图b： WPL=5*3+2*3+7*2+13*1=48

可见，图b的带权路径长度较小，可以证明图b就是哈夫曼树(也称为最优二叉树)。

二、如何构建哈夫曼树

一般按下面步骤构建：

1，将所有左，右子树都为空的作为根节点。

2，在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。

3，从森林中删除这两棵树，同时把新树加入到森林中。

4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程：



三、哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示"0"码，指向右子树的分支表示"1"码，取每条路径上的"0"或"1"的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。

上图例子来说：

A，B，C，D对应的哈夫曼编码分别为：111，10，110，0

用图说明如下：



记住，设计电文总长最短的二进制前缀编码，就是以n个字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。

四、算法实现

/**

*    实验题目:

*        构造哈夫曼树和生成哈夫曼编码

*    实验目的:

*        领会哈夫曼的构造过程以及哈夫曼编码的生成过程

*    实验内容:

*        设计程序，构造一颗哈夫曼树，输出对应的哈夫曼

*    编码和平均查找长度。并用如下数据进行验证：

*    单词以及出现的频度

*    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

*    备注:二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)

*/

#include <stdio.h>

#include <string.h>

#define N   (50)        // 树中叶子结点数最大值

#define M   (2 * N - 1) // 树中结点总数最大值

typedef struct

{

    char data[5]; // 结点值

    int weight; // 权重

    int parent; // 双亲结点

    int lchild; // 左孩子结点

    int rchild; // 右孩子结点

}HTNode; // 声明哈夫曼树结点类型

typedef struct

{

    char cd[N]; // 存放哈夫曼编码

    int start;

}HCode; // 声明哈夫曼编码类型

/*-------------由含有n个叶子结点的ht构造完整的哈夫曼树-----------------*/

static void create_huffman_tree(HTNode ht[], int n)

{

    int i;

    int k;

    int lnode;

    int rnode;

    int min1;

    int min2;

    // 所有结点的相关域设置初值为-1

    for(i = 0; i < 2 * n - 1; i++)

        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;

    for(i = n; i < 2 * n - 1; i++) // 构造哈夫曼树的分支结点

    {

        min1 = min2 = 32767;

        lnode = rnode = -1;

        for(k = 0; k <= i - 1; k++) // 查找最小和次小的结点

        {

            if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找

            {

                if(ht[k].weight < min1)

                {

                    min2 = min1;

                    rnode = lnode;

                    min1 = ht[k].weight;

                    lnode = k;

                }

                else if(ht[k].weight < min2)

                {

                    min2 = ht[k].weight;

                    rnode = k;

                }

            }

        }

        ht[lnode].parent = i; // 合并两个最小和次小的结点

        ht[rnode].parent = i;

        ht[i].weight = ht[lnode].weight + ht[rnode].weight; // 计算双亲结点的权重

        ht[i].lchild = lnode; // 设置双亲结点的左孩子

        ht[i].rchild = rnode; // 设置双亲结点的右孩子

    }

}

/*-------------由哈夫曼树ht构造哈夫曼编码hcd-----------------*/

static void create_huffman_code(HTNode ht[], HCode hcd[], int n)

{

    int i;

    int f;

    int c;

    HCode hc;

    for(i = 0; i < n; i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码

    {

        hc.start = n;

        c = i;

        f = ht[i].parent;

        while(f != -1) // 循环直到树根结点

        {

            if(ht[f].lchild == c) // 处理左孩子结点

                hc.cd[hc.start--] = '0';

            else // 处理右孩子结点

                hc.cd[hc.start--] = '1';

            c = f;

            f = ht[f].parent;

        }

        hc.start++; // start指向哈夫曼编码最开始字符

        hcd[i] = hc;

    }

}

/*-------------输出哈夫曼编码-----------------*/

static void display_huffman_code(HTNode ht[], HCode hcd[], int n)

{

    int i;

    int k;

    int sum = 0;

    int m = 0;

    int j;

    printf("输出哈夫曼编码:\n");

    for(i = 0; i < n; i++)

    {

        j = 0;

        printf("      %s:\t", ht[i].data);

        for(k = hcd[i].start; k <= n; k++)

        {

            printf("%c", hcd[i].cd[k]);

            j++;

        }

        m += ht[i].weight;

        sum += ht[i].weight * j;

        printf("\n");

    }

    printf("\n平均长度 = %g\n", 1.0 * sum / m);

}

int main(void)

{

    int n = 15;

    int i;

    HTNode ht[M];

    HCode hcd[N];

    char *str[] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};

    int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};

    for(i = 0; i < n; i++)

    {

        strcpy(ht[i].data, str[i]);

        ht[i].weight = fnum[i];

    }

    create_huffman_tree(ht, n); // 创建哈夫曼树

    create_huffman_code(ht, hcd, n); // 构造哈夫曼编码

    display_huffman_code(ht, hcd, n); // 输出哈夫曼编码

    return 0;

}

测试结果：

输出哈夫曼编码:

     The:      01

     of:       101

     a:        001

     to:       000

     and:      1110

     in:       1101

     that:     11110

     he:       11001

     is:       11000

     at:       10011

     on:       10010

     for:      10001

     His:      10000

     are:      111111

     be:       111110

平均长度 = 3.56208

用C语言实现哈夫曼树和生成哈夫曼编码，首先生成哈夫曼树，哈夫曼树是从中选取权值最小的两个进行相加，将这两个分别做为生成的左子树和右子树，左子树要比右子树小。然后将相加得到的值从新放入，然后又从中找到最小的两个值，然后用这个两个值一直相加，直到只剩最后一个值，将这个值作为哈夫曼树的根。

生成哈夫曼编码，如果是左子树的话为0，右子树的话为1，从父节点还是往下找。然后这串代码就是哈夫曼编码。
上代码



 #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>


using namespace std;


const int Lsize  = 1000000;

typedef struct{

   int order;//序号
   char character;//字符值
   int weight;//权重
   int parent;
   int lift_Child;
   int right_Child;
   int deep;
   int code[100];//哈夫曼编码
}Nodetree,*HuffmanTree;


typedef struct node{

   char symbol;
   int quantity;
   struct node *next;
}Node;




int getListSize(char *pStr){

    int len=0;
    char *start = pStr;
    while(*start){
        len++;
        start++;
    }
    return len;
}

int getLIstLink(Node *head){

   int a = 0;
   Node *p = head->next;
   while(p){
     a++;
     p = p->next;
   }
   return a;
};

//打印链表
void print(struct node *head){

    struct node *p ;
    printf("开始打印\n");
    p=head->next ;
    if(p == NULL){
        printf("值为空\n");
    }
    while(p!=NULL){
     printf("          %c",p->symbol);
     printf("         %d\n",p->quantity);
     p=p->next;
    }
};



int QueryNOde(Node *head,char ch){

    Node *p;
    p = head->next;
    while(p!=NULL){
        if(p->symbol == ch){
            p->quantity = p->quantity + 1;//字符存在节点加1
            return 1;//这个字符已经存在
        }
        p = p->next;
    }
   return 0;//这个字符不存在
};

//生成权值
Node *createWeight(char *str){

    Node *head , *q ,*p;
    int list_size = getListSize(str);
    q=head=(struct node*)malloc(sizeof(struct node));
     for(int i = 0 ; i < list_size ; i++){
            //printf("当前的值：%c\n",*str);
            if(QueryNOde(head,*str)==1){//如果该数据已经存在，则节点加1
                  //  printf("开始遍历\n");
                // Node *boos = head = (struct node*)malloc(sizeof(struct node));
                   // printf("开始查找\n");
                // while(boos){
                  //  printf("进入查找\n");
                   // printf("当前遍历值为:%c\n",boos->symbol);
                   // if(boos->symbol == *str){
                      //  printf("开始修改值\n");
                       // boos->quantity = boos->quantity + 1;
                       // printf("值相同\n");
                       // break;
                   // }
                   // boos = boos->next;
                 //}
                } else{//生成新的权值
                    p = (struct node*)malloc(sizeof(struct node));
                    p->quantity = 1;
                    p->symbol = *str;
                    p->next = NULL;
                    q->next = p;
                    q = p;
                    //printf("值不同\n");
                }
                 str++;
            }
            return head;
};


void createTree(HuffmanTree &root,int n,Node *head){

    if(n<=0){
        return;
    }
    Node *q;
    q = head->next;
    int length = 2*n - 1;
    printf("n is %d\n",n);
    int HFCode[100];//哈夫曼编码数组
    root = new Nodetree[length+1];
    //初始化哈夫曼树
    for(int i = 1;i<=length;i++){
        root[i].order = i;
        root[i].character = 0;
        root[i].parent = 0;
        root[i].lift_Child = 0;
        root[i].right_Child = 0;
    }
    //给哈夫曼树赋值
    for(int i = 1;i<=n;i++){
        root[i].character = q->symbol;
        root[i].weight = q->quantity;
        q = q->next;
    }


    //开始建立哈夫曼树

      for(int i = n+1; i <=length; i++){  //进行 n-1 次循环建立哈夫曼树
        //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
        int k1 = -1 , k2;
        for(int j = 0; j < i; j++){
            if ( root[j].parent == 0  && k1 == -1 && root[j].weight > 0){
                k1 = j;
                continue;
            }
            if (root[j].parent == 0 && root[j].weight > 0){
                k2 = j;
                break;
            }
        }
        //将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
        for (int j = k2; j < i; j++){
            if(root[j].parent == 0 ){
                if(root[j].weight < root[k1].weight){
                    k2 = k1;
                    k1 = j;
                }else if(root[j].weight < root[k2].weight){
                    k2 = j;
                }
            }
        }
        //开始生成新的哈夫曼树节点
        root[k1].parent = i;
        root[k2].parent = i;
       // printf(" i is:%d\n",i);
       // printf("k1 is :%d\n",k1);
       // printf("k2 is :%d\n",k2);
       // printf(" k1 weight is:%d\n",root[k1].weight);
       // printf(" k2 weight is:%d\n",root[k2].weight);
        root[i].order = i;
        root[i].lift_Child = k1;
        root[i].right_Child = k2;
        root[i].weight = root[k1].weight + root[k2].weight;
      }
          int start;
         // HFCode[n-1]='\0';
         //生成哈夫曼编码
      for(int i = 1;i<=n;i++){
          start = 0;
          int deep = 0;//节点的深度
          int c = i;
          int f = root[i].parent;
          while(f!=0){
            //printf("tart is:%d\n",start);
            if(root[f].lift_Child == c){
                root[i].code[start] = 0;//如果为左子树就为0
            }else{
               root[i].code[start] = 1;//右子树就为1
            }
            deep++;
            start++;
            c = f;
            f = root[f].parent;
          }
          root[i].deep = deep;
         // printf("code is:%d\n",root[i].code[start]);
      }

};



//void CreatHFCode(Nodetree *root,)
//打印哈夫曼树的表态结构
void printTree(Nodetree *root,int n){

   int length = 2*n -1;
   for(int i = 1 ;i<=length;i++){
    printf("order is %d   character is %c"   "  parent is %d  LiftC is %d  rightC is %d   weight is %d  deep is %d   ",root[i].order, root[i].character, root[i].parent,root[i].lift_Child,root[i].right_Child, root[i].weight,root[i].deep);
       int deep = root[i].deep;
         printf("HFCode is  :");
        for(int j=deep-1;j>=0;j--){
            printf("%d",root[i].code[j]);
        }
        printf("\n");
   }

};

 void QueryCOde(Nodetree *root,int n){

     int query_list[100];//哈夫曼编码整数数组
     int flag ;//哈夫曼编码匹配判断标志
     int c;
     int code_Size;
     char query_char[100];//用来接收哈夫曼编码
     scanf("%s",&query_char);
     //printf("%s\n",query_char);
     code_Size = getListSize(query_char);//输入的哈夫曼编码长度

     //将输入的哈夫曼编码有字符数组转换为整数数组
     for(int i = 0;i<code_Size;i++){
        c = query_char[i]-'0';
        query_list[i] = c;
       // printf("n is:%d\n",c);
     }

   // for(int i=0;i<code_Size;i++){
       //  printf("%d ",query_list[i]);
    // }

     for(int i=1;i<=n;i++){
        int deep = root[i].deep;
        int j ;
        //若哈夫曼的深度和输入的哈夫曼编码长度相同则开始查找
        if(deep==code_Size){
            //printf("deep is:%d code_size is:%d\n",deep,code_Size);
             j=0;
             int code = code_Size-1;
            deep--;
            //开始匹配值
            flag = i;
            while(deep>=0){
           // printf("开始匹配deep %d\n",deep);
            if(root[i].code[j]!=query_list[code]){
               //printf("值不相同\n");
               flag = -1;
               break;
            }
            j++;
            code--;
            //printf("%d deep is %d\n",i,deep);
            deep--;
        }
        }
        //判断是否找到对应的权重的值
       // printf("deep is:%d\n",deep);
        if(deep<0){
            flag = i;
            i = n+1;
        }

     }
    // printf("flag is:%d\n",flag);
     if(flag>0){
        printf("翻译结果值:%c\n",root[flag].character);
     }
     else{
        printf("没有与编码匹配的数据值\n");
     }

 };



int main()
{
    int Link_size ;
    struct node *head;
    Nodetree *root;
    char input_list[Lsize];



     printf("........................功能列表...................\n");
     printf("..............         输入报文  ................\n");
     printf("..............         打印频度  ................\n");
     printf("..............         建立哈夫曼树  ................\n");
     printf("..............         翻译报文  ................\n");
     //printf("..............         5.退出  ................\n");





    printf("..............输入想要赋值的字符串\n");
    scanf("%s",&input_list);
    gets(input_list);
    printf("%s\n",input_list);
    head = createWeight(input_list);
    printf("..............出现频度为\n");
    print(head);
    Link_size = getLIstLink(head);
    printf("..............链表长度为：%d\n",Link_size);
    createTree(root,Link_size,head);
    printTree(root,Link_size);

    int flag = 1;
    while(flag==1){
        printf("..............输入你想要查找的代码\n");
        QueryCOde(root,Link_size);
        printf("..............想继续查找输入1，不想输入0\n");
        scanf("%d",&flag);
    }

}

代码里面有备注，不清楚的可以留言，有错误的欢迎指出。