AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】

2025-01-08 59
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构——树】哈夫曼树（头歌实践教学平台习题）【合集】目录任务描述相关知识测试说明我的通关代码：测试结果：任务描述本关任务：编写一个程序构建哈夫曼树和生成哈夫曼编码。相关知识为了完成本关任务，你需要掌握：1.如何构建哈夫曼树，2.如何生成哈夫曼编码。测试说明平台会对你编写的代码进行测试：测试输入：1192677541518462450242195190181174157138124123(用户分别输入所列单词的频度）预

 

目录😋

任务描述

相关知识

如何构建哈夫曼树

  1. 定义节点结构体

  2. 实现比较函数（用于优先队列）

  3. 构建哈夫曼树

生成哈夫曼编码

整体结构说明：

各函数详细解释：

测试说明

通关代码：

测试结果：

任务描述

本关任务：编写一个程序构建哈夫曼树和生成哈夫曼编码。

相关知识

为了完成本关任务，你需要掌握：

  1. 如何构建哈夫曼树，
  2. 如何生成哈夫曼编码。

如何构建哈夫曼树

  1. 定义节点结构体

       首先，需要定义哈夫曼树节点的结构体。一个哈夫曼节点包含以下几个部分：

  • 左子节点指针。
  • 右子节点指针。
  • 节点的权重（通常是字符出现的频率）。
  • 可能还包含节点表示的数据（例如字符）。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
image.gif

  2. 实现比较函数（用于优先队列）

       为了能够在构建哈夫曼树时方便地找到权重最小的节点，通常使用优先队列（priority_queue）。需要定义一个比较函数，使得优先队列可以根据节点权重进行排序。

struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
image.gif

  3. 构建哈夫曼树

       构建哈夫曼树的主要步骤如下：

  1. 将所有节点放入优先队列。
  2. 每次从优先队列中取出两个权重最小的节点，创建一个新的父节点，其权重为这两个节点权重之和，并将这两个节点作为新父节点的左右子节点，然后将新父节点放入优先队列。
  3. 重复步骤 2，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。

以下是构建哈夫曼树的函数：

#include <iostream>
#include <queue>
#include <vector>
// 1. 定义节点结构体
// 哈夫曼树节点的结构体定义。一个哈夫曼节点包含以下几个部分：
// - 左子节点指针，用于指向该节点的左子树节点。
// - 右子节点指针，用于指向该节点的右子树节点。
// - 节点的权重（通常是字符出现的频率），代表该节点在构建树过程中的重要程度等相关属性。
// - 可能还包含节点表示的数据（例如字符），在某些应用场景下用于标识该节点对应的具体内容。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    // 构造函数，用于方便地初始化哈夫曼节点的权重和数据成员，同时将左右子节点指针初始化为nullptr。
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
// 2. 实现比较函数（用于优先队列）
// 为了能够在构建哈夫曼树时方便地找到权重最小的节点，通常使用优先队列（priority_queue）。
// 需要定义一个比较函数，使得优先队列可以根据节点权重进行排序。
// 这里定义的比较函数是一个函数对象（仿函数），重载了括号运算符，使得它可以像函数一样被调用。
// 它的作用是比较两个哈夫曼节点指针所指向节点的权重大小，返回 true 表示第一个节点的权重大于第二个节点的权重，
// 这样在优先队列中就会按照权重从小到大的顺序来排列节点（因为优先队列默认是大顶堆，通过这样的比较函数实现小顶堆效果）。
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
// 3. 构建哈夫曼树
// 构建哈夫曼树的主要步骤如下：
// 该函数接受一个包含所有初始节点（通常是代表字符及其频率的节点）的向量作为参数，返回构建好的哈夫曼树的根节点指针。
HuffmanNode* buildHuffmanTree(const std::vector<HuffmanNode*>& nodes) {
    // 创建一个优先队列，用于存放哈夫曼节点指针，使用自定义的比较函数 CompareNodes 来确定节点的优先级顺序，即按照权重从小到大排列。
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNodes> pq;
    // 将所有节点放入优先队列
    for (HuffmanNode* node : nodes) {
        pq.push(node);
    }
    // 循环执行以下操作，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
    while (pq.size() > 1) {
        // 每次从优先队列中取出两个权重最小的节点
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        // 创建一个新的父节点，其权重为这两个节点权重之和
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, '\0');
        // 将取出的两个节点作为新父节点的左右子节点
        parent->left = left;
        parent->right = right;
        // 将新父节点放入优先队列，以便后续继续参与构建树的合并操作。
        pq.push(parent);
    }
    // 最后返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，则返回 nullptr（这里暂未做额外的错误处理，可根据实际需求完善）。
    return pq.empty()? nullptr : pq.top();
}
// 辅助函数，用于释放哈夫曼树的内存空间（采用后序遍历的方式递归释放节点）。
// 这是一个很重要的函数，避免内存泄漏，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
void freeHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) {
        return;
    }
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}
// 以下是一个简单的测试示例，用于展示如何使用构建哈夫曼树的函数。
int main() {
    // 模拟创建一些初始节点，这里简单地手动构造了几个节点，实际应用中可能根据字符频率统计等方式来生成这些节点。
    std::vector<HuffmanNode*> nodes;
    nodes.push_back(new HuffmanNode(5, 'a'));
    nodes.push_back(new HuffmanNode(9, 'b'));
    nodes.push_back(new HuffmanNode(12, 'c'));
    nodes.push_back(new HuffmanNode(13, 'd'));
    nodes.push_back(new HuffmanNode(16, 'e'));
    // 调用构建哈夫曼树的函数，得到哈夫曼树的根节点指针。
    HuffmanNode* root = buildHuffmanTree(nodes);
    // 这里可以进行后续对哈夫曼树的操作，比如编码、解码等，暂时省略这些操作的具体实现代码。
    // 释放哈夫曼树的内存空间，避免内存泄漏。
    freeHuffmanTree(root);
    return 0;
}
image.gif

