根据哈夫曼树树,求哈夫曼树编码的代码具体实现
时间: 2023-07-08 07:51:01 浏览: 93
哈夫曼树的编码的实现
哈夫曼编码是一种基于字符出现频率来构建可变长度编码的压缩方式。下面是求哈夫曼树编码的具体实现:
1. 定义一个结构体来存储哈夫曼树结点的信息,包括字符、权值、左右子树指针和编码信息等。
```
struct HuffmanNode {
char ch; // 字符
int weight; // 权值
HuffmanNode *left; // 左子树
HuffmanNode *right; // 右子树
string code; // 编码信息
};
```
2. 定义一个比较函数,用来对哈夫曼树结点按照权值从小到大排序。
```
struct cmp {
bool operator() (HuffmanNode *a, HuffmanNode *b) const {
return a->weight > b->weight;
}
};
```
3. 构建哈夫曼树,首先将每个字符和它的权值存储在一个数组中,然后将数组中的元素按照权值从小到大排序。接着,取出权值最小的两个元素作为左右子树,构建一个新的哈夫曼树结点,它的权值为左右子树的权值之和,将它插入到数组中,并将数组中的元素按照权值重新排序。重复这个过程,直到数组中只剩下一个结点,这个结点就是哈夫曼树的根节点。
```
HuffmanNode *buildHuffmanTree(char *ch, int *weight, int n) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
for (int i = 0; i < n; i++) {
HuffmanNode *node = new HuffmanNode();
node->ch = ch[i];
node->weight = weight[i];
node->left = NULL;
node->right = NULL;
pq.push(node);
}
while (pq.size() > 1) {
HuffmanNode *left = pq.top();
pq.pop();
HuffmanNode *right = pq.top();
pq.pop();
HuffmanNode *parent = new HuffmanNode();
parent->ch = '\0';
parent->weight = left->weight + right->weight;
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
```
4. 对哈夫曼树进行前序遍历,记录每个叶子结点的编码信息,编码信息是由每个叶子结点到根节点的路径上的方向(0表示向左,1表示向右)组成的。
```
void getHuffmanCode(HuffmanNode *root, string code) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
root->code = code;
return;
}
getHuffmanCode(root->left, code + "0");
getHuffmanCode(root->right, code + "1");
}
```
5. 最后,根据每个字符的编码信息,将原始文本进行编码压缩。
```
string encodeText(string text, HuffmanNode *root) {
string result;
for (int i = 0; i < text.length(); i++) {
char ch = text[i];
HuffmanNode *node = findHuffmanNode(root, ch);
result += node->code;
}
return result;
}
```
这样,就可以求出哈夫曼树的编码了。
阅读全文