哈夫曼树的创建，对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载（代码详细注释，便于理解）：
对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载
（课设题目）输入节点信息与权重，创建哈夫曼树，将编码信息存储至文件中，译码时从文件中再读取编码信息，对输入的二进制码串进行译码，C语言代码实现下载：
创建哈夫曼树进行编码到文件并从文件读编码进行译码下载
（课设题目）输入字符串从而计算字符串中每个字符出现的次数作为权重,依据节点信息和权重创建哈弗曼树，进行哈夫曼编码，再对二进制码串进行译码下载：
 输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载devc++编译器版本
 输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载vs编译器版本
（课设题目）输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码C语言实现下载：
输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码
图例
1.手动输入节点信息以及节点所对应的权值，创建哈弗曼树进行编码与译码





2.输入一个字符串，计算字符串中每种字符出现的次数作为权重，创建哈弗曼树，并哈弗曼编码，再对二进制码串进行译码。


以上图例解释：

如果需要将文件编码或译码，则应该加入文件操作，将文件的字符读入。其权重应该为在整个文件中该字符所出现的次数。

**
哈夫曼树（编码及译码）
**

初学数据结构哈夫曼树（小菜鸟），借用了一些经典教材案例，编译软件为vs2013，有问题能指点，当然不喜勿喷哦，谢谢大家。

此程序是利用哈夫曼树实现对文本文件的加密与解密，程序所能达到的内容：使用从文件中读取显示原文本文件、使用哈夫曼树编码对文本文件进行加密、使用哈夫曼表显示字符编码、显示加密文件、使用哈夫曼树译码文本文件解密、显示解密文件、这些程序执行完以后，退出系统。主要包含以下内容：

1.输入文件所存在的位置；

2.进入主菜单界面，显示所有可操作的选项；

3.显示jiemi.txt文件的内容；

4.对文件进行加密，将其与字符转换为二进制编码；

5.对文件进行解密，将二进制编码写入；

6.从文件中读取二进制编码转换为字符，再写入文件；

7.退出系统。

原文件内容：
构建哈夫曼树
从文件中读入字符个数，判定权值最大值，因为了方便给构建哈夫曼树，每个节点的权值相差为1，也就是{1 2 3 4 5 ……n}第一步先取两个最小权值作为左右子树构造一个新树，取1，2构成新树，其结点为1+2=3 虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，再根据第二步，取最小的两个权值构成新树，再不断重复步骤建立哈夫曼树。
void Great(hufmantree &ht, int n)//n为从文件中读入字符的个数
{
	int m, S1, i, S2;
	m = 2 * n - 1;
	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;
}

实现哈夫曼编码
void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
{
	char *cd;
	int strat;
	hc = new char*[n + 1];
	cd = new char[n];
	cd[n - 1] = '\0';//最后一个给‘\0’
	int c, i, f;
	for (i = 1; i <= n; ++i)
	{
		strat = n - 1;//确定最后一个
		c = i;
		f = ht[i].parent;//f—>第i个的节点的双亲
		while (f != 0)
		{
			--strat;//cd倒数第二个空
			if (ht[f].lchild == c)//看看左边有没有孩子
				cd[strat] = '0';
			else cd[strat] = '1';//右边有没有孩子
			c = f; f = ht[f].parent;//回到双亲，f->i的双亲


		}
		hc[i] = new char[n - strat];
		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
	}

//	delete cd;
}

实现哈夫曼译码
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
{
	cout << endl;
	int d, i = 1, j;
	char *cd;
	d = n * 2 - 1;
	cd = new char[n];
	char c;
	for (i = 1; i <= n; i++)
	{
		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);//从hc里把编码调过来
	for (j = 0; j <strlen(cd); j++)
		{
			c = cd[j];
			if (c == '0')
			{
				d = ht[d].lchild;/如果是0往走孩子走

			}
			if (c == '1')
			{

				d = ht[d].rchild;//如果是1往右孩子走
			}
		}
	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
		d = n * 2 - 1;
	}
	delete cd;
	//往文件里写入编译好的字符
	char bf[100];
