使用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++ 实现哈夫曼树的构造过程。

相关文章
|
11天前
|
C语言 C++ 开发者
深入探索C++:特性、代码实践及流程图解析
深入探索C++:特性、代码实践及流程图解析
|
2天前
|
安全 算法 程序员
探索C++的魅力:语言特性、编程实践及代码示例
C++是广泛应用的编程语言,尤其在系统级编程、应用开发、游戏和嵌入式系统中广泛使用。其主要特性包括:面向对象编程(封装、继承、多态),泛型编程(通过模板实现代码复用和类型安全),以及丰富的标准库和第三方库。在编程实践中,需注意内存管理、异常处理和性能优化。示例代码展示了面向对象和泛型编程,如类的继承和泛型函数的使用。C++的内存管理和库支持使其在解决复杂问题时具有高效和灵活性。
|
2天前
|
存储 算法 编译器
C++性能调优:从代码层面提升程序效率
本文探讨了C++程序性能调优的关键点:选择合适的数据结构和算法,例如用哈希表(如`std::unordered_map`)替换低效的数组或链表;减少不必要的内存分配和释放,利用智能指针和容器如`std::vector`自动管理内存;优化循环和条件语句,例如在循环外存储数组大小;利用编译器优化如`-O2`或`-O3`;以及使用性能分析工具如`gprof`、`callgrind`和`perf`识别并解决性能瓶颈。通过这些方法,可以有效提升C++程序的运行效率。
|
4天前
|
Serverless C++
C++多态性、虚函数、纯虚函数和抽象类知识网络构造
C++多态性、虚函数、纯虚函数和抽象类知识网络构造
|
11天前
|
存储 安全 算法
【Linux | C++ 】基于环形队列的多生产者多消费者模型(Linux系统下C++ 代码模拟实现)
【Linux | C++ 】基于环形队列的多生产者多消费者模型(Linux系统下C++ 代码模拟实现)
27 0
|
11天前
|
算法 Linux 数据安全/隐私保护
【Linux | C++ 】生产者消费者模型(Linux系统下C++ 代码模拟实现)
【Linux | C++ 】生产者消费者模型(Linux系统下C++ 代码模拟实现)
16 0
|
11天前
|
C++
【C++】一文深入浅出带你参透库中的几种 [ 智能指针 ]及其背后实现原理(代码&图示)
【C++】一文深入浅出带你参透库中的几种 [ 智能指针 ]及其背后实现原理(代码&图示)
|
11天前
|
C++ 数据格式
【C++】C++中的【文件IO流】使用指南 [手把手代码演示] & [小白秒懂]
【C++】C++中的【文件IO流】使用指南 [手把手代码演示] & [小白秒懂]
【C++】C++中的【文件IO流】使用指南 [手把手代码演示] & [小白秒懂]
|
11天前
|
编译器 C++
【C++】【C++的常变量取地址问题(对比C的不同)】const修饰的常变量&volatile修饰用法详解(代码演示)
【C++】【C++的常变量取地址问题(对比C的不同)】const修饰的常变量&volatile修饰用法详解(代码演示)
|
11天前
|
C++
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】