首页 > 编程语言 >C++实现哈夫曼树

C++实现哈夫曼树

时间：2024-05-30 11:32:30浏览次数：26  
标签：right 哈夫曼 实现 C++ minHeap MinHeapNode freq 节点

哈夫曼树（Huffman Tree）是一种特殊的二叉树，通常用于数据压缩的哈夫曼编码。在哈夫曼树中，频率（或权重）较高的节点离根节点较远，而频率较低的节点离根节点较近。这样，我们可以为频率较低的节点分配较短的编码，为频率较高的节点分配较长的编码，从而实现数据的压缩。本文将详细介绍如何使用C++实现哈夫曼树，并附有完整的代码。

一、哈夫曼树的基本概念

  1. 节点权重：在哈夫曼树中，每个节点都有一个权重，表示该节点在数据中出现的频率。
  2. 哈夫曼编码：从根节点到每个叶子节点的路径可以用来表示该叶子节点对应的字符的编码。由于哈夫曼树的构造特性，频率较高的字符的编码较长，频率较低的字符的编码较短。
  3. 最小堆：在构建哈夫曼树的过程中，我们通常使用最小堆来维护节点集合，以便快速找到权重最小的两个节点进行合并。

二、C++实现哈夫曼树的步骤

  1. 定义节点结构体：包括节点的权重、字符（或索引）、左右子节点指针等。
  2. 实现最小堆：用于维护节点集合，并实现插入节点、删除最小节点等操作。
  3. 构建哈夫曼树：从节点集合中取出权重最小的两个节点，合并为一个新节点，并将新节点插入节点集合。重复此过程，直到节点集合中只剩下一个节点，即为哈夫曼树的根节点。
  4. 生成哈夫曼编码：从根节点开始遍历哈夫曼树，为每个叶子节点生成哈夫曼编码。

三、详细代码实现

#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <vector>

using namespace std;

struct MinHeapNode {
    char data;
    unsigned freq;
    MinHeapNode* left, *right;

    MinHeapNode(char data, unsigned freq) {
        this->data = data;
        this->freq = freq;
        left = right = nullptr;
    }
};

struct MinHeap {
    priority_queue<MinHeapNode*, vector<MinHeapNode*>, function<bool(MinHeapNode*, MinHeapNode*)>> minHeap;

    // 比较函数，用于priority_queue中的元素比较
    auto compare = [](MinHeapNode* l, MinHeapNode* r) {
        return (l->freq > r->freq);
    };

    // 插入节点
    void insertNode(MinHeapNode* minHeapNode) {
        minHeap.push(minHeapNode);
    }

    // 提取最小节点
    MinHeapNode* extractMin() {
        MinHeapNode* temp = minHeap.top();
        minHeap.pop();
        return temp;
    }

    // 判断堆是否为空
    bool isEmpty() {
        return minHeap.empty();
    }
};

// 构造哈夫曼树
MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    MinHeap minHeap;

    // 创建节点并插入最小堆
    for (int i = 0; i < size; ++i) {
        minHeap.insertNode(new MinHeapNode(data[i], freq[i]));
    }

    // 当堆中只剩下一个节点时，停止构建
    while (!minHeap.isEmpty()) {
        MinHeapNode* left = minHeap.extractMin();
        MinHeapNode* right;

        // 如果堆中只剩下一个节点，则将其视为另一个子节点
        if (minHeap.isEmpty()) {
            right = left;
        } else {
            right = minHeap.extractMin();
        }

        // 合并两个节点，并创建一个新的内部节点
        MinHeapNode* top = new MinHeapNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;

        // 将新节点插入最小堆
        minHeap.insertNode(top);
    }

    // 返回根节点
    return minHeap.extractMin();
}

// 打印哈夫曼编码  
void printCodes(MinHeapNode* root, string str, map<char, string>& huffmanCodes) {  
    if (!root) return;  
  
    if (root->data != '$') {  
        // 叶子节点，将当前路径保存到编码映射中  
        huffmanCodes[root->data] = str;  
    }  
  
    // 递归遍历左子树，添加'0'到路径中  
    printCodes(root->left, str + "0", huffmanCodes);  
    // 递归遍历右子树，添加'1'到路径中  
    printCodes(root->right, str + "1", huffmanCodes);  
}  
  
