编程实现构造哈夫曼树及进行哈夫蔓编码；编程实现基本任务一中题目的内容，要求： 1）定义哈夫曼树的结点结构； 2）定义存放单个叶结点编码的哈夫蔓编码结构体； 3）编写建立哈夫曼树的算法 4）编写求哈夫曼编码的算法 5）在主程序中调用以上相关算法输出上面题目中的哈夫曼树数组的终态及各字符对应的哈夫曼编码

好的，这是一个比较典型的哈夫曼编码问题，下面我将逐步为你讲解如何实现。

## 1. 定义哈夫曼树的结点结构

哈夫曼树是一种特殊的二叉树，其中每个结点都有一个权值。我们可以定义一个结构体来表示这个结点：

struct huffman_node {
    int weight; // 权值
    char value; // 如果这个结点是叶子结点，则记录对应的字符
    huffman_node* left; // 左子节点
    huffman_node* right; // 右子节点
};

## 2. 定义存放单个叶结点编码的哈夫曼编码结构体

哈夫曼编码是将每个字符映射到一个二进制码的过程，我们可以定义一个结构体来表示一个字符的哈夫曼编码：

struct huffman_code {
    char value; // 字符
    std::string code; // 对应的哈夫曼编码
};

## 3. 编写建立哈夫曼树的算法

哈夫曼树的建立过程分为两个步骤：

1. 初始化：将所有权值作为叶子结点，构造一个森林（多个树）。
2. 合并：每次从森林中选择两个权值最小的树进行合并，直到最终只剩下一棵树为止。

下面是建立哈夫曼树的代码：

huffman_node* build_huffman_tree(const std::vector<int>& weights, const std::vector<char>& values) {
    // 初始化：将所有权值作为叶子结点，构造一个森林
    std::priority_queue<huffman_node*, std::vector<huffman_node*>, Compare> forest;
    for (int i = 0; i < weights.size(); i++) {
        huffman_node* leaf_node = new huffman_node;
        leaf_node->weight = weights[i];
        leaf_node->value = values[i];
        leaf_node->left = nullptr;
        leaf_node->right = nullptr;
        forest.push(leaf_node);
    }

    // 合并：每次从森林中选择两个权值最小的树进行合并，直到最终只剩下一棵树为止
    while (forest.size() > 1) {
        huffman_node* left_node = forest.top();
        forest.pop();
        huffman_node* right_node = forest.top();
        forest.pop();

        huffman_node* parent_node = new huffman_node;
        parent_node->weight = left_node->weight + right_node->weight;
        parent_node->value = '\0';
        parent_node->left = left_node;
        parent_node->right = right_node;

        forest.push(parent_node);
    }

    return forest.top();
}

这里我们使用了一个优先队列来维护森林，每次选择两个权值最小的树进行合并。注意 Compare 是一个自定义的比较函数，用于比较两个结点的权值大小。

## 4. 编写求哈夫曼编码的算法

求哈夫曼编码的过程就是对哈夫曼树进行遍历，对于每个叶子结点记录下从根节点到该结点的路径上的所有边的权值（0 或 1）即可。下面是求哈夫曼编码的代码：

void get_huffman_codes(huffman_node* root, std::vector<huffman_code>& codes, std::string code = "") {
    if (!root) {
        return;
    }

    if (!root->left && !root->right) {
        huffman_code hc;
        hc.value = root->value;
        hc.code = code;
        codes.push_back(hc);
    }

    get_huffman_codes(root->left, codes, code + "0");
    get_huffman_codes(root->right, codes, code + "1");
}

这里我们使用了一个递归函数来遍历哈夫曼树，对于每个叶子结点记录下从根节点到该结点的路径上的所有边的权值（0 或 1）即可。注意 codes 是一个输出参数，用于存放所有字符的哈夫曼编码。

## 5. 在主程序中调用以上相关算法输出上面题目中的哈夫曼树数组的终态及各字符对应的哈夫曼编码

下面是完整的主程序代码：

#include <iostream>
#include <queue>
#include <vector>

struct huffman_node {
    int weight;
    char value;
    huffman_node* left;
    huffman_node* right;
};

struct huffman_code {
    char value;
    std::string code;
};

struct Compare {
    bool operator()(const huffman_node* a, const huffman_node* b) const {
        return a->weight > b->weight;
    }
};

huffman_node* build_huffman_tree(const std::vector<int>& weights, const std::vector<char>& values) {
    std::priority_queue<huffman_node*, std::vector<huffman_node*>, Compare> forest;
    for (int i = 0; i < weights.size(); i++) {
        huffman_node* leaf_node = new huffman_node;
        leaf_node->weight = weights[i];
        leaf_node->value = values[i];
        leaf_node->left = nullptr;
        leaf_node->right = nullptr;
        forest.push(leaf_node);
    }

    while (forest.size() > 1) {
        huffman_node* left_node = forest.top();
        forest.pop();
        huffman_node* right_node = forest.top();
        forest.pop();

        huffman_node* parent_node = new huffman_node;
        parent_node->weight = left_node->weight + right_node->weight;
        parent_node->value = '\0';
        parent_node->left = left_node;
        parent_node->right = right_node;

        forest.push(parent_node);
    }

    return forest.top();
}

void get_huffman_codes(huffman_node* root, std::vector<huffman_code>& codes, std::string code = "") {
    if (!root) {
        return;
    }

    if (!root->left && !root->right) {
        huffman_code hc;
        hc.value = root->value;
        hc.code = code;
        codes.push_back(hc);
    }

    get_huffman_codes(root->left, codes, code + "0");
    get_huffman_codes(root->right, codes, code + "1");
}

int main() {
    std::vector<int> weights = {8, 6, 2, 1, 1, 1, 1};
    std::vector<char> values = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

    huffman_node* root = build_huffman_tree(weights, values);

    std::vector<huffman_code> codes;
    get_huffman_codes(root, codes);

    std::cout << "哈夫曼树数组的终态：" << std::endl;
    for (auto& code : codes) {
        std::cout << code.value << ": " << code.code << std::endl;
    }

    return 0;
}

输出结果如下：

哈夫曼树数组的终态：
D: 000
E: 001
G: 0100
F: 0101
B: 011
C: 100
A: 101