for (i = 0; i < n;i++)
	bf[i] = '\0';
	FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	if (ht[i].zifu != '\0')
	{
		bf[i - 1] = ht[i].zifu;
		fprintf_s(fp,"%c", bf[i-1]);
		}
	
	fclose(fp);
}

**
完整代码
**
#include <iostream>
#include <string>
using namespace std;
typedef char elemtype;
typedef int status;
typedef char **huffmancode;
typedef struct
{
	char zifu;
	status weight;
	status parent, lchild, rchild;
}hufman, *hufmantree;
void Great(hufmantree &ht, int n);
status  chushihua(hufmantree &ht, char a[100],int n);
status select(hufmantree ht, int m, int &S1, int &S2);
void HuffmanCode(hufmantree ht, int n, huffmancode &hc);
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100]);

void Zifubianma(huffmancode hc, int n, char a[]);
status wenben(char a[]);
void jiemi(hufmantree ht,  int n);
void Menu();
status duxu(char a[],char b[100]);
void xianshi(huffmancode hc, int n, char b[100]);
	int main()
{
		hufmantree ht;
		huffmancode hc;
		char a[100];
		char b[100];
		int  n;
	    n=duxu(a,b);
	    chushihua(ht, a,n);
		Great(ht, n);
		while (1)
		{
			Menu();
			printf("输入要做的操作：（1-7）：  \n");
			int x;
			cin >> x;
			switch (x)
			{
			case 1:wenben(a); break;
			case 2: HuffmanCode(ht, n, hc); system("pause"); break;
			case 3:Zifubianma(hc, n,a); system("pause"); break;
			case 4:xianshi(hc,n,b);system("pause");break; 
			case 5: jiemi(ht,  n); system("pause"); break;
			case 6:HuffmanCoding(ht, n, hc,b); system("pause"); break;
			case 7:
			case 0:exit(0);

			}
			system("cls");
		}

		return 0;
	}
	

void Menu()
{
	printf_s("\n\t\t         ---------------------超级文件加密系统-------------------\n");
	printf_s("\n\t\t\t ψ卍ψ                   0.退出                    ψ卍ψ\n");
	printf_s("\n\t\t\t ψ卍ψ                   1.显示原文本文件          ψ卍ψ\n");
	printf_s(" \n\t\t\t ψ卍ψ                   2.文本文件加密            ψ卍ψ    \n");
	printf_s(" \n\t\t\t ψ卍ψ                   3.显示字符编码            ψ卍ψ\n");
	printf_s(" \n\t\t\t ψ卍ψ                   4.显示加密文件            ψ卍ψ \n");
	printf_s("\n\t\t\t ψ卍ψ                   5.文本文件解密            ψ卍ψ \n ");
	printf_s(" \n\t\t\t ψ卍ψ                   6.显示解密文件            ψ卍ψ \n");
	printf_s(" \n\t\t\t ψ卍ψ                   7.退出系统                ψ卍ψ \n");
	printf_s("\n\t\t         --------------------------------------------------------\n");
}
status wenben(char a[])
{
	int i;
	for (i = 0; i <= strlen(a) - 1; i++)
cout << a[i];
	system("pause");
	return 0;

}
status duxu(char a[],char b[100])
{
	
	cout << "输入文件所在位置"<<endl;
	gets(b);
	FILE *fp = fopen(b, "r");
	int i=100;
fgets(a,i, fp);

	fclose(fp);
	i = 0; 
	while (a[i] !='\0')
	{
		i++;
	}
	
	return i;
}
status  chushihua(hufmantree &ht,char a[100],int n)
{
	int  i, m;
	//cin >> n;/*输入结点1--n之间的节点*/
	m = 2 * n - 1;/*m用于开辟两倍的ht的空间*/
	ht = new hufman[m + 1];/*同上*/
	for (i = 1; i <= m; i++)
	{
		ht[i].parent = 0; ht[i].lchild = 0; ht[i].rchild = 0;
		ht[i].zifu = '0';
	}

	for (i = 1; i <= n; i++)
	{
			
		 ht[i].weight=i;/*输入前几个节点的权值课本p138*/	
		ht[i].zifu = a[i-1];
	}

	return n;
}
void Great(hufmantree &ht, int n)
{
	int m, S1, i, S2;
	m = 2 * n - 1;
	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;

	}
	

}status select(hufmantree ht, int m, int &S1, int &S2)
{
	int j;
	for (j = 1; j <= m; j++)
	{
		if (ht[j].parent == 0)
		{
			S1 = j;
			break;
		}
	}
	for (j = 1; j <= m; j++)
	{
		if (ht[j].parent == 0 && j != S1)
		{
			S2 = j;
			break;
		}
	}
	for (j = 1; j <= m; j++)
	{



		if (ht[j].parent == 0 && ht[j].weight < ht[S1].weight)
		{
			S1 = j;
	
		}

	}
	for (j = 1; j <= m; j++)
	{

		if (ht[j].parent == 0 && j != S1&&ht[j].weight < ht[S2].weight)//双亲为0j不等于上
		{
			S2 = j;
			}


	}
	return 0;
}


