使用C++代码实现哈夫曼树的构造

简介: 使用C++代码实现哈夫曼树的构造

哈夫曼树是一种用于数据压缩的树形数据结构,其构造过程可以通过以下步骤实现:

 

1. 定义哈夫曼树的节点结构体,包括权重和指向左右子节点的指针。

2. 创建一个优先队列(最小堆),用于存储权重最小的节点。

3. 将所有权重作为单独的节点插入优先队列。

4. 重复以下步骤,直到只剩下一个节点为止:

     a. 从优先队列中取出两个权重最小的节点作为左右子节点。

     b. 创建一个新节点,权重为两个子节点的权重之和,将这个新节点插入优先队列。

5. 最终剩下的节点即为哈夫曼树的根节点。

 

以下是一个简单的 C++ 实现哈夫曼树构造的示例代码:

 

```cpp
#include <iostream>
#include <queue>
 
using namespace std;
 
struct Node {
    char data;
    int weight;
    Node* left;
    Node* right;
 
    Node(char data, int weight) : data(data), weight(weight), left(nullptr), right(nullptr) {}
};
 
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};
 
Node* buildHuffmanTree(priority_queue<Node*, vector<Node*>, Compare>& pq) {
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
 
        Node* right = pq.top();
        pq.pop();
 
        Node* parent = new Node('$', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
 
        pq.push(parent);
    }
 
    return pq.top();
}
 
void printCodes(Node* root, string code) {
    if (root == nullptr) {
        return;
    }
 
    if (root->data != '$') {
        cout << root->data << ": " << code << endl;
    }
 
    printCodes(root->left, code + "0");
    printCodes(root->right, code + "1");
}
 
int main() {
    priority_queue<Node*, vector<Node*>, Compare> pq;
 
    pq.push(new Node('a', 5));
    pq.push(new Node('b', 9));
    pq.push(new Node('c', 12));
    pq.push(new Node('d', 13));
    pq.push(new Node('e', 16));
    pq.push(new Node('f', 45));
 
    Node* root = buildHuffmanTree(pq);
 
    cout << "Huffman Codes are: " << endl;
    printCodes(root, "");
 
    return 0;
}
```

 

在这个示例中,我们定义了一个 `Node` 结构体表示哈夫曼树的节点,以及一个比较器 `Compare` 用于优先队列中节点的比较。然后我们实现了 `buildHuffmanTree` 函数来构建哈夫曼树,以及 `printCodes` 函数来打印哈夫曼编码。

 

`main` 函数中,我们创建了一个优先队列,并插入了一些示例数据。然后构建哈夫曼树,并打印出对应的哈夫曼编码。

 

这个示例展示了如何使用 C++ 实现哈夫曼树的构造过程。

相关文章
|
3月前
|
C++
C++ 语言异常处理实战:在编程潮流中坚守稳定,开启代码可靠之旅
【8月更文挑战第22天】C++的异常处理机制是确保程序稳定的关键特性。它允许程序在遇到错误时优雅地响应而非直接崩溃。通过`throw`抛出异常,并用`catch`捕获处理,可使程序控制流跳转至错误处理代码。例如,在进行除法运算或文件读取时,若发生除数为零或文件无法打开等错误,则可通过抛出异常并在调用处捕获来妥善处理这些情况。恰当使用异常处理能显著提升程序的健壮性和维护性。
74 2
|
3月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
229 0
|
5天前
|
算法 安全 C++
提高C/C++代码的可读性
提高C/C++代码的可读性
19 4
|
1月前
|
Linux C语言 C++
vsCode远程执行c和c++代码并操控linux服务器完整教程
这篇文章提供了一个完整的教程,介绍如何在Visual Studio Code中配置和使用插件来远程执行C和C++代码,并操控Linux服务器,包括安装VSCode、安装插件、配置插件、配置编译工具、升级glibc和编写代码进行调试的步骤。
195 0
vsCode远程执行c和c++代码并操控linux服务器完整教程
|
2月前
|
C++
继续更新完善:C++ 结构体代码转MASM32代码
继续更新完善:C++ 结构体代码转MASM32代码
|
2月前
|
C++ Windows
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
|
2月前
|
C++
2合1,整合C++类(Class)代码转换为MASM32代码的平台
2合1,整合C++类(Class)代码转换为MASM32代码的平台
|
2月前
|
前端开发 C++ Windows
C++生成QML代码与QML里面集成QWidget
这篇文章介绍了如何在C++中生成QML代码,以及如何在QML中集成QWidget,包括使用Qt Widgets嵌入到QML界面中的技术示例。
|
3月前
|
程序员 C++ 开发者
C++命名空间揭秘:一招解决全局冲突,让你的代码模块化战斗值飙升!
【8月更文挑战第22天】在C++中,命名空间是解决命名冲突的关键机制,它帮助开发者组织代码并提升可维护性。本文通过一个图形库开发案例,展示了如何利用命名空间避免圆形和矩形类间的命名冲突。通过定义和实现这些类,并在主函数中使用命名空间创建对象及调用方法,我们不仅解决了冲突问题,还提高了代码的模块化程度和组织结构。这为实际项目开发提供了宝贵的参考经验。
61 2
|
3月前
|
C++
拥抱C++面向对象编程,解锁软件开发新境界!从混乱到有序,你的代码也能成为高效能战士!
【8月更文挑战第22天】C++凭借其强大的面向对象编程(OOP)能力,在构建复杂软件系统时不可或缺。OOP通过封装数据和操作这些数据的方法于对象中,提升了代码的模块化、重用性和可扩展性。非OOP方式(过程化编程)下,数据与处理逻辑分离,导致维护困难。而OOP将学生信息及其操作整合到`Student`类中,增强代码的可读性和可维护性。通过示例对比,可以看出OOP使C++代码结构更清晰,特别是在大型项目中,能有效提高开发效率和软件质量。
33 1