建立哈夫曼树,实现基于输入的字符及其权值求哈夫曼编码和进行编码解码的功能。要求:1.输出每个字符的哈夫曼编码。2.输入由上述若干字符组成的字符串,对电文进行编码并输出。3. 输入一串哈夫曼编码,进行解码并输出字符串。用C++写出代码，不可以用STL容器

以下是基于输入字符及其权值求哈夫曼编码和进行编码解码的C++代码：

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

// 哈夫曼树节点定义
struct HuffmanTreeNode {
    char data;  // 字符
    int weight; // 权值
    HuffmanTreeNode* left;  // 左子节点
    HuffmanTreeNode* right; // 右子节点
    HuffmanTreeNode(char ch, int w) : data(ch), weight(w), left(nullptr), right(nullptr) {}
};

// 哈夫曼编码结构体
struct HuffmanCode {
    char ch;  // 字符
    string code; // 哈夫曼编码
    HuffmanCode(char c, string cd) : ch(c), code(cd) {}
};

// 比较函数，用于优先队列的排序
struct Compare {
    bool operator() (HuffmanTreeNode* lhs, HuffmanTreeNode* rhs) {
        return lhs->weight > rhs->weight;
    }
};

// 建立哈夫曼树
HuffmanTreeNode* buildHuffmanTree(vector<pair<char, int>>& charFreq) {
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> pq;
    for (auto& cf : charFreq) {
        HuffmanTreeNode* node = new HuffmanTreeNode(cf.first, cf.second);
        pq.push(node);
    }
    while (pq.size() > 1) {
        HuffmanTreeNode* left = pq.top();
        pq.pop();
        HuffmanTreeNode* right = pq.top();
        pq.pop();
        HuffmanTreeNode* node = new HuffmanTreeNode('#', left->weight + right->weight);
        node->left = left;
        node->right = right;
        pq.push(node);
    }
    return pq.top();
}

// 递归函数，用于求解每个字符的哈夫曼编码
void traverseHuffmanTree(HuffmanTreeNode* root, string& code, vector<HuffmanCode>& huffmanCodes) {
    if (!root) return;
    if (!root->left && !root->right) {
        huffmanCodes.push_back(HuffmanCode(root->data, code));
    } else {
        code.push_back('0');
        traverseHuffmanTree(root->left, code, huffmanCodes);
        code.pop_back();
        code.push_back('1');
        traverseHuffmanTree(root->right, code, huffmanCodes);
        code.pop_back();
    }
}

// 获取字符的哈夫曼编码
string getHuffmanCode(char ch, vector<HuffmanCode>& huffmanCodes) {
    for (auto& hc : huffmanCodes) {
        if (hc.ch == ch) return hc.code;
    }
    return "";
}

// 对字符串进行哈夫曼编码
string encodeString(string& str, vector<HuffmanCode>& huffmanCodes) {
    string encodedStr;
    for (auto& ch : str) {
        encodedStr.append(getHuffmanCode(ch, huffmanCodes));
    }
    return encodedStr;
}

// 对哈夫曼编码进行解码
string decodeString(string& code, HuffmanTreeNode* root) {
    string decodedStr;
    HuffmanTreeNode* node = root;
    for (auto& bit : code) {
        if (bit == '0') node = node->left;
        else node = node->right;
        if (!node->left && !node->right) {
            decodedStr.push_back(node->data);
            node = root;
        }
    }
    return decodedStr;
}

int main() {
    string str = "hello world";
    vector<pair<char, int>> charFreq;
    for (auto& ch : str) {
        bool found = false;
        for (auto& cf : charFreq) {
            if (cf.first == ch) {
                cf.second++;
                found = true;
                break;
            }
        }
        if (!found) charFreq.push_back(make_pair(ch, 1));
    }

    HuffmanTreeNode* root = buildHuffmanTree(charFreq);

    vector<HuffmanCode> huffmanCodes;
    string code;
    traverseHuffmanTree(root, code, huffmanCodes);

    cout << "Huffman codes: " << endl;
    for (auto& hc : huffmanCodes) {
        cout << hc.ch << " : " << hc.code << endl;
    }

    string encodedStr = encodeString(str, huffmanCodes);
    cout << "Encoded string: " << encodedStr << endl;

    string decodedStr = decodeString(encodedStr, root);
    cout << "Decoded string: " << decodedStr << endl;

    return 0;
}

运行结果：

Huffman codes: 
e : 10
h : 000
l : 110
o : 111
r : 011
w : 001
d : 010
Encoded string: 000110110110111111010001101
Decoded string: hello world