【数据结构】哈夫曼树的构建和哈夫曼编码

说明

本篇为笔者学习随记，供学习和复习使用

结构体定义

typedef struct
{
	int weight=0;
	int parent=0,lchild=0,rchild=0;
}HTNode;

此处=0可使结构体在构建时就自动初始化

typedef char** HuffmanCode;

把多重指针换成HuffmanCode 

哈夫曼树的构建

构建

思路：

a)初始化哈夫曼树（结构体数组）：

若有n个有效权值节点则整棵树共有m=2n-1个节点，多申请一个空间是因为第0位置弃用，再根据传入的权重数组初始化各节点的权重。

b)构建：

先利用Select函数找到当前权重最小且未被选择过的两个节点，这两个节点就是当前层的两个兄弟节点，他们的双亲就是当前的i，双亲的孩子自然就是这两个节点，最后双亲的权重等于两孩子的权重之和。

void createHT(HTNode* &HT_root,int weight[],int n)
{
	int m=2*n-1;
	HT_root=new HTNode[m+1];//第0位置弃用
	HT_root[0].weight=1000;//用于select
	for(int i=1; i<=n; i++)
	{
		HT_root[i].weight=weight[i-1];
	}

	int index1=0,index2=0;
	for(int i=n+1; i<=m; i++)
	{
		Select(HT_root,i-1,index1,index2);
		HT_root[index1].parent=i;
		HT_root[index2].parent=i;
		HT_root[i].lchild=index1;
		HT_root[i].rchild=index2;
		HT_root[i].weight=HT_root[index1].weight+HT_root[index2].weight;
	}

}

Select函数 

思路：该函数的功能是找到两个权重最小且之前未被选择的节点，初始化index1和index2为0（之前已经把第0个节点的权重设为一个很大的数），之后依次进行比较，若遍历到的节点未被选择（即parent=0）且权重小于现有的两个最小权重，则替换。

void Select(HTNode* HT_root,int n,int &index1,int &index2)//传引用可改变实参的值
{
	//在下标【1，n】中找两个双亲域为0（未被选择）且最小的两个权重节点(index1权重<index2权重)
	index1=0;
	index2=0;//index1对应权重<index2
	for(int i=1; i<=n; i++)
	{
		if(HT_root[i].parent==0&&HT_root[i].weight<HT_root[index2].weight&&HT_root[i].weight>=HT_root[index1].weight)
		{
			index2=i;
		}
		else if(HT_root[i].parent==0&&HT_root[i].weight<HT_root[index2].weight&&HT_root[i].weight<HT_root[index1].weight)
		{
			index2=index1;
			index1=i;
		}
		else
		{
			continue;
		}
	}
}

哈夫曼编码表构建

思路：编码表的本质是一个指针数组，存储的每一个指针都指向一个字符串，这个字符串是当前字符所对应的二进制码。初始化字符数组cd用来临时存储二进制码，便于后续直接复制。遍历下标1-n求每个节点的二进制码：从哈夫曼树的叶子节点向上走，如果当前节点是双亲的左孩子则在cd中写入0，否则写入1，直到回溯到根节点为止。此时cd中存储的二进制码就是该字符对应的二进制码。

void createHuffmanCode(HTNode* HT,HuffmanCode &HC,int n)//HC指向指针数组中的第一个指针(可当整个指针数组使用)，传引用改变实参
{
	HC=new char*[n+1];//0位置弃用
	char* cd=new char[n];
	cd[n-1]='\0';//结束符，与下面strcpy适配
	for(int i=1; i<=n; i++) //求下标1-n即有权重的实际节点的编码
	{
		int start=n-1;
		int call=i;//当前编码节点
		int parent=HT[i].parent;//当前节点的双亲
		while(parent!=0)
		{
			start--;
			if(HT[parent].lchild==call)
			{
				cd[start]='0';
			}
			else
			{
				cd[start]='1';
			}
			call=parent;
			parent=HT[parent].parent;//回溯继续编码，直到回溯到根为止
		}
		HC[i]=new char[n-start];//多了一个位置用来存'\0'
		strcpy(HC[i],&cd[start]);

	}
	delete cd;//能释放的及时释放，HC需要保留
}

字符串的编码与解码

有了哈夫曼树和哈夫曼编码表就可以对文件进行编码和译码

编码

思路：

依次读入文件中的字符c，在哈夫曼编码表中找到该字符对应的二进制编码，然后将该字符替换为二进制编码或将二进制编码写入新文件。

void encoder(char* txt_file_path,HuffmanCode HC,const char* binary_file_path)//编码
{
	FILE* txt_file=fopen(txt_file_path,"r");
	FILE* binary_file=fopen(binary_file_path,"w");
	if(txt_file==nullptr||binary_file==nullptr)
	{
		perror("文件打开失败");
	}
	else
	{
		char ch;
		char str[30]={0};//保存转换成的二进制字符串
		while ((ch = fgetc(txt_file)) != EOF)
		{
			strcpy(str,HC[ch-'a'+1]);
			fputs(str, binary_file);
		}
	}
	fclose(txt_file);
	fclose(binary_file);
}

解码

思路：

利用哈夫曼树。依次读入文件的二进制码，从哈夫曼树的根节点开始，若读到0则走左孩子，否则走右孩子，然后接着读入二进制码，循环往复，直到走到叶子节点处，这个叶子节点对应的字符就是之前读到的一连串二进制码对应的字符。然后重新从根出发，继续读入二进制码，直到文件结束。

string decoder(const char* binary_file_path,HTNode* HT)//译码
{
	string result="";
	char ch;
	FILE* file=fopen(binary_file_path,"r");
	if(file==nullptr)
	{
		perror("文件打开失败");
	}
	else
	{
		int index=51;//初始化为根节点，指示当前节点
		while((ch = fgetc(file)) != EOF)//文件还没读取结束
		{
			if(ch=='0')
			{
				index=HT[index].lchild;
			}
			else
			{
				index=HT[index].rchild;
			}
			
			if(HT[index].lchild==0&&HT[index].rchild==0)//叶子节点
			{
				ch=index+'a'-1;
				result.push_back(ch);
				index=51;
			}
		}
		
	}
	fclose(file);
	return result;	
}

注：这里要注意哈夫曼树的根节点索引不是1，而是2n-1（n为有效权重的节点数）