C++链表：哈夫曼树（附源码）_哈夫曼树c++代码

 在开始之前先给大家介绍一下什么是哈夫曼树

          哈夫曼树就是给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

 

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

 

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

我们现在进入正题，那如何用代码来实现哈夫曼树呢 

首先就是进行哈夫曼编码

void Encoding( HuffmanTree & HT,HuffmanCode & HC,char EnteringData[]  )  //编码
{	
	if( HC[0].ch == NULL )
	{
		char code[MAXCODELEN];
		CreateHuffmanTree( HT,HC );
		HuffmanTree RootNode = HT->next;
		while( RootNode->next != NULL )  //找根结点
		{
			RootNode = RootNode->next;
		}
		PreOrderEncode( RootNode,HC,code,0 );  //先序遍历编码
	}
	else
	{
		MessageBox(NULL,"没有文档录入,请录入文档后编码!","提示",MB_ICONERROR | MB_OK);
		return;
	}
	int ref = MessageBox(NULL,"编码成功,是否要保存哈夫曼编码?","提示",MB_ICONQUESTION | MB_YESNO);
	if( IDYES == ref )
	{
		FILE *fp = fopen("HuffmanCode.txt","wb");
		if( ! fp )
		{
			MessageBox(NULL,"文件打开失败!","提示",MB_ICONERROR | MB_OK);
			system("cls");
			return;
		}
		for( int i = 0; EnteringData[i] != '\0'; ++i )
		{
			int Ascii = EnteringData[i];
			if( Ascii < 0 )   //当出现在不是0～128的Ascii时，不能实现编码，退出循环
				break;
			fputs( HC[Ascii].code,fp );
		}
		fclose( fp );
	}
	else
	{
		system("cls");
		return;
	}
}

然后进行先序遍历编码，用递归实现

void PreOrderEncode( HuffmanTree RootNode,HuffmanCode & HC,char code[],int n ) //先序遍历编码，用递归实现
{
	if( RootNode->lchild == NULL && RootNode->rchild == NULL )
	{
		int Ascii = RootNode->ch;
		HC[Ascii].code = ( char * )malloc( (n+1) * sizeof( char ) );
		if( ! HC[Ascii].code )
			exit( OVERFLOW );
		for( int i = 0; i < n; ++i )
		{
			HC[Ascii].code[i] = code[i];
		}
		HC[Ascii].code[i] = '\0';
		return;
	}
	if( RootNode->lchild )
	{
		code[n] = '0';
		PreOrderEncode( RootNode->lchild,HC,code,n+1 );
	}
	if( RootNode->rchild )
	{
		code[n] = '1';
		PreOrderEncode( RootNode->rchild,HC,code,n+1 );
	}
}

进行链表排序，哈夫曼加码解码

void HuffmanNodeSort( HuffmanTree & HT,int & Len )  //排序函数
{
	int len = 0;
	HuffmanTree Head = HT->next,Prior,Next;
	while( Head != NULL )
	{
		++len;
		Head = Head->next;
	}
	Len = len;
 
	bool exchange = TRUE;
	while( exchange )   //对链表进行排序, 采用优化后的冒泡排序算法
	{
		exchange = FALSE;
		Prior = HT;
		Head = HT->next;
		Next = Head->next;
		for( int i = 0; i < len-1; ++i )
		{
			if( Head->weigth > Next->weigth )
			{
				Prior->next = Next;
				Head->next = Next->next;
				Next->next = Head;
				Prior = Next;
				Next = Head->next;
				exchange = TRUE;
			}
			else
			{
				Prior = Prior->next;
				Head = Head->next;
				Next = Head->next;
			}
		}
		len--;
	}
}
 
void InsertNode( HuffmanTree & SecondFind,HuffmanTree & FirstFind,HuffmanTree &New )
{
	HuffmanTree Prior,Next;
	Prior = SecondFind;
	Next  = SecondFind->next;
	if( SecondFind->next == NULL )  //SecondFind 指向链表结尾的情况，并将新结点插入链表
	{
		SecondFind->next = New;
		return;
	}
	while( New->weigth > Next->weigth && Next->next != NULL )  //SecondFind 没有指向链尾，进行有序插入
	{
		Prior = Prior->next;
		Next  = Next->next;
	}
	if( Next->next == NULL )   //实现链表的插入
	{
		Next->next = New;
	}
	else
	{
		New->next = Next;
		Prior->next = New;
	}
	FirstFind = SecondFind->next;   //First Second 分别指向下两个结点
	SecondFind = FirstFind->next;
}
 
void Decoding( HuffmanTree & HT,HuffmanCode & HC )
{
	int i = 0;
	char EnteringData[MAX_FILE_SIZE];
	HT = ( HuffmanTree )malloc( sizeof( HTNode ) );
	HT->next = NULL;
	HT->weigth = 0;
	HT->lchild = NULL;
	HT->rchild = NULL;
	HT->parent = NULL;
	HT->ch = NULL;
	
	FILE *fp = fopen("HuffmanTree.txt","rb");
	if( ! fp )
	{
		MessageBox(NULL,"文件打开失败!","提示",MB_OK);
		system("cls");
		return;
	}
	else
	{
		for( int i = 0; i < MAX_CHAR_SIZE; ++i )
		{
			fread( &HC[i],sizeof( struct Huffman ),1,fp );
		}
		fclose( fp );
		CreateHuffmanTree( HT,HC );
	}
 
	fp = fopen("HuffmanCode.txt","rb");
	if( ! fp )
	{
		MessageBox(NULL,"文件打开失败!","错误",MB_ICONERROR | MB_OK);
		system("cls");
		return;
	}
	HuffmanTree RootNode = HT->next,Decode;
	while( RootNode->next != NULL )  //找根结点
	{
		RootNode = RootNode->next;
	}
	Decode = RootNode;
 
	gotoxy(0,23);
	while( ! feof( fp ) )  //解码，采用非递归算法
	{
		char ch = fgetc( fp );
		if( ch == '0' && Decode->lchild )
		{
			Decode = Decode->lchild;
		}
		if( ch == '1' && Decode->rchild )
		{
			Decode = Decode->rchild;
		}
		if( Decode->lchild == NULL && Decode->rchild == NULL )
		{
			EnteringData[i] = Decode->ch;
			++i;
			printf("%c",Decode->ch);
			Decode = RootNode;
		}
	}
	EnteringData[i] = '\0';
	fclose( fp );
	printf("\n请按任意键继续...\n");
	getch();
 
	int ref = MessageBox(NULL,"译码成功,是否要保存译码内容?","提示",MB_ICONQUESTION | MB_YESNO);
	if( IDYES == ref )
	{
		fp = fopen("contents.txt","wb");
		if( ! fp )
		{
			MessageBox(NULL,"文件打开失败!","提示",MB_ICONERROR | MB_OK);
			system("cls");
			return;
		}
		i = 0;
		while( EnteringData[i] != '\0' )
		{
			fputc( EnteringData[i],fp );
			++i;
		}
		fclose( fp );
		system("cls");
	}
	else
	{
		system("cls");
		return;
	}
}

这就是哈夫曼树实现的基本过程，其实可以看到代码并不是很难，更重要的是对于逻辑的理解和算法是熟悉

UP在主页上传了一些学习C/C++编程的视频教程，有兴趣或者正在学习的小伙伴一定要去看一看哦！会对你有帮助的~ 

  加群1083227756！！！

分享（源码、项目实战视频、项目笔记，基础入门教程）

想要哈夫曼树源码的同学也可以加群加群1083227756！！！来领取