1. 定义一个二叉树的二叉链表结构，以应用于下面各个算法中（5分）。 2. 输入一组正整数（假设输入0结束）建立一棵二叉排序树（30）。 3. 交换所建立的二叉排序树的左右子树，中序遍历该二叉树，查看其结果。（40分）。 4. 统计该二叉树的叶子节点个数

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

struct BinaryTreeNode {
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

2. 输入一组正整数（假设输入0结束）建立一棵二叉排序树

可以按照以下步骤建立二叉排序树：

1. 定义一个 `BinaryTreeNode* root` 指针，初始化为 `nullptr`。
2. 循环读入正整数，直到读入 0 为止。
3. 对于每个读入的正整数，执行以下操作：
- 如果 `root` 为 `nullptr`，则创建一个新节点并将其赋值给 `root`。
- 否则，从 `root` 开始搜索：
- 如果当前节点的值等于读入的正整数，则不做操作。
- 如果当前节点的值大于读入的正整数，则向左子树搜索：
- 如果左孩子为 `nullptr`，则创建一个新节点并将其赋值给左孩子。
- 否则，继续向左子树搜索。
- 如果当前节点的值小于读入的正整数，则向右子树搜索：
- 如果右孩子为 `nullptr`，则创建一个新节点并将其赋值给右孩子。
- 否则，继续向右子树搜索。
4. 建树完成后，返回 `root` 指针即可。

以下是建立二叉排序树的示例代码：

BinaryTreeNode* buildBST() {
    BinaryTreeNode* root = nullptr;
    int val;
    cin >> val;
    while (val != 0) {
        if (root == nullptr) {
            root = new BinaryTreeNode{val, nullptr, nullptr};
        } else {
            BinaryTreeNode* p = root;
            while (true) {
                if (val < p->val) {
                    if (p->left == nullptr) {
                        p->left = new BinaryTreeNode{val, nullptr, nullptr};
                        break;
                    } else {
                        p = p->left;
                    }
                } else if (val > p->val) {
                    if (p->right == nullptr) {
                        p->right = new BinaryTreeNode{val, nullptr, nullptr};
                        break;
                    } else {
                        p = p->right;
                    }
                } else {
                    break;
                }
            }
        }
        cin >> val;
    }
    return root;
}

3. 交换所建立的二叉排序树的左右子树，中序遍历该二叉树，查看其结果

可以按照以下步骤交换二叉排序树的左右子树，并进行中序遍历：

1. 如果二叉排序树为空，直接返回。
2. 否则，交换当前节点的左右子树，并分别递归交换左右子树。

以下是交换二叉排序树左右子树并中序遍历的示例代码：

void swapBST(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    swapBST(root->left);
    swapBST(root->right);
    BinaryTreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
}

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

// 在 main 函数中使用示例
BinaryTreeNode* root = buildBST();
swapBST(root);
inorderTraversal(root);

4. 统计该二叉树的叶子节点个数

可以按照以下步骤统计二叉树的叶子节点个数：

1. 如果二叉树为空，直接返回 0。
2. 如果二叉树只有一个节点，返回 1。
3. 否则，递归计算左子树和右子树的叶子节点个数，并将其相加。

以下是统计二叉树叶子节点个数的示例代码：

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

// 在 main 函数中使用示例
BinaryTreeNode* root = buildBST();
int numLeaves = countLeaves(root);
cout << "Number of leaves: " << numLeaves << endl;