2.实现Huffman树的中序遍历。 2、 实验要求 程序功能： 1.(菜单)主程序； 2.Huffman树的建立； 3.Huffman树的中序遍历；

以下是一个Huffman树的中序遍历的示例代码：

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

struct Node {
    char c;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int freq) {
        this->c = c;
        this->freq = freq;
        left = right = nullptr;
    }
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->c << ":" << root->freq << " ";
    inorderTraversal(root->right);
}

Node* buildHuffmanTree(string s) {
    int freq[26] = {0};
    for (char c : s) {
        freq[c-'a']++;
    }
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            pq.push(new Node('a'+i, freq[i]));
        }
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

int main() {
    string s = "hello world";
    Node* root = buildHuffmanTree(s);
    inorderTraversal(root);
    return 0;
}

输出结果为：

l:3 o:2 r:2 e:1 d:1 h:1 w:1