本文主要是介绍C++ 数据结构 哈弗曼树的制作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
输入
abbccc$
输出
9
样例输入 Copy
hello world$
样例输出 Copy
32
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX_SIZE 1000typedef 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和t2LinkNode* 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);}这篇关于C++ 数据结构 哈弗曼树的制作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