// 主函数  
int main() {  
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};  
    int freq[] = {5, 9, 12, 13, 16, 45};  
    int size = sizeof(arr) / sizeof(arr[0]);  
  
    // 构建哈夫曼树  
    MinHeapNode* root = buildHuffmanTree(arr, freq, size);  
  
    // 打印哈夫曼编码  
    map<char, string> huffmanCodes;  
    printCodes(root, "", huffmanCodes);  
  
    // 输出哈夫曼编码  
    cout << "Huffman Codes: " << endl;  
    for (auto& code : huffmanCodes) {  
        cout << code.first << ": " << code.second << endl;  
    }  
  
    // 释放哈夫曼树占用的内存（需要编写相应的函数来递归地释放）  
  
    return 0;  
}  
  
// 注意：为了完整起见，应该编写一个递归函数来释放哈夫曼树占用的内存。  
  
// 示例输出（可能会因权重不同而有所变化）：  
// Huffman Codes:   
// a: 1111  
// b: 1110  
// c: 110  
// d: 10  
// e: 01  
// f: 00

为了完整实现C++中的哈夫曼树，并包括内存释放的部分，可以添加一个函数来遍历树并释放其内存。下面是完整的代码，包括内存释放的功能：

#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <vector>

using namespace std;

struct MinHeapNode {
    char data;
    unsigned freq;
    MinHeapNode* left, *right;

    MinHeapNode(char data, unsigned freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}

    ~MinHeapNode() {
        // 递归释放左右子节点的内存
        if (left) delete left;
        if (right) delete right;
    }
};

struct MinHeap {
    priority_queue<MinHeapNode*, vector<MinHeapNode*>, function<bool(MinHeapNode*, MinHeapNode*)>> minHeap;

    // 比较函数，用于priority_queue中的元素比较
    auto compare = [](MinHeapNode* l, MinHeapNode* r) {
        return (l->freq > r->freq);
    };

    // 插入节点
    void insertNode(MinHeapNode* minHeapNode) {
        minHeap.push(minHeapNode);
    }

    // 提取最小节点
    MinHeapNode* extractMin() {
        MinHeapNode* temp = minHeap.top();
        minHeap.pop();
        return temp;
    }

    // 判断堆是否为空
    bool isEmpty() {
        return minHeap.empty();
    }
};

// 构造哈夫曼树
MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    MinHeap minHeap;

    // 创建节点并插入最小堆
    for (int i = 0; i < size; ++i) {
        minHeap.insertNode(new MinHeapNode(data[i], freq[i]));
    }

    // 当堆中只剩下一个节点时，停止构建
    while (!minHeap.isEmpty()) {
        MinHeapNode* left = minHeap.extractMin();
        MinHeapNode* right;

        // 如果堆中只剩下一个节点，则将其视为另一个子节点
        if (minHeap.isEmpty()) {
            right = left;
        } else {
            right = minHeap.extractMin();
        }

        // 合并两个节点，并创建一个新的内部节点
        MinHeapNode* top = new MinHeapNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;

        // 将新节点插入最小堆
        minHeap.insertNode(top);
    }

    // 返回根节点
    return minHeap.extractMin();
}

// 打印哈夫曼编码
void printCodes(MinHeapNode* root, string str, map<char, string>& huffmanCodes) {
    if (!root) return;

    if (root->data != '$') {
        // 叶子节点，将当前路径保存到编码映射中
        huffmanCodes[root->data] = str;
    }

    // 递归遍历左子树，添加'0'到路径中
    printCodes(root->left, str + "0", huffmanCodes);
    // 递归遍历右子树，添加'1'到路径中
    printCodes(root->right, str + "1", huffmanCodes);
}

// 释放哈夫曼树占用的内存
void freeHuffmanTree(MinHeapNode* root) {
    if (!root) return;

    // 递归释放左右子树
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);

    // 释放当前节点
    delete root;
}

// 主函数
int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 构建哈夫曼树
    MinHeapNode* root = buildHuffmanTree(arr, freq, size);

    // 打印哈夫曼编码
    map<char, string> huffmanCodes;
    printCodes(root, "", huffmanCodes);

    // 输出哈夫曼编码
    cout << "Huffman Codes: " << endl;
    for (auto& code : huffmanCodes) {
        cout << code.first << ": " << code.second << endl;
    }

    // 释放哈夫曼树占用的内存
    freeHuffmanTree(root);

    return 0;
}

// 示例输出（可能会因权重不同而有所变化）：
// Huffman Codes: 
// a: 1111
// b: 1110
// c: 110
// d: 10
// e: 01
// f: 00

// 注意：
// 在这个示例中，我们定义了一个简单的MinHeapNode结构体，它包含一个析构函数来递归地释放左右子节点的内存。
// 在freeHuffmanTree函数中，我们递归地调用该函数来释放整个树的内存。
// 在main函数中，我们调用了这个释放函数来确保程序结束时不再占用内存。
//
// 请注意，由于哈夫曼树的构建和内存管理可能因不同的实现而有所不同，因此上述代码仅作为示例。
// 在实际应用中，您可能需要根据自己的需求和环境进行调整和优化。

