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

Rossy Yan

修改于 2024-12-26 10:26:48

6510

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

任务描述

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

相关知识

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

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

如何构建哈夫曼树

1. 定义节点结构体

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

左子节点指针。
右子节点指针。
节点的权重（通常是字符出现的频率）。
可能还包含节点表示的数据（例如字符）。

struct HuffmanNode {
    int weight;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;

    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. 构建哈夫曼树

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

将所有节点放入优先队列。
每次从优先队列中取出两个权重最小的节点，创建一个新的父节点，其权重为这两个节点权重之和，并将这两个节点作为新父节点的左右子节点，然后将新父节点放入优先队列。
重复步骤 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;
}

节点结构体部分:

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);
}

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

#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;
}

整体结构说明：

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

各函数详细解释：

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

测试说明

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

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

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

预期输出：

哈夫曼编码:
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

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

通关代码：

#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;
}

测试结果：

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除

实践