本文主要是介绍【数据结构与算法】哈夫曼树,哈夫曼编码 详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
哈夫曼树的数据结构。
struct TreeNode {ElemType data;TreeNode *left, *right;
};
using HuffmanTree = TreeNode *;
结构体包含三个成员:
data
是一个ElemType
类型的变量,用于存储哈夫曼树节点的数据。left
是一个指向TreeNode
类型的指针,用于指向哈夫曼树节点的左子节点。right
是一个指向TreeNode
类型的指针,用于指向哈夫曼树节点的右子节点。
Huffman树能够解决的问题是什么?
Huffman树,也称为Huffman编码树,主要用于数据压缩和编码。它可以解决如何以最短的方式来表示一组数据的问题,使得整体数据的存储或传输更加高效。
如何构造Huffman树?
- 根据给定的n个权值{w1,w2,……wn},构造n 棵二叉树的集合F={T1,T2,……,Tn},其中每棵二叉树Ti 中只有一个带权为wi 的根结点,其左右子树均为空。
- 在森林F中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。
- 在森林中删除这两棵树,同时将新得到的二叉树加入森林中。
- 重复上述2和3两步直到只含一棵树为止,这棵树即哈夫曼树。
TreeNode *createTreeNode(ElemType e, TreeNode *l, TreeNode *r) {TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));if (!t) {return NULL;}t->data = e;t->left = l;t->right = r;return t;
}HuffmanTree createHuffmanTree(int n, ElemType *a, int *f) {priority_queue<Node> hmin;for (int i = 0; i < n; i++) {TreeNode *t = createTreeNode(a[i], nullptr, nullptr);hmin.push({f[i], t});}while (hmin.size() > 1) {Node a = hmin.top();hmin.pop();Node b = hmin.top();hmin.pop();if (a.f > b.f) {swap(a, b);}TreeNode *t = createTreeNode(' ', a.node, b.node);// cout << a.f << " " << b.f << endl;hmin.push({a.f + b.f, t});}return hmin.top().node;
}
这篇关于【数据结构与算法】哈夫曼树,哈夫曼编码 详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!