Input: a pointer to the decoding tree root z & received Huffman encoded binary string i • Output: Huffman decoded string

以下是使用C++实现的示例代码：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

// 定义Huffman树节点结构体
struct Node {
    char c; // 节点代表的字符
    int freq; // 节点对应的频率
    Node* left; // 左子节点
    Node* right; // 右子节点
    // 构造函数
    Node(char _c, int _freq) : c(_c), freq(_freq), left(nullptr), right(nullptr) {}
    Node(int _freq) : freq(_freq), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于构建小根堆
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建Huffman树
Node* buildHuffmanTree(const unordered_map<char, int>& freq) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto p : freq) {
        pq.push(new Node(p.first, p.second));
    }
    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();
}

// 从根节点按照编码字符串i往下遍历Huffman树，返回叶子节点对应的字符
char decode(Node* root, string& i) {
    Node* cur = root;
    for (char c : i) {
        if (c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
    }
    return cur->c;
}

// Huffman解码函数
string huffmanDecode(Node* root, string& i) {
    string res;
    while (!i.empty()) {
        res.push_back(decode(root, i));
    }
    return res;
}

int main() {
    // 给定Huffman编码字符串i和字符频率freq
    string i = "001101110010011010";
    unordered_map<char, int> freq{{'a', 2}, {'b', 3}, {'c', 4}, {'d', 5}};

    // 构建Huffman树
    Node* root = buildHuffmanTree(freq);

    // Huffman解码
    string res = huffmanDecode(root, i);
    cout << res << endl; // 输出"bccdd"
    return 0;
}

以上代码中，`buildHuffmanTree()`函数用于构建Huffman树，`decode()`函数用于从根节点按照编码字符串i往下遍历Huffman树，返回叶子节点对应的字符，`huffmanDecode()`函数用于对整个编码字符串进行解码。程序输出结果为"bccdd"。