节点结构体部分:

  HuffmanNode 结构体清晰地定义了哈夫曼树节点的构成要素。其中 weight 成员变量用于记录节点的权重，在文本压缩等应用场景下通常对应字符出现的频率，权重越小，表示该字符相对出现的次数越少；data 成员变量用于存放节点所代表的数据内容，比如在基于字符构建哈夫曼树时，这里可以存放具体的字符；left 和 right 指针分别指向该节点的左子节点和右子节点，用于构建树的层次结构，初始化为 nullptr 表示新建节点时默认没有子节点。

比较函数部分：

  CompareNodes 结构体通过重载 operator() 函数实现了一个比较函数对象（仿函数）。在 std::priority_queue（优先队列）的使用中，这个比较函数决定了队列中元素的排列顺序。因为默认情况下，std::priority_queue 是大顶堆（即队头元素是最大的元素），但我们希望按照节点权重从小到大来管理节点，所以通过这个比较函数返回 a->weight > b->weight 的结果，使得优先队列实际上变成了小顶堆，这样每次调用 pq.top() 就能获取到权重最小的节点。

 

构建哈夫曼树函数部分:

  • 节点入队：首先创建了一个 std::priority_queue 类型的优先队列 pq，并将输入的所有节点指针通过循环依次放入队列中。这些输入节点可以看作是最初的、独立的叶子节点，代表了构建哈夫曼树的基础元素，每个节点都有其特定的权重和可能的数据标识。
  • 循环构建树：在 while 循环中，只要优先队列中节点数量大于 1，就不断进行以下操作。每次先取出两个权重最小的节点（通过两次调用 pq.top() 并接着 pq.pop() 实现），这两个节点将作为新生成节点的左右子节点。然后创建一个新的父节点，其权重设置为取出的两个子节点权重之和，并且将刚才取出的两个节点分别赋值给新父节点的左右子节点指针。最后把这个新创建的父节点再放入优先队列中，参与后续的合并操作。这样不断合并节点，树的层次结构逐渐形成，直到队列中只剩下一个节点，这个节点就是整个哈夫曼树的根节点，代表了所有节点合并后的最终结果，通过它可以访问到整棵哈夫曼树的各个部分。
  • 内存释放：由于在构建哈夫曼树过程中使用了 new 操作符动态分配内存来创建节点，所以需要编写 freeHuffmanTree 函数来释放这些内存，避免内存泄漏。该函数采用后序遍历的方式，先递归释放左子树节点内存，再释放右子树节点内存，最后释放根节点内存，确保整个哈夫曼树所占用的内存都能正确回收。

