数据结构_树_赫夫曼树及赫夫曼编码_C++实现

传说中的最优二叉树——赫夫曼(Huffman)树

本例采用如下存储结构：

实例：

下面这个是严蔚敏《数据结构》C语言版上的赫夫曼编码存储结构

我换了一种方式，开了一个栈然后反复用，具体见代码：

"head.h"

#include<iostream>
#include<stack>
using namespace std;

class NODE
{
public:
	NODE();
	int weight,parent,lchild,rchild;
};

NODE::NODE()
{
	weight=parent=lchild=rchild=0;
}

class HUFFMAN
{
public:
	HUFFMAN();
	void GetHuffmanCode();//获得赫夫曼编码主调函数
private:
	void GetHuffmanNode();//获得节点
	void HuffmanCoding();//编码
	void PrintHuffmanCode();//输出编码
	void Select(int &,int &);//从森林中选择两颗权值较小的树
	int len,cur;//len表示表长度cur表示当前指示的节点
	NODE * HT;//HT指向表头结点
};

HUFFMAN::HUFFMAN()
{
	len=cur=0;
	HT=NULL;
}

void HUFFMAN::GetHuffmanCode()//获得赫夫曼编码主调函数
{
	GetHuffmanNode();
	HuffmanCoding();
	PrintHuffmanCode();
}

void HUFFMAN::GetHuffmanNode()//获得节点
{
	cout<<"GetHuffmanNode Called !"<<endl<<endl;
	cout<<"Please Enter The Weight Of Each Node ."<<endl<<endl;
	NODE node[100];
	int i=0,t;
	while(cin>>t)
	{
		node[i++].weight=t;
	}
	cin.clear();
	len=i;
	HT=new NODE[2*i];
	for(i=1;i<=len;i++)
		*(HT+i)=node[i-1];
	cur=len+1;
}

void HUFFMAN::HuffmanCoding()//编码
{
	cout<<"HuffmanCoding Called !"<<endl<<endl;
	while(cur<2*len)//建树过程
	{
		int a,b;
		Select(a,b);//选择两颗权值较小的子树
		(HT+cur)->weight=(HT+a)->weight+(HT+b)->weight;//连接成新树并更该其权值
		(HT+cur)->lchild=a;
		(HT+cur)->rchild=b;
		cur++;
	}
}

void HUFFMAN::PrintHuffmanCode()//输出编码
{
	cout<<"PrintHuffmanCode Called !"<<endl<<endl;
	cout<<"The Huffman Code Is :"<<endl<<endl;
	stack<int> s;//定义一个栈存放编码
	for(int i=1;i<=len;i++)//从叶子节点向上查找到根节点
	{
		cout<<(HT+i)->weight<<" : ";
		int j=i;
		do
		{
			if((HT+(HT+j)->parent)->lchild==j)//左子树表示为0
				s.push(0);
			else//右子树表示为1
				s.push(1);
			j=(HT+j)->parent;//j指向其父节点
		}while((HT+j)->parent!=0);//未查找到根节点时进行查找
		while(!s.empty())//输出编码
		{
			cout<<s.top()<<" ";
			s.pop();
		}
		cout<<endl;
	}
}

void HUFFMAN::Select(int &a,int &b)//从森林中选择两颗权值较小的树
{
	int min;
	bool first=true;
	for(int i=1;i<cur;i++)//从表中获得min的值并得到a其中有个小技巧不知道您看懂了木有？
	{
		if((HT+i)->parent==0&&(first==true||(HT+i)->weight<min))
		{
			a=i;
			min=(HT+i)->weight;
			if(first==true)
				first=false;
		}
	}
	first=true;
	(HT+a)->parent=cur;//更改a的父节点
	for(int i=1;i<cur;i++)//从表中获得min的值并得到b
	{
		if((HT+i)->parent==0&&(first==true||(HT+i)->weight<min))
		{
			b=i;
			min=(HT+i)->weight;
			if(first==true)
				first=false;
		}
	}
	(HT+b)->parent=cur;//更改b的父节点
	if(a>b)//如有必要调整a、b次序
	{
		int t=a;
		a=b;
		b=t;
	}
}

"main.cpp"

#include<iostream>
#include"head.h"
using namespace std;

int main()
{
	HUFFMAN ht;
	ht.GetHuffmanCode();
	system("pause");
}