传说中的最优二叉树——赫夫曼(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");
}