测试示例部分:

       在 main 函数中，模拟创建了一个包含几个节点的向量，这些节点的权重和对应的数据（字符）是手动设定的，仅用于简单展示构建哈夫曼树的流程。实际应用中，这些节点通常是根据文本中字符出现的频率统计等操作来生成的。然后调用 buildHuffmanTree 函数构建哈夫曼树，得到根节点指针后，虽然这里省略了后续对哈夫曼树进行编码、解码等实际操作的代码，但展示了基本的使用流程，最后调用 freeHuffmanTree 函数来释放哈夫曼树所占用的内存空间，保证程序的内存管理正确

生成哈夫曼编码

       构建哈夫曼树后，可以通过遍历哈夫曼树来生成每个字符的哈夫曼编码。通常使用递归函数来实现。

以下是一个简单的生成哈夫曼编码的函数示例：

void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) return;
    if (root->data!= '\0') {
        huffmanCodes[root->data] = code;
    }
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
image.gif

以下是一个使用上述函数构建哈夫曼树和生成哈夫曼编码的完整示例：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;
// 1. 定义哈夫曼树节点结构体
// 该结构体用于表示哈夫曼树中的节点，包含以下几个重要成员：
// - weight：节点的权重，通常代表字符在文本中出现的频率，权重值越大，表示对应字符出现的相对次数越多。
// - data：节点所代表的数据，这里一般是字符本身，如果是其他应用场景也可以是其他类型的数据标识。
// - left 和 right：分别指向该节点的左子节点和右子节点的指针，用于构建哈夫曼树的树形结构，初始化为 nullptr 表示新建节点时无子节点。
struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;
    // 构造函数，用于方便地初始化节点的权重和数据成员，同时将左右子节点指针初始化为 nullptr。
    HuffmanNode(int w, char d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
// 2. 定义比较函数结构体（用于优先队列）
// 这个结构体实现了一个函数对象（仿函数），通过重载括号运算符来定义比较规则。
// 在优先队列（priority_queue）中使用，目的是按照节点的权重从小到大对节点进行排序。
// 这样优先队列的顶部元素始终是权重最小的节点，方便在构建哈夫曼树时取出权重最小的节点进行合并操作。
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};
// 3. 构建哈夫曼树的函数
// 该函数接受一个包含所有初始节点（通常是代表字符及其频率的节点）的向量作为参数，返回构建好的哈夫曼树的根节点指针。
HuffmanNode* buildHuffmanTree(vector<HuffmanNode*>& nodes) {
    // 创建一个优先队列，用于存放哈夫曼节点指针，使用自定义的比较函数 CompareNodes 来确定节点的优先级顺序，即按照权重从小到大排列。
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> pq;
    // 将所有节点放入优先队列，如果输入的节点向量为空，这里可以添加错误处理逻辑，暂时简单打印提示信息并返回 nullptr。
    if (nodes.empty()) {
        cout << "输入的节点向量为空，无法构建哈夫曼树！" << endl;
        return nullptr;
    }
    for (HuffmanNode* node : nodes) {
        pq.push(node);
    }
    // 循环执行以下操作，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
    while (pq.size() > 1) {
        // 每次从优先队列中取出两个权重最小的节点
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        // 创建一个新的父节点，其权重为这两个节点权重之和
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, '\0');
        // 将取出的两个节点作为新父节点的左右子节点
        parent->left = left;
        parent->right = right;
        // 将新父节点放入优先队列，以便后续继续参与构建树的合并操作。
        pq.push(parent);
    }
    // 返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，这里返回的是之前已经处理的 nullptr。
    return pq.top();
}
// 4. 生成哈夫曼编码的函数
// 该函数通过递归遍历哈夫曼树来生成每个字符对应的哈夫曼编码，将其存储在一个无序映射（unordered_map）中。
// 参数说明：
// - root：哈夫曼树的根节点指针，从根节点开始递归遍历整棵树。
// - code：当前路径的编码字符串，随着递归遍历不断累加，向左子树走添加 '0'，向右子树走添加 '1'。
// - huffmanCodes：无序映射，用于存储字符及其对应的哈夫曼编码，键为字符，值为编码字符串。
void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodes) {
    // 如果当前节点为空，直接返回，这是递归的边界条件，用于结束递归调用。
    if (root == nullptr) return;
    // 如果当前节点的数据不为空字符（'\0'），说明该节点代表一个实际的字符（非中间合并节点），
    // 将当前的编码字符串赋值给该字符对应的映射项，即记录下该字符的哈夫曼编码。
    if (root->data!= '\0') {
        huffmanCodes[root->data] = code;
    }
    // 递归遍历左子树，将当前编码字符串添加 '0' 后继续递归，用于生成左子树中各字符的哈夫曼编码。
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    // 递归遍历右子树，将当前编码字符串添加 '1' 后继续递归，用于生成右子树中各字符的哈夫曼编码。
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
// 5. 辅助函数，用于释放哈夫曼树的内存空间（采用后序遍历的方式递归释放节点）。
// 这是一个很重要的函数，避免内存泄漏，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
void freeHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) {
        return;
    }
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}
// 6. 主函数，用于测试哈夫曼树构建及编码生成的功能。
int main() {
    // 示例：假设字符和频率
    vector<HuffmanNode*> nodes;
    nodes.push_back(new HuffmanNode(5, 'a'));
    nodes.push_back(new HuffmanNode(9, 'b'));
    nodes.push_back(new HuffmanNode(12, 'c'));
    nodes.push_back(new HuffmanNode(13, 'd'));
    nodes.push_back(new HuffmanNode(16, 'e'));
    // 构建哈夫曼树，获取根节点指针，如果构建失败（返回 nullptr），则直接结束程序。
    HuffmanNode* root = buildHuffmanTree(nodes);
    if (root == nullptr) {
        return 0;
    }
    // 用于存储生成的哈夫曼编码，键为字符，值为对应的哈夫曼编码字符串。
    unordered_map<char, string> huffmanCodes;
    // 调用函数生成哈夫曼编码，从根节点开始，初始编码字符串为空。
    generateHuffmanCodes(root, "", huffmanCodes);
    // 输出哈夫曼编码
    for (auto& code : huffmanCodes) {
        cout << code.first << " : " << code.second << endl;
    }
    // 释放哈夫曼树占用的内存空间，避免内存泄漏，调用辅助函数进行后序遍历释放。
    freeHuffmanTree(root);
    return 0;
}
image.gif