void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
{
	char *cd;
	int strat;
	hc = new char*[n + 1];
	cd = new char[n];
	cd[n - 1] = '\0';//最后一个给o
	int c, i, f;
	for (i = 1; i <= n; ++i)
	{
		strat = n - 1;//确定最后一个
		c = i;
		f = ht[i].parent;//f—>第i个的节点的双亲
		while (f != 0)
		{
			--strat;//cd倒数第二个空
			if (ht[f].lchild == c)//看看左边有没有孩子
				cd[strat] = '0';
			else cd[strat] = '1';//右边有没有孩子
			c = f; f = ht[f].parent;//回到双亲，f->i的双亲


		}
		hc[i] = new char[n - strat];
		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
	}
	cout << "文本文件加密成功！";
//	delete cd;
}
void jiemi(hufmantree ht ,int n){
	printf_s("   显示字符编码(哈夫曼表)\n");cout << "位置 右子树 左子树 双亲 对应字符"<<endl;
	int i; for (i = 1; i <= 2 * n - 1; i++)
	{
		
		printf_s("%2d", i);
		printf_s("%6d%6d%6d%6c\n", ht[i].rchild, ht[i].lchild, ht[i].parent, ht[i].zifu);
	}
	
	cout << "解密成功!";
}
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
{
	cout << endl;
	int d, i = 1, j;
	char *cd;
	d = n * 2 - 1;
	cd = new char[n];
	char c;
	for (i = 1; i <= n; i++)
	{
		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);

	for (j = 0; j <strlen(cd); j++)
		{
			c = cd[j];
			if (c == '0')
			{
				d = ht[d].lchild;

			}
			if (c == '1')
			{

				d = ht[d].rchild;
			}
		}
	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
		d = n * 2 - 1;
	}
	delete cd;
	char bf[100];

	for (i = 0; i < n;i++)
	bf[i] = '\0';
	FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	if (ht[i].zifu != '\0')
	{
		bf[i - 1] = ht[i].zifu;
		fprintf_s(fp,"%c", bf[i-1]);
		}
	
	fclose(fp);
}
void Zifubianma(huffmancode hc, int n, char a[])
{
	printf_s("   显示字符编码\n");
	int i; for (i = 1; i <= n; i++)
	{
		cout << a[i - 1] << "  " << hc[i] << endl;
	}
}
void xianshi(huffmancode hc, int n,char b[100])
{
	int i;

	printf_s("\n         4. 显示加密文件\n");
FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	{
		cout <<hc[i];	fputs(hc[i], fp);	
	}
fclose(fp);
}

