两种遍历方法实现赫夫曼编码

对之前的代码做了些改进，并增加了一种无栈非递归求赫夫曼编码的方法。加入了更详细的注释。。

#include
#include
#include
#include“data_structure.h“

/*
根据给定的n个权值构造一棵赫夫曼树wet中存放n个权值
*/
HuffmanTree create_HuffmanTree（int *wetint n）
{
	//一棵有n个叶子节点的赫夫曼树共有2n-1个节点
	int total = 2*n-1;
	HuffmanTree HT = （HuffmanTree）malloc（total*sizeof（HTNode））;
	if（!HT）
	{
		printf（“HuffmanTree malloc faild!“）;
		exit（-1）;
	}
	int i;

	//以下初始化序号全部用-1表示，
	//这样在编码函数中进行循环判断parent或lchild或rchild的序号时，
	//不会与HT数组中的任何一个下标混淆而造成误判

	//HT[0]HT[1]...HT[n-1]中存放需要编码的n个叶子节点
	for（i=0;i	{
		HT[i].parent = -1;
		HT[i].lchild = -1;
		HT[i].rchild = -1;
		HT[i].weight = *wet;
		wet++;
	}

	//HT[n]HT[n+1]...HT[2n-2]中存放的是中间构造出的每棵二叉树的根节点
	for（;i	{
		HT[i].parent = -1;
		HT[i].lchild = -1;
		HT[i].rchild = -1;
		HT[i].weight = 0;
	}

	int min1min2; //用来保存每一轮选出的两个weight最小且parent为0的节点
	//每一轮比较后选择出min1和min2构成一课二叉树最后构成一棵赫夫曼树
	for（i=n;i	{
		select_minium（HTimin1min2）;
		HT[min1].parent = i;
		HT[min2].parent = i;
		//这里左孩子和右孩子可以反过来，构成的也是一棵赫夫曼树，只是所得的编码不同
		HT[i].lchild = min1;
		HT[i].rchild = min2;
		HT[i].weight =HT[min1].weight + HT[min2].weight;
	}
	return HT;
}

/*
从HT数组的前k个元素中选出weight最小且parent为-1的两个，分别将其序号保存在min1和min2中
*/
void select_minium（HuffmanTree HTint kint &min1int &min2）
{
	min1 = min（HTk）;
	min2 = min（HTk）;
}

/*
从HT数组的前k个元素中选出weight最小且parent为-1的元素，并将该元素的序号返回
*/
int min（HuffmanTree HTint k）
{
	int i = 0;
	int min;        //用来存放weight最小且parent为-1的元素的序号
	int min_weight; //用来存放weight最小且parent为-1的元素的weight值

	//先将第一个parent为-1的元素的weight值赋给min_weight留作以后比较用。
	//注意，这里不能按照一般的做法，先直接将HT[0].weight赋给min_weight，
	//因为如果HT[0].weight的值比较小，那么在第一次构造二叉树时就会被选走，
	//而后续的每一轮选择最小权值构造二叉树的比较还是先用HT[0].weight的值来进行判断，
	//这样又会再次将其选走，从而产生逻辑上的错误。
	while（HT[i].parent != -1）
		i++;
	min_weight = HT[i].weight;
	min = i;

	//选出weight最小且parent为-1的元素，并将其序号赋给min
	for（;i	{
		if（HT[i].weight		{
			min_weight = HT[i].weight;
			min = i;
		}
	}

    //选出weight最小的元素后，将其parent置1，使得下一次比较时将其排除在外。
	HT[min].parent = 1; 

	return min;
}

/*
从叶子节点到根节点逆向求赫夫曼树HT中n个叶子节点的赫夫曼编码，并保存在HC中
*/
void HuffmanCoding（HuffmanTree HTHuffmanCode &HCint n）
{
	//用来保存指向每个赫夫曼编码串的指针
	HC = （HuffmanCode）malloc（n*sizeof（char *））;
	if（!HC）
	{
		printf（“HuffmanCode malloc faild!“）;
		exit（-1）;
	}

	//临时空间，用来保存每次求得的赫夫曼编码串
	//对于有n个叶子节点的赫夫曼树，各叶子节点的编码长度最长不超过n-1
	//外加一个‘\0‘结束符，因此分配的数组长度最长为n即可
	char *code = （char *）malloc（n*sizeof（char））;
	if（!code）
	{
		printf（“code malloc faild!“）;
		exit（-1）;
	}

	code[n-1] = ‘\0‘;  //编码结束符，亦是字符数组的结束标志
	//求每个字符的赫夫曼编码
	int i;
	for（i=0;i	{
		int current = i;           //定义当前访问的节点
		int father = HT[i].parent; //当前节点的父节点
		int start = n-1;           //每次编码的位置，初始为编码结束符的位置
		//从叶子节点遍历赫夫曼树直到根节点
		while（father != -1）
		{
			if（HT[father].lchild == current）   //如果是左孩子，则编码为0
				code[--start] = ‘0‘;    
			else                              //如果是右孩子，则编码为1       
				code[-

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-02-15 20:14  Huffman tree\
     文件        6170  2014-02-15 20:02  Huffman tree\Function.cpp
     目录           0  2014-02-15 20:14  Huffman tree\HuffmanCoding\
     目录           0  2014-02-15 20:14  Huffman tree\HuffmanCoding\Debug\
     文件        7974  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\Function.obj
     文件      184403  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\HuffmanCoding.exe
     文件      237916  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\HuffmanCoding.ilk
     文件      227172  2014-02-15 19:46  Huffman tree\HuffmanCoding\Debug\HuffmanCoding.pch
     文件      451584  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\HuffmanCoding.pdb
     文件        3575  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\main.obj
     文件       50176  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\vc60.idb
     文件       53248  2014-02-15 20:02  Huffman tree\HuffmanCoding\Debug\vc60.pdb
     文件        4490  2014-02-13 20:27  Huffman tree\HuffmanCoding\HuffmanCoding.dsp
     文件         534  2014-02-13 13:12  Huffman tree\HuffmanCoding\HuffmanCoding.dsw
     文件       50176  2014-02-15 20:14  Huffman tree\HuffmanCoding\HuffmanCoding.ncb
     文件       48640  2014-02-15 20:14  Huffman tree\HuffmanCoding\HuffmanCoding.opt
     文件         260  2014-02-15 20:02  Huffman tree\HuffmanCoding\HuffmanCoding.plg
     文件         983  2014-02-15 19:46  Huffman tree\data_structure.h
     文件         784  2014-02-15 20:02  Huffman tree\main.cpp