整体结构说明：

       整个代码主要实现了构建哈夫曼树以及基于构建好的哈夫曼树生成相应字符的哈夫曼编码的功能。代码分为几个主要部分，包括定义哈夫曼树节点结构体、实现用于优先队列的比较函数、构建哈夫曼树的函数、生成哈夫曼编码的函数以及主函数进行测试和内存释放操作等。

 

各函数详细解释：

  1. buildHuffmanTree 函数：
  • 输入节点入队：首先创建了一个 std::priority_queue 类型的优先队列 pq，并将输入的所有节点指针通过循环依次放入队列中。添加了对输入节点向量为空情况的简单错误处理，如果为空则打印提示信息并返回 nullptr，避免后续出现错误操作。
  • 循环构建树：在 while 循环中，只要优先队列中节点数量大于 1，就不断进行以下操作。每次先取出两个权重最小的节点（通过两次调用 pq.top() 并接着 pq.pop() 实现），这两个节点将作为新生成节点的左右子节点。然后创建一个新的父节点，其权重设置为取出的两个子节点权重之和，并且将刚才取出的两个节点分别赋值给新父节点的左右子节点指针。最后把这个新创建的父节点再放入优先队列中，参与后续的合并操作。这样不断合并节点，树的层次结构逐渐形成，直到队列中只剩下一个节点，这个节点就是整个哈夫曼树的根节点，代表了所有节点合并后的最终结果，通过它可以访问到整棵哈夫曼树的各个部分。
  • 返回根节点：最后返回构建好的哈夫曼树的根节点指针，如果输入的节点向量为空，这里返回的是之前已经处理的 nullptr。
  1. generateHuffmanCodes 函数：
  • 递归边界处理：首先判断当前传入的节点指针是否为 nullptr，如果是则直接返回，这是递归调用的边界条件，用于终止递归过程，避免无限递归。
  • 记录字符编码：当节点的数据成员不为空字符（'\0'）时，说明该节点代表一个实际的字符（非中间合并节点），此时将当前已经生成的编码字符串（通过递归过程中不断累加 0 或 1 形成）赋值给该字符对应的映射项，也就是记录下这个字符的哈夫曼编码到 huffmanCodes 无序映射中。
  • 递归遍历子树：接着分别递归遍历当前节点的左子树和右子树，在遍历左子树时，将当前编码字符串添加 0 后继续递归调用该函数；遍历右子树时，将当前编码字符串添加 1 后继续递归调用。通过这样的递归方式，能够遍历整棵哈夫曼树，为每个叶子节点（代表字符的节点）生成对应的哈夫曼编码。
  1. freeHuffmanTree 函数：
  • 这是一个用于释放哈夫曼树内存空间的辅助函数，采用后序遍历的方式进行递归释放。先判断根节点指针是否为 nullptr，如果是则直接返回，不需要进行释放操作。然后递归调用自身先释放左子树的内存，再释放右子树的内存，最后释放根节点的内存（通过 delete 操作符），确保整个哈夫曼树所占用的内存都能正确回收，避免内存泄漏问题，因为在构建哈夫曼树过程中使用了动态分配内存（new 操作符）来创建节点。
  1. main 函数：
  • 构建测试数据：在主函数中，首先模拟创建了一个包含几个节点的向量，这些节点的权重和对应的数据（字符）是手动设定的，仅用于简单展示构建哈夫曼树和生成编码的流程。实际应用中，这些节点通常是根据文本中字符出现的频率统计等操作来生成的。
  • 构建哈夫曼树并处理错误：调用 buildHuffmanTree 函数构建哈夫曼树，获取根节点指针后，对返回的指针进行判断，如果为 nullptr，说明构建树过程出现问题（比如输入节点为空等情况），则直接结束程序。
  • 生成并输出编码：创建一个 unordered_map 用于存储生成的哈夫曼编码，然后调用 generateHuffmanCodes 函数从根节点开始，初始编码字符串为空的情况下生成哈夫曼编码，并通过循环遍历 huffmanCodes 无序映射来输出每个字符及其对应的哈夫曼编码。
  • 释放内存：最后调用 freeHuffmanTree 函数来释放哈夫曼树所占用的内存空间，保证程序的内存管理正确，避免出现内存泄漏等问题。

