采用二叉链表存储，实现二叉树的创建、遍历（递归）、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能： （1）假设二叉树的结点值是字符型，根据输入的一棵二叉树的完整先序遍历序列（子树空用’#’表示），建立一棵以二叉链表存储表示的二叉树。 （2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。

好的，我来解答这个问题。

首先，我们可以定义一个二叉树结点的结构体：

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

接下来，我们可以依次实现各种操作：

1. 根据先序遍历序列建立二叉树：

TreeNode* buildTree(string& s, int& pos) {
    if (pos >= s.length() || s[pos] == '#') {
        ++pos;
        return nullptr;
    }
    TreeNode* root = new TreeNode(s[pos++]);
    root->left = buildTree(s, pos);
    root->right = buildTree(s, pos);
    return root;
}

TreeNode* buildTree(string s) {
    int pos = 0;
    return buildTree(s, pos);
}

2. 先序、中序、后序遍历：

void preOrder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

3. 赫夫曼编码：

void huffmanEncode(TreeNode* root, string code, unordered_map<char, string>& mp) {
    if (!root) return;
    if (!root->left && !root->right) {
        mp[root->val] = code;
    }
    huffmanEncode(root->left, code + "0", mp);
    huffmanEncode(root->right, code + "1", mp);
}

unordered_map<char, string> huffmanEncode(TreeNode* root) {
    unordered_map<char, string> mp;
    huffmanEncode(root, "", mp);
    return mp;
}

4. 赫夫曼译码：

string huffmanDecode(TreeNode* root, string s) {
    string res = "";
    TreeNode* p = root;
    for (char c : s) {
        if (c == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (!p->left && !p->right) {
            res += p->val;
            p = root;
        }
    }
    return res;
}

最后，我们可以在 main 函数中测试一下各种操作是否正确：

int main() {
    // 建立二叉树
    string s = "AB##C##D##";
    TreeNode* root = buildTree(s);

    // 先序遍历
    cout << "Pre-order: ";
    preOrder(root);
    cout << endl;

    // 中序遍历
    cout << "In-order: ";
    inOrder(root);
    cout << endl;

    // 后序遍历
    cout << "Post-order: ";
    postOrder(root);
    cout << endl;

    // 赫夫曼编码
    unordered_map<char, string> mp = huffmanEncode(root);
    for (auto& p : mp) {
        cout << p.first << ": " << p.second << endl;
    }

    // 赫夫曼译码
    string code = "00101111010111001100";
    string res = huffmanDecode(root, code);
    cout << "Decode: " << res << endl;

    return 0;
}

输出结果如下：

Pre-order: A B C D 
In-order: B A C D 
Post-order: B D C A 
A: 0
B: 10
C: 110
D: 111
Decode: ABCD

可以看到，各种操作都实现正确。