请用C++实现（1）定义一个二叉树的二叉链表。 （2）编写二叉树的先序和中序遍历算法。 （3）编写构造哈夫曼树和求哈夫曼编码的算法。 （4）设计菜单，以选择菜单方式进行操作，并实现上述算法。

为了方便，我将分别回答每个问题。

1. 定义一个二叉树的二叉链表

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

typedef TreeNode* Tree;

2. 编写二叉树的先序和中序遍历算法

void preorderTraversal(Tree root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(Tree root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

3. 编写构造哈夫曼树和求哈夫曼编码的算法

struct HuffmanTreeNode {
    int weight;
    int parent;
    int left;
    int right;
};

void createHuffmanTree(HuffmanTreeNode* nodes, int n) {
    for (int i = 0; i < 2 * n - 1; i++) {
        nodes[i].parent = -1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }
    for (int i = n; i < 2 * n - 1; i++) {
        int min1 = INT_MAX;
        int min2 = INT_MAX;
        int min1Idx = -1;
        int min2Idx = -1;
        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].weight < min1) {
                    min2 = min1;
                    min2Idx = min1Idx;
                    min1 = nodes[j].weight;
                    min1Idx = j;
                } else if (nodes[j].weight < min2) {
                    min2 = nodes[j].weight;
                    min2Idx = j;
                }
            }
        }
        nodes[min1Idx].parent = i;
        nodes[min2Idx].parent = i;
        nodes[i].left = min1Idx;
        nodes[i].right = min2Idx;
        nodes[i].weight = nodes[min1Idx].weight + nodes[min2Idx].weight;
    }
}

void encodeHuffman(HuffmanTreeNode* nodes, int n, string* codes) {
    for (int i = 0; i < n; i++) {
        int j = i;
        string code = "";
        while (nodes[j].parent != -1) {
            int parent = nodes[j].parent;
            if (nodes[parent].left == j) {
                code = "0" + code;
            } else {
                code = "1" + code;
            }
            j = parent;
        }
        codes[i] = code;
    }
}

4. 设计菜单，以选择菜单方式进行操作，并实现上述算法

int main() {
    cout << "1. 二叉树的先序和中序遍历" << endl;
    cout << "2. 构造哈夫曼树和求哈夫曼编码" << endl;
    int choice;
    cin >> choice;

    if (choice == 1) {
        // 构造二叉树
        Tree root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->left = new TreeNode(4);
        root->left->right = new TreeNode(5);
        root->right->left = new TreeNode(6);
        root->right->right = new TreeNode(7);

        // 先序遍历
        cout << "先序遍历：";
        preorderTraversal(root);
        cout << endl;

        // 中序遍历
        cout << "中序遍历：";
        inorderTraversal(root);
        cout << endl;
    } else if (choice == 2) {
        // 构造哈夫曼树
        int n = 5;
        HuffmanTreeNode nodes[2 * n - 1];
        nodes[0].weight = 5;
        nodes[1].weight = 29;
        nodes[2].weight = 7;
        nodes[3].weight = 8;
        nodes[4].weight = 14;
        createHuffmanTree(nodes, n);

        // 求哈夫曼编码
        string codes[n];
        encodeHuffman(nodes, n, codes);

        // 输出哈夫曼编码
        for (int i = 0; i < n; i++) {
            cout << "字符 " << i << " 的哈夫曼编码为 " << codes[i] << endl;
        }
    } else {
        cout << "无效选择" << endl;
    }

    return 0;
}