数据结构 Huffman Tree(哈夫曼树）

1.定义

哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。

2.简介

在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

4.代码如下：

#include
#include
#include
#include 
using namespace std;

#define MaxSize 1024
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct wordcnt {
	char ch;
	int cnt = 0;
}Count; 

typedef struct NumCount {
	Count count[MaxSize];
	int length = 0;
}NumCount;

typedef struct HTree {
	char data;
	char weight;
	int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedef struct HCode {
	char data;
	char* str; 
}*HuffmanCode;


Status ReadData(char *source); 
Status WordCount(char *data, NumCount *paraCnt);
Status Show(NumCount *paraCnt);
Status CreateHuffmanTree(HuffmanTree &HT, int length, NumCount cntarray);
Status select(HuffmanTree HT, int top, int *s1, int *s2);
Status CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int length);
Status Encode(char *data, HuffmanCode HC, int length);
Status Decode(HuffmanTree HT, int length);

int main(int argc, char** argv) {
	char data[MaxSize];
	NumCount Cntarray;
	ReadData(data);
	WordCount(data, &Cntarray);
	
	HuffmanTree tree;
	CreateHuffmanTree(tree, Cntarray.length, Cntarray);
	HuffmanCode code;
	CreateHuffmanCode(tree, code, Cntarray.length);
	Encode(data, code,Cntarray.length);
	Decode(tree, Cntarray.length);
	cout<<"Please view  the generated TXT file to chek the result"<length; ++j) {
			
			if(paraCnt->count[j].ch == data[i]) {
				
				++paraCnt->count[j].cnt;
				flag = 1;
				break;
			}
		}
		
		if (!flag) {
			
			paraCnt->count[paraCnt->length].ch = data[i];
			++paraCnt->count[paraCnt->length].cnt;
			++paraCnt->length;
		}
	}
	return OK;
}

Status Show(NumCount *paraCnt) {
	
	cout<<"the length is "<length<length; ++i) {
		
		cout<<"the character "<count[i].ch<<"appears "<count[i].cnt< 
5.创建一个txt文件，命名为in.txt,然后放在跟代码同一个文件夹里面，然后就可以了。