标签：right,哈夫曼,实现,C++,minHeap,MinHeapNode,freq,节点
From： https://blog.csdn.net/qq_41256535/article/details/139251153

相关文章

  • 微信小程序之实现弹窗组件及点击弹窗按钮实现页面跳转
    创建一个名为PopupWindow的弹窗组件：   1、创建组件目录结构：    在项目的components目录下新建一个名为PopupWindow的文件夹，里面包含四个核心文件： PopupWindow.wxml 、PopupWindow.wxss、PopupWindow.js 、PopupWindow.json   2、编写组件文件......
  • 基于SqlSugar的开发框架循序渐进介绍（20）-- 在基于UniApp+Vue的移动端实现多条件查询的
    在做一些常规应用的时候，我们往往需要确定条件的内容，以便在后台进行区分的进行精确查询，在移动端，由于受限于屏幕界面的情况，一般会对多个指定的条件进行模糊的搜索，而这个搜索的处理，也是和前者强类型的条件查询处理类似的处理过程，因此本篇随笔探讨两种不同查询在前端界面上的展示效......
  • 使用 Bootstrap 5 无法在 php 文件中实现智能识别
    我使用VisualStudioCode在php文件中使用Bootstrap5。Bootstrap会在我编写HTML代码时向我显示建议，如第一张图片。但当我编写HTML代码时，它什么也不显示，如第二张图片。我尝试使用了许多扩展，并在设置中将php的执行路径和"php":"html"设置为emmet语言。我......
  • 如何使用前端表格控件实现多数据源整合？
    前言作为表格产品的典型应用场景之一，几乎所有的行业都会存在类Excel报表开发这样的应用场景，而在这些应用场景中，经常会遇见下面的这些痛点：报表数据往往来自多个不同的数据源，需要报表系统能够同时连接多个数据源，并融合不同的数据格式实际的报表中需要对数据结果进行逻辑计算，例......
  • MySQL 与 Redis 缓存一致性的实现与挑战
    缓存是提高应用性能的重要手段之一，而MySQL和Redis是两种常用的数据存储和缓存技术。在许多应用中，常常将Redis用作缓存层，以加速对数据的访问。然而，在使用MySQL和Redis组合时，保持缓存与数据库之间的一致性是一个不得不考虑的问题。一、缓存一致性的挑战MySQL和Re......
  • django基于大数据的汽车销售可视化系统的设计与实现论文(1)
    摘要近年来，随着互联网的蓬勃发展，企事业单位对信息的管理提出了更高的要求。以传统的管理方式已无法满足现代人们的需求。为了迎合时代需求，优化管理效率，各种各样的管理系统应运而生，随着各行业的不断发展，汽车销售可视化系统分析系统也逐渐进入了信息化的进程。这个系统的设......
  • 基于Java公考综合学习平台设计与实现论文
    摘要本文的重点是对公考综合学习平台展开了详细的描述，其中包含了其目前的发展状况和所涉及到的发展背景。接着，本文还讨论了该系统的设计目的，还讨论了系统的需求，并提出了整体的设计方案。对于该系统的设计和实现，也都进行了较为详细的讨论，并在此基础上，对公考综合学习平台展......
  • 基于Springboot + vue实现的蜗牛兼职网--附源码+论文+数据库
    基于Springboot+vue实现的蜗牛兼职网摘 要随着科学技术的飞速发展，社会的方方面面、各行各业都在努力与现代的先进技术接轨，通过科技手段来提高自身的优势，蜗牛兼职网当然也不能排除在外。蜗牛兼职网是以实际运用为开发背景，运用软件工程原理和开发方法，采用springboot框架构......
  • paddleXOCR c++ vs2022编译以及使用
    PaddleOCR的使用（C++)——Windows编译篇-夕西行-博客园(cnblogs.com) 参考官方的指导地址，按照他的来很全PaddleOCR/deploy/cpp_infer/docs/windows_vs2019_build.mdatmain·PaddlePaddle/PaddleOCR·GitHub1.opencv我这里用的4.4（高版本应该也可以）Releases-OpenC......
  • C++设计模式的原则
    1、依赖倒置原则(DIP)·高层模块(稳定)不应该依赖于低层模块(变化)，二者都应该依赖于抽象稳定)。·抽象(稳定)不应该依赖于实现细节(变化)，实现细节应该依赖于抽象(稳定)。2、开放封闭原则(OCP)·对扩展开放，对更改封闭。·类模块应该是可扩展的，但是不可修改。3、单一职责原......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99