源于一次实验课，要求实现哈夫曼树、哈夫曼编码与译码；我就直接贴实验要求和代码实现了。

注：因为当时时间有限，故其实该代码还有优化空间，且输出文件是0/1字符串文本（UTF-8）并不是ASCII码编码文件，计算压缩率除以8即可。
实验项目：哈夫曼编码与译码方法
哈夫曼编码是一种以哈夫曼树（最优二叉树，带权路径长度最小的二叉

树）为基础的基于统计学的变长编码方式。其基本思想是：将使用次数多的代

码转换成长度较短的编码，而使用次数少的采用较长的编码，并且保持编码的

唯一可解性。在计算机信息处理中，经常应用于数据压缩。是一种一致性编码

法（又称"熵编码法"），用于数据的无损耗压缩。本实验要求利用贪心算法实

现一个完整的哈夫曼编码与译码系统。
实验内容和实验要求：

从文件中读入任意一篇英文文本文件，分别统计英文文本文件中各字符（包

括标点符号和空格）的使用频率；
根据已统计的字符使用频率构造哈夫曼编码树，并给出每个字符的哈夫曼编

码（字符集的哈夫曼编码表）；
将文本文件利用哈夫曼树进行编码，存储成压缩文件（哈夫曼编码文件）；
计算哈夫曼编码文件的压缩率；
将哈夫曼编码文件译码为文本文件，并与原文件进行比较。

C代码：

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

#define n 65

//哈夫曼树节点存储结构
typedef struct{
    char data;
    int weight;
    int lchild;
    int rchild;
    int parent;
}Htnode;

typedef Htnode HuffmanT[129];

//哈夫曼编码表的存储结构
typedef struct{
    char ch;        //储存被编码的字符
    char bits[n+1]; //字符编码位串
}CodeNode;

typedef CodeNode HuffmanCode[n];


//0-9为数字；10-35为小写字母；36-61为大写字母；62-64为特殊字符
void InitHT(HuffmanT T)   //初始化
{
    char sz = '0';
    char xzm = 'a';
    char dzm = 'A';
    char kong = ' ';
    char dh = ',';
    char jh = '.';

    for(int i=0; i<n; i++)        
    {
        T[i].lchild = T[i].rchild = T[i].parent = -1;
        T[i].weight = 0;
        if(i>=0&&i<=9)
        {
            T[i].data = sz;
            sz++;
        }
        if(i>=10&&i<=35)
        {
            T[i].data = xzm;
            xzm++;
        }
        if(i>=36&&i<=61)
        {
            T[i].data = dzm;
            dzm++;
        }
        if(i>=62&&i<=64)
        {
            T[62].data = kong;
            T[63].data  = dh;
            T[64].data= jh;
        }
    }

    for(int j = n; j<2*n-1; j++)
    {
        T[j].weight = 0;
        T[j].lchild = T[j].rchild = T[j].parent = -1;
    }

    printf("initHT over\n");
}

void InputW(HuffmanT T)         //读入文件中字符并输入权值
{
    FILE *fp;
    char ch;
    char Filename[20];

    printf ("input the filename:");
    scanf("%s",Filename);
   
    if((fp=fopen(Filename,"r"))==NULL)    printf("faild\n");
    ch = fgetc(fp);

    while(ch != EOF)
    {
        for(int i = 0; i<n; i++)
        {
            if(T[i].data == ch) T[i].weight++;
        }
        ch = fgetc(fp);
    }

    for(int i =0; i<n; i++)
    {
        printf("%c weight is:",T[i].data);
        printf("%d\n",T[i].weight);
        // printf("%d,%d,%d\n",T[i].parent,T[i].lchild,T[i].rchild);
    }
    
    fclose(fp);
   
    printf("inputW over\n");
}

