C++ 数据结构 哈弗曼树的制作

 
输入
abbccc$
输出
9
样例输入 Copy
hello world$
样例输出 Copy
32
 
 

#include 
#include 
#include 
#define MAX_SIZE  1000
 
typedef char elemtype;
 
 
//带权值的二叉树
typedef struct BiTNode {
	elemtype data;
	int weight; //权重
	struct BiTNode* lchild, * rchild; /*左右孩子指针*/
}BiTNode, * BiTree;
 
 
//用单链表表示森林
typedef struct linkNode {
	BiTree tree;
	struct linkNode* next;
}LinkNode, * Forest;
 
//创建森林
int createForest(Forest& forest)
{
	//待补全，读入字符串，以‘$'为结束符，根据每个字符出现频率为权值，构造森林。并返回森林中树的个数
	
	int count = 0; // 森林中树的个数
	BiTree tree;
	LinkNode* p = forest;
 
	char ch;
	
 
	char list[128] = {0};
	scanf("%c", &ch);
	while (ch != '$') {		
		list[ch] += 1;
		scanf("%c", &ch);
	}
	for (int i = 0; i < 128; i++) {
		if (!list[i])
			continue;
 
		tree = (BiTNode*)malloc(sizeof(BiTNode));
		tree->data = i;
		tree->weight = list[i];
		tree->lchild = NULL;
		tree->rchild = NULL;
 
		LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
		newNode->tree = tree;
		newNode->next = NULL;
 
		p->next = newNode;
		p = p->next;
		count++;
	}	 	 
	return count;
}
 
 
void sortForest(Forest forest)
{
	int count = 0;
	LinkNode* p = forest->next;
	BiTree* trees = (BiTree*)malloc(sizeof(BiTree) * MAX_SIZE);
 
	// 将森林中所有的树存储到数组中
	while (p != NULL) {
		trees[count++] = p->tree;
		p = p->next;
	}
 
	// 使用冒泡排序将树按照权值从小到大排序
	for (int i = 0; i < count - 1; i++) {
		for (int j = 0; j < count - i - 1; j++) {
			if (trees[j]->weight > trees[j + 1]->weight) {
				BiTree tmp = trees[j];
				trees[j] = trees[j + 1];
				trees[j + 1] = tmp;
			}
		}
	}
 
 
	// 将排好序的树重新插入森林中
	p = forest->next;
	for (int i = 0; i < count; i++) {
		p->tree = trees[i];
		p = p->next;
	}
 
	free(trees);
}
 
BiTree createHuffmanTree(Forest forest)
{
	// 将森林中的所有树按照权值从小到大排序
	sortForest(forest);
 
	// 合并森林中的树，直到只剩下一棵树为止
	while (forest->next->next != NULL) {
		BiTree t1 = forest->next->tree;
		BiTree t2 = forest->next->next->tree;
		
 
		// 创建新的二叉树节点，作为t1和t2的父节点
		BiTree newNode = (BiTree)malloc(sizeof(BiTNode));
		newNode->data = '#';
		newNode->weight = t1->weight + t2->weight;
		newNode->lchild = t1;
		newNode->rchild = t2;
 
		// 将新节点插入森林中，并删除t1和t2
		LinkNode* newLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
		newLinkNode->tree = newNode;
		newLinkNode->next = forest->next->next->next;
		forest->next->next->next = newLinkNode;
		forest->next = forest->next->next->next;
 
		// 重新排序森林
		sortForest(forest);
	}
 
	// 返回剩下的最后一棵树，即哈夫曼树
	return forest->next->tree;
}
 
void calculateEncodingLength(BiTNode* root, int depth, int& totalLength) {
	if (!root) {
		return;
	}
 
	if (!root->lchild && !root->rchild) {
		totalLength += depth * root->weight;
	}
 
	calculateEncodingLength(root->lchild, depth + 1, totalLength);
	calculateEncodingLength(root->rchild, depth + 1, totalLength);
}
 
 
 
int main()
{
	Forest forest = (linkNode*)malloc(sizeof(linkNode));
	//森林的单链表包含一个头结点，头结点符号‘$'
	forest->tree = (BiTNode*)malloc(sizeof(BiTNode));
	forest->tree->data = '$';
	forest->next = NULL;
	createForest(forest);
	BiTree root = createHuffmanTree(forest);
	int totalLength = 0;
	calculateEncodingLength(root, 0, totalLength);
	printf("%d\n",totalLength);
	 
}