测试说明

平台会对你编写的代码进行测试：

测试输入：(用户分别输入所列单词的频度）

1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123
image.gif

预期输出：

哈夫曼编码:
The:01
of:101
a:001
to:000
and:1110
in:1101
that:11110
he:11001
is:11000
at:10011
on:10010
for:10001
His:10000
are:111111
be:111110
image.gif

开始你的任务吧，祝你成功！

通关代码：

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct HuffmanNode{
    int weight;
    string word;
    HuffmanNode *left,*right;
    HuffmanNode(int weight,string word):weight(weight),word(word),left(nullptr),right(nullptr){}
};
struct Compare{
    bool operator()(HuffmanNode *l,HuffmanNode *r){
        if(l->weight == r->weight){
            return l->word < r->word;
        }
        return l->weight > r->weight;
    }
};
void generateHuffmanCode(HuffmanNode *root,string str,unordered_map<string,string> & huffmanCodes){
    if(!root)
    return;
    if(!root->word.empty()){
        huffmanCodes[root->word] = str;
    }
    generateHuffmanCode(root->left,str + "0",huffmanCodes);
    generateHuffmanCode(root->right,str + "1",huffmanCodes);
}
double calculateAverageSearchLength(HuffmanNode *root,int depth = 0){
    if(!root)
    return 0;
    if(!root->word.empty())
    return depth * root->weight;
    return calculateAverageSearchLength(root->left,depth + 1) + calculateAverageSearchLength(root ->right,depth + 1);
}
int main(){
    vector<string>words = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
    vector<int> weights(words.size());
    priority_queue<HuffmanNode *,vector<HuffmanNode *>,Compare> minHeap;
    for(int i = 0;i < words.size();++i){
        cin >> weights[i];
        minHeap.push(new HuffmanNode(weights[i],words[i]));
    }
    while (minHeap.size() > 1){
        HuffmanNode *left = minHeap.top();
        minHeap.pop();
        HuffmanNode *right =minHeap.top();
        minHeap.pop();
        HuffmanNode *top = new
HuffmanNode(left->weight + right -> weight,"");
        top->left =left;
        top->right = right;
        minHeap.push(top);
    }
    HuffmanNode *root = minHeap.top();
    unordered_map<string,string> huffmanCodes;
    generateHuffmanCode(root,"",huffmanCodes);
    cout <<"哈夫曼编码:\n";
    for(const string &word : words){
        cout <<word <<":"<<huffmanCodes[word]<<endl;
    }
    while(!minHeap.empty()){
        delete minHeap.top();
        minHeap.pop();
    }
    delete root;
    return 0;
}

image.gif

测试结果：

image.gif

image.gif

文章标签：
C++
存储
关键词：
C++实践
C++实践教学习题
C++树教学
数据结构树
数据结构教学
RossyYan
目录
相关文章
RossyYan
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
139 77
RossyYan
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
声明一个简单的Computer类，含有数据成员芯片（cpu）、内存（ram）、光驱（cdrom）等等，以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制，用于保护类的数据不被外部随意修改。根据提示，在右侧编辑器补充代码，平台会对你编写的代码进行测试。成员可以在派生类（继承该类的子类）中访问。成员，在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务，你需要掌握。
RossyYan
68 19
RossyYan
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
任务描述 本关任务：编写一个程序，利用Dijkstra算法，实现带权有向图的最短路径。 相关知识 为了完成本关任务，你需要掌握：Dijkst本关任务：编写一个程序，利用Dijkstra算法，实现带权有向图的最短路径。为了完成本关任务，你需要掌握：Dijkstra算法。带权有向图:该图对应的二维数组如下所示：Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下：(1)初始时,S只包含源点,即S={v},v的距离为0。
RossyYan
53 15
RossyYan
|
1月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
42 10
ephemerals__
|
3月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
322 9
那年春天
|
3月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
50 1
RossyYan
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
42 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
45 9
RossyYan
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
36 7
龙大吉
|
3月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
94 5