void SelectMin(HuffmanT T, int length, int *p1, int *p2)    //选择权值最小的两个元素，返回下标
{
    int min1,min2;              //min1标记最小，min2标记次小
    int i=0;
    int k,j=0;
    for(j; j<length; j++)
    {
        if(T[j].parent == -1)
        {
            min1=j;
            break;
        }
    }

    for(k=min1+1;k<length;k++)
    {
        if(T[k].parent == -1)
        {
            min2 = k;
            break;
        }
    }
    // for(i = 0;i<length;i++)
    while(i<length)
    {
        if(T[i].parent == -1)
        {
            
            if(T[i].weight<T[min1].weight)
            {
                min2 = min1;
                min1 = i;
            }
            else if((i!=min1)&&(T[i].weight<T[min2].weight))
            {
                min2 = i;
            }
        }

        i++;
    }

    // printf("%d,%d:%d,%d ",min1,min2,T[min1].weight,T[min2].weight);
    *p1 = min1;
    *p2 = min2;

    // printf("selectmin\n");
}

void CreartHT(HuffmanT T)       //构造哈夫曼编码树
{
    int i,p1,p2;
    int wei1,wei2;
    InitHT(T);      //初始化
    InputW(T);      //输入权值
    for(i=n; i<129; i++)
    {
        SelectMin(T,i,&p1,&p2);
        wei1 = T[p1].weight;
        wei2 = T[p2].weight;
        T[p1].parent = i;
        T[p2].parent = i;
        T[i].lchild = p1;
        T[i].rchild = p2;
        T[i].weight = wei1 + wei2;
    }

    printf("creatHT over\n");
}

void CharSetHuffmEncoding(HuffmanT T, HuffmanCode H)    //根据哈夫曼树求哈夫曼编码表H
{
    int c,p,i;          //c和p分别指示T中孩子和双亲位置
    char cd[n+1];       //临时存放编码
    int start;          //指示编码在cd中的位置
    cd[n]='\0';         //编码结束符
    for(i=0; i<n; i++)
    {
        H[i].ch = T[i].data;
        start = n;
        c=i;
        while((p=T[c].parent)>=0)   //回溯到T[c]是树根位置
        {
            cd[--start] = (T[p].lchild==c) ? '0':'1';   //T[c]是T[p]的左孩子，生成代码0否则生成1
            c=p;
        }
        strcpy(H[i].bits,&cd[start]);
    }
    printf("creatHcode over\n");
}

void PHUM(char *file,char *s);

char s[30000]={3};
void PrintHUffmancode(HuffmanCode H)        //将文件中字符的哈夫曼编码打印出来并将其写入指定txt文件
{
    
    FILE *fp;
    char ch;
    char Filename[80];
    char file[80];

    printf ("output the Huffmancode of which file:");
    scanf("%s",Filename);
    if((fp=fopen(Filename,"r"))==NULL)    printf("failda\n");
    ch = fgetc(fp);
    int L =0;
    printf("1");
    while(ch != EOF)
    {

        for(int i = 0; i<n; i++)
        {
            if(H[i].ch == ch) 
            {
                printf("%s",H[i].bits);
                sprintf(s+L,"%s",H[i].bits);
                L=strlen(s);
            }
        }

        ch = fgetc(fp);
    }
    printf("\n");

    for(int k =0;k<n;k++)
    {
        printf("%c-%s\n",H[k].ch, H[k].bits);
    }

    // printf("3\n");
    fclose(fp);
    printf("stand by\n");

    PHUM(file,s);
    
}

void PHUM(char *file,char *s)
{
    FILE *fp;
    int i=0;
    printf ("save your Huffmancode to the file:");
    scanf("%s",file);
    if((fp=fopen(file,"w"))==NULL)    printf("faild\n");

    while(s[i]!='\0')
    {
        // fwrite(s,1,strlen(s),fp);
        // fprintf(fp,'%c',s[i]);
        fprintf(fp,"%c",s[i]);
        i++;
    }
    
    fclose(fp);
    printf("write over\n");

    
}

