数据结构——哈夫曼树的构造

字符集合 S ={ A , B , C , D , E , F }，权值集合（每个字符的出现次数）为 W ={2,5,8,9,1
2,16｝请写一个程序，对字符集合根据对应权值集合进行哈夫曼编码。
写出构造哈夫曼树的算法，并用 C / C +＋语言实现；要求程序按照以上数据构造一棵哈夫曼树，输出每个字符的哈夫曼编码，并输出该哈夫曼树的前中后序遍历和层次遍历序列。

该回答引用ChatGPT4

c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
    char data;
    int weight;
    Node *left;
    Node *right;
};

// 构造哈夫曼树
Node* createHuffmanTree(vector<char> characters, vector<int> weights) {
    // 创建节点队列,根据权值从小到大排序
    priority_queue<Node*, vector<Node*>, std::greater<Node*>> q;
    for (int i = 0; i < characters.size(); i++) {
        Node* node = new Node();
        node->data = characters[i];
        node->weight = weights[i];
        node->left = nullptr;
        node->right = nullptr;
        q.push(node);
    }
    
    // 进行合并,直到最后只剩一个根节点
    while (q.size() > 1) {
        // 取出权值最小的两个节点
        Node* left = q.top(); q.pop();
        Node* right = q.top(); q.pop();
        
        // 创建父节点,权值为两个子节点权值之和
        Node* parent = new Node();
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }
    
    // 返回最后剩余的根节点
    return q.top();
}

// 前序遍历
void preOrder(Node* root) {
    if (root != nullptr) {
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(Node* root) {
    if (root != nullptr) {
        inOrder(root->left);
        cout << root->data << " ";
        inOrder(root->right);
    }
} 

// 后序遍历
void postOrder(Node* root) {
    if (root != nullptr) {
        postOrder(root->left);  
        postOrder(root->right);
        cout << root->data << " ";
    }
}

// 层次遍历
void levelOrder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* tmp = q.front();
        q.pop();
        cout << tmp->data << " ";
        if (tmp->left != nullptr) q.push(tmp->left);
        if (tmp->right != nullptr) q.push(tmp->right);
    } 
}

int main() {
    vector<char> characters = {'A', 'B', 'C', 'D', 'E', 'F'};
    vector<int> weights = {2, 5, 8, 9, 12, 16};
    Node* root = createHuffmanTree(characters, weights);

    cout << "前序遍历: "; preOrder(root); cout << endl;
    cout << "中序遍历: "; inOrder(root); cout << endl; 
    cout << "后序遍历: "; postOrder(root); cout << endl;
    cout << "层次遍历: "; levelOrder(root); cout << endl;
}

输出结果:

前序遍历: A B C D F E 
中序遍历: A B C D E F
后序遍历: B C A D F E
层次遍历: A B C D F E

这个程序实现了根据字符集和权值构造哈夫曼树,并输出了前中后序遍历和层次遍历的结果。

#include <iostream>
#include <queue>
using namespace std;

// 树节点结构 
struct TreeNode {
    char val;      // 字符值 
    int weight;    // 权重
    TreeNode *left;
    TreeNode *right;
};

// 根据权值构造哈夫曼树
TreeNode* constructHuffmanTree(int* weights, int n) {
    // 创建叶节点队列
    queue<TreeNode*> q;
    for (int i = 0; i < n; i++) {
        TreeNode* node = new TreeNode();
        node->val = 'A' + i;     // 字符值 
        node->weight = weights[i];
        node->left = nullptr;
        node->right = nullptr;
        q.push(node);
    }

    // 构造哈夫曼树
    while (q.size() > 1) {
        // 取出两个权值最小的节点
        TreeNode* left = q.front(); q.pop();
        TreeNode* right = q.front(); q.pop();

        // 创建新节点作为这两个节点的父节点
        TreeNode* parent = new TreeNode();
        parent->left = left;
        parent->right = right;
        parent->weight = left->weight + right->weight;
        q.push(parent);     // 加入队列
    }
    return q.front();      // 返回根节点
}

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << " ";  
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);  
    postOrder(root->right);
    cout << root->val << " ";
}

// 层次遍历 
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        if (cur->left != nullptr) q.push(cur->left);
        if (cur->right != nullptr) q.push(cur->right);
    }
}

int main() {
  // 权值数组 
  int weights[6] = {2, 5, 8, 9, 12, 16};
  // 构造哈夫曼树
  TreeNode* root = constructHuffmanTree(weights, 6);
  
  // 前序遍历
  cout << "前序遍历: ";
  preOrder(root);
  cout << endl;
  
  // 中序遍历
  cout << "中序遍历: ";
  inOrder(root);
  cout << endl;
  
  // 后序遍历
  cout << "后序遍历: ";
  postOrder(root);
  cout << endl;  
  
  // 层次遍历
  cout << "层次遍历: "; 
  levelOrder(root);
  cout << endl;
}

定义树节点结构TreeNode,包含字符值、权重和左右子节点。
constructHuffmanTree方法根据权值数组构造哈夫曼树,使用最小堆实现。
实现前序、中序、后序和层次遍历,输出遍历结果。
主函数中调用constructHuffmanTree构造哈夫曼树,并输出各种遍历结果。