哈夫曼树基本操作代码实现

目录

哈夫曼树功能函数

测试样例

实现代码

哈夫曼树功能函数

void CreatHuffmanTree(HuffmanTree &HT, int n);                                       //构造哈夫曼树 

void PrintT(HuffmanTree HT, int n);                                                              //打印哈夫曼树

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n);        //构造哈夫曼编码

void PrintC(HuffmanTree HT, HuffmanCode HC, int n);                               //打印哈夫曼编码 

测试样例

样例输入：

8
7 19 2 6 32 3 21 10

样例输出：

打印哈夫曼树
7 11 0 0
19 13 0 0
2 9 0 0
6 10 0 0
32 14 0 0
3 9 0 0
21 13 0 0
10 11 0 0
5 10 3 6
11 12 9 4
17 12 1 8
28 14 10 11
40 15 2 7
60 15 12 5
100 0 13 14

打印哈夫曼编码
7：1010
19：00
2：10000
6：1001
32：11
3：10001
21：01
10：1011

 上述例子中的哈夫曼树如下图所示

实现代码

#include<bits/stdc++.h>
using namespace std;

typedef struct {
	int weight;
	int parent, lch, rch;
} HTNode, *HuffmanTree; 

typedef char * HuffmanCode[10];

//找权值最小和第二小的结点 ,s1第二小,s2最小
void  Select(HuffmanTree HT, int n, int &s1, int &s2) {
	int min = 32767 , low = 32767;
	for(int i = 1; i <= n; i++) {
		if(min > HT[i].weight && !HT[i].parent) {
			s1 = s2;
			low = min;
			s2 = i;
			min = HT[i].weight;
		}
		else if(low > HT[i].weight && !HT[i].parent) {
			s1 = i;
			low = HT[i].weight;
		}
	}
}

//构造哈夫曼树 
void CreatHuffmanTree(HuffmanTree &HT, int n) {
	if(n <= 1)
		return ;
	int m = 2 * n - 1;
	HT = new HTNode[m + 1];
	for(int i = 1; i <= m; i++) {
		HT[i].lch = 0;
		HT[i].rch = 0;
		HT[i].parent = 0;
	}
	for(int i = 1; i <= n; i++) {
		cin >> HT[i].weight;
	}
	for(int i = n + 1; i <= m; i++) {
		int s1 = -1, s2 = -1;
		Select(HT, i, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].rch = s1;
		HT[i].lch = s2;
		HT[i].weight = HT[s1].weight +  HT[s2].weight;
	}
}

//打印哈夫曼树
void PrintT(HuffmanTree HT, int n) {
	int m = 2 * n - 1;
	for(int i = 1; i <= m; i++) {
		cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lch << " " << HT[i].rch <<endl;
	}
} 

//构造哈夫曼编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
	char tmp[n];
	tmp[n-1] = '\0';
	int start, c, f;
	for(int i = 1; i <= n; i++) {
		start = n - 1;
		c = i;
		f = HT[i].parent;
		while(f){
			if(HT[f].lch == c)
				tmp[--start] = '0';
			else
				tmp[--start] = '1';
			c = f;
			f = HT[f].parent;
		}
		HC[i] = (char *)malloc((n-start)*sizeof(char));
		strcpy(HC[i], &tmp[start]);
	}
}

//打印哈夫曼编码 
void PrintC(HuffmanTree HT, HuffmanCode HC, int n) {
	for(int i = 1; i <= n; i++)
		cout << HT[i].weight << "：" << HC[i] << endl;
}

int main() {
	int n;
	cout << "请输入结点数：" << endl;
	cin >> n;
	HuffmanTree HT;
	CreatHuffmanTree(HT, n);
	cout << endl << "打印哈夫曼树" << endl; 
	PrintT(HT, n);
	HuffmanCode HC;
	CreatHuffmanCode(HT, HC, n);
	cout<< endl << "打印哈夫曼编码" << endl;
	PrintC(HT, HC, n);
	return 0;
}