void Printftxt(HuffmanT T,char a[])  //左0右1
{
    int root,c;
    int i = 0;
    FILE *fp;
    char ch;
    char Filename[30];

    printf ("print words acroding to Huffmancode:");
    scanf("%s",Filename);
    if((fp=fopen(Filename,"r"))==NULL)    printf("faild\n");

    // printf("1\n");
    for(int j =0; j<129; j++)     //找到根节点
    {
        if(T[j].parent==-1)
        {
            root = j;
            break;
        }
    }
    
    ch=fgetc(fp);
    while(ch!=EOF)
    {
        c=root;

        while((T[c].lchild != -1) || (T[c].rchild != -1))
        {
            if(ch=='0')
            {
                c=T[c].lchild;
                ch = fgetc(fp);
            }
            else if(ch=='1')
            {
                c=T[c].rchild;
                ch = fgetc(fp);
            }
            // printf("2");
        }

        printf("%c",T[c].data);
       
        // ch = fgetc(fp);

    }

    fclose(fp);
}

int main()
{
    HuffmanT T;
    HuffmanCode H;

    CreartHT(T);     //读入文件构造一个哈夫曼树初始化并输入权值 输出各字符权值
    CharSetHuffmEncoding(T,H);   //根据哈夫曼树构造哈夫曼表，并输出各字符的编码
    PrintHUffmancode(H);        //输出某个文件中文本的哈夫曼编码，并把它保存在指定文件中
    
    Printftxt(T,s);   //根据哈夫曼编码打印文本文件字符

}

哈夫曼树编码代码实现
首先用的是优先队列和STL pair实现的树的构建
对于结构体

struct TreeNode {

int power;

int ascii;

TreeNode* Left;

TreeNode* Right;

TreeNode* Parent;

TreeNode() {

Left = NULL;

Right = NULL;

Parent = NULL;

power = -1;

ascii = 0;

}
};

建立parent指针指向父结点可以更方便的实现编码的回溯。

1.pair中存储结点和ascii值，存在优先队列中，

2.每次提出队列中power值最小的两个元素，将其与新建的Temp父结点构成一棵子树；父结点的power值等于两子树power之和；

3.将构成的新的父结点重新放入优先队列，如此循环

4.当优先队列中只剩下一个结点时，说明哈夫曼树已经构造完成
（利用结构体cmp可以设置优先队列的优先级

关键代码：return a.first->power > b.first->power; ）

（结点的第二个数值为ascii的原因是为了更好的将含有字符的结点用数组保存下来，新生成的结点second值都是-1，所以当second的值不为-1，

可以有代码 HufmNodeAdress[que.top().second - 65] = TempNode;)
编码：

对于哈夫曼树的编码，由于之前建树时已经顺便将每个含字符的结点的位置存起来，可以从根结点向上回溯，我使用的方法是用栈；

1.将追溯到根节点前的结点都用栈保存起来

2.将栈的结点出栈，与当前栈顶元素进行进行比较

若为左子树，输出 0，右子树为1

由此可以得出所选字符的哈夫曼编码；

译码：

编码之后直接可以进行译码，0往左，1往右

每完成一个字符的译码记得将指针指回头结点。
ps:代码如下
#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
struct TreeNode {
	int power;
	int ascii;
	TreeNode* Left;
	TreeNode* Right;
	TreeNode* Parent;
	TreeNode() {
		Left = NULL;
		Right = NULL;
		Parent = NULL;
		power = -1;
		ascii = 0;
	}
	
};
typedef pair<TreeNode*, int> P;   //<节点，ascii>

