设计一个二叉链表存储的二叉树； （2）编写二叉树的创建、显示的程序； （3）编写二叉树先序、中序、后序、层次遍历的应用程序； （4）编写求二叉树叶子结点数、总结点数和深度的应用程序； （5）设计一个选择式菜单，以菜单方式选择上述操作。

1. 二叉链表存储的二叉树定义：

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

2. 二叉树的创建和显示程序：

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr; // -1 表示为空节点
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void printTree(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

3. 二叉树的遍历程序：

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

void levelorder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) continue;
        cout << node->val << " ";
        q.push(node->left);
        q.push(node->right);
    }
}

4. 求二叉树叶子结点数、总结点数和深度的程序：

int countLeaf(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaf(root->left) + countLeaf(root->right);
}

int countNode(TreeNode* root) {
    if (root == nullptr) return 0;
    return countNode(root->left) + countNode(root->right) + 1;
}

int depth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(depth(root->left), depth(root->right)) + 1;
}

5. 选择式菜单程序：

int main() {
    TreeNode* root = nullptr;
    while (true) {
        cout << "1. 创建二叉树\n";
        cout << "2. 显示二叉树\n";
        cout << "3. 先序遍历\n";
        cout << "4. 中序遍历\n";
        cout << "5. 后序遍历\n";
        cout << "6. 层次遍历\n";
        cout << "7. 求叶子结点数\n";
        cout << "8. 求总结点数\n";
        cout << "9. 求深度\n";
        cout << "0. 退出程序\n";
        cout << "请选择操作：";
        int choice;
        cin >> choice;
        switch (choice) {
            case 1:
                root = createTree();
                break;
            case 2:
                printTree(root);
                cout << endl;
                break;
            case 3:
                preorder(root);
                cout << endl;
                break;
            case 4:
                inorder(root);
                cout << endl;
                break;
            case 5:
                postorder(root);
                cout << endl;
                break;
            case 6:
                levelorder(root);
                cout << endl;
                break;
            case 7:
                cout << countLeaf(root) << endl;
                break;
            case 8:
                cout << countNode(root) << endl;
                break;
            case 9:
                cout << depth(root) << endl;
                break;
            case 0:
                return 0;
            default:
                cout << "输入错误，请重新选择。\n";
        }
    }
}