struct cmp {
	bool operator()(const P a, const P b)
	{
		return a.first->power > b.first->power;       //频率小的优先 
	}
};
priority_queue<P, vector<P>, cmp> que;    //优先队列
TreeNode* HufmNodeAdress[26] = {0};
void MakeHufmTree(TreeNode* Node) {
	if (que.size() <= 1)
		return;
	while (que.size()!=1)
	{
		TreeNode* TempLeft = new TreeNode;
		TreeNode* TempRight = new TreeNode;
		TreeNode* TempParent = new TreeNode;
		//TempLeft->power = que.top().first->power;
		//TempLeft->Left = que.top().first->Left;
		//TempLeft->Right = que.top().first->Right;
		TempLeft = que.top().first;
		if (que.top().second != -1)
			HufmNodeAdress[que.top().second - 65] = TempLeft;
		que.pop();
		//TempRight->Left = que.top().first->Left;
		//TempRight->Right = que.top().first->Right;
		//TempRight->power = que.top().first->power;
		TempRight = que.top().first;
		if (que.top().second != -1)
			HufmNodeAdress[que.top().second - 65] = TempRight;
		que.pop();
		TempParent->Left = TempLeft;
		TempParent->Right = TempRight;
		TempParent->power = TempLeft->power + TempRight->power;
		TempLeft->Parent = TempParent;
		TempRight->Parent = TempParent;
		P temp(TempParent, -1);
		que.push(temp);
	}
	Node->Left = que.top().first->Left;
	Node->Right = que.top().first->Right;
	Node->power = que.top().first->power;
	
}
void GetCode(TreeNode* pos)
{
	stack<TreeNode*> stk;
	TreeNode* p;
	while (pos->Parent)
	{
		stk.push(pos);
		pos = pos->Parent;
	}
	stk.push(pos);
	while (stk.size()!=1)
	{
		p = stk.top();
		stk.pop();
		if (p->Left == stk.top())
			cout << 0;
		else if (p->Right == stk.top())
			cout << 1;
	}
	
	
}
void ShowCode()
{
	for (int i = 0;i < 26;i++)
	{
		if (NULL != HufmNodeAdress[i]) {
			printf("%c的编码为：", i + 65);
			GetCode(HufmNodeAdress[i]);
			cout << endl;
		}
			
	}
}
void Decoding(char ch[])
{
	int cnt = 0;
	while (1)
	{
		if (ch[cnt] == '\0')
			break;
		GetCode(HufmNodeAdress[ch[cnt++] - 65]);

	}
	cout << endl;
}
void check(TreeNode* Node)
{
	if (Node->Parent)
		cout << Node->power << "has the parent" << Node->Parent->power<<endl;
	cout << Node->power << " ";
	if (Node->Left)
		check(Node->Left);
	if (Node->Right)
		check(Node->Right);
}
void Coding(TreeNode* pos,char ch[])
{
	int i = 0;
	TreeNode* p = new TreeNode;
	p = pos;
	while (ch[i] != 0)
	{
		if (ch[i] == '0')
			p = p->Left;
		else if (ch[i] == '1')
			p = p->Right;
		if (p->ascii != 0)
		{
			printf("%c", p->ascii);
			p = pos;
		}
		i++;
	}
}
int main()
{
	char Ch[1000];
	cin >> Ch;
	int Fre[26] = { 0 };
	for (int i = 0;;i++)
	{
		if (Ch[i] == '\0')
			break;
		Fre[Ch[i] - 65]++;
	}
	for (int i = 0;i < 26;i++)
	{
		if (Fre[i] != 0)
		{
			TreeNode* NewNode = new TreeNode;
			NewNode->power = Fre[i];
			NewNode->ascii = i + 65;
			P temp(NewNode, i + 65);//结点，ascii
			que.push(temp);
		}
	}
	TreeNode* Node = new TreeNode;
	MakeHufmTree(Node);
	ShowCode();
	Decoding(Ch);
	//check(Node);
	char num[1000];
	cin >> num;
	Coding(Node, num);
	return 0;

}