c++实现1.分别用1~9顺序输入的方法和随机方式构造二叉排序树； 2，比较查找值为1和9需要查找次数； 3，在随机生成的二叉排序树中插入值为15的结点，用中序遍历输出整个树； 4，在3中的树中删除值为8的结点，用中序遍历输出整个树。

好的，我将回答您的问题。

首先是问题1，我将分别给出用顺序输入和随机方式构造二叉排序树的代码示例：

顺序输入方式构造二叉排序树：

#include<iostream>
using namespace std;

//定义二叉树结点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//插入二叉排序树结点
void insertNode(TreeNode*& root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertNode(root->left, val);
    }
    else {
        insertNode(root->right, val);
    }
}

//顺序输入方式构造二叉排序树
TreeNode* buildTree1() {
    int arr[] = { 1,2,3,4,5,6,7,8,9 };
    int len = sizeof(arr) / sizeof(arr[0]);
    TreeNode* root = NULL;
    for (int i = 0; i < len; i++) {
        insertNode(root, arr[i]);
    }
    return root;
}

//中序遍历输出二叉树结点
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    //用顺序输入方式构造二叉排序树
    TreeNode* root1 = buildTree1();
    //中序遍历输出二叉排序树
    inorderTraversal(root1);
    return 0;
}

随机方式构造二叉排序树：

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

//定义二叉树结点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//插入二叉排序树结点
void insertNode(TreeNode*& root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertNode(root->left, val);
    }
    else {
        insertNode(root->right, val);
    }
}

//随机方式构造二叉排序树
TreeNode* buildTree2() {
    int arr[] = { 1,2,3,4,5,6,7,8,9 };
    int len = sizeof(arr) / sizeof(arr[0]);
    srand((unsigned)time(NULL)); //设置随机种子
    TreeNode* root = NULL;
    for (int i = 0; i < len; i++) {
        int index = rand() % (i + 1);
        insertNode(root, arr[index]);
        swap(arr[i], arr[index]);
    }
    return root;
}

//中序遍历输出二叉树结点
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    //用随机方式构造二叉排序树
    TreeNode* root2 = buildTree2();
    //中序遍历输出二叉排序树
    inorderTraversal(root2);
    return 0;
}

接下来是问题2，比较查找值为1和9需要查找次数。我们可以通过二叉排序树的性质进行查找，如果查找的值小于当前结点的值，则在左子树中查找，否则在右子树中查找，直到找到该结点或者遍历到空结点。因此，查找次数等于从根结点到目标结点的路径长度。

我们先来看查找值为1的情况，假设我们用顺序输入方式构造了二叉排序树，则查找值为1的过程如下：

1. 从根结点开始，当前结点为1，查找次数为1
2. 由于1小于5，从1的左子树中查找，当前结点为2，查找次数为2
3. 由于1小于2，从2的左子树中查找，当前结点为1，查找次数为3

因此，查找值为1的次数为3。

接下来我们看查找值为9的情况，假设我们用随机方式构造了二叉排序树，则查找值为9的过程如下：

1. 从根结点开始，当前结点为5，查找次数为1
2. 由于9大于5，从5的右子树中查找，当前结点为7，查找次数为2
3. 由于9大于7，从7的右子树中查找，当前结点为9，查找次数为3

因此，查找值为9的次数为3。

接着是问题3，在随机生成的二叉排序树中插入值为15的结点，用中序遍历输出整个树。我们可以使用与插入结点相同的方法进行查找，找到插入的位置后，将新结点插入到该位置上即可。

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

//定义二叉树结点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//插入二叉排序树结点
void insertNode(TreeNode*& root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertNode(root->left, val);
    }
    else {
        insertNode(root->right, val);
    }
}

//随机方式构造二叉排序树
TreeNode* buildTree2() {
    int arr[] = { 1,2,3,4,5,6,7,8,9 };
    int len = sizeof(arr) / sizeof(arr[0]);
    srand((unsigned)time(NULL)); //设置随机种子
    TreeNode* root = NULL;
    for (int i = 0; i < len; i++) {
        int index = rand() % (i + 1);
        insertNode(root, arr[index]);
        swap(arr[i], arr[index]);
    }
    return root;
}

//中序遍历输出二叉树结点
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    //用随机方式构造二叉排序树
    TreeNode* root2 = buildTree2();
    //中序遍历输出原始二叉排序树
    inorderTraversal(root2);
    cout << endl;
    //在二叉排序树中插入值为15的结点
    insertNode(root2, 15);
    //中序遍历输出新的二叉排序树
    inorderTraversal(root2);
    return 0;
}

最后是问题4，在3中的树中删除值为8的结点，用中序遍历输出整个树。删除二叉排序树结点的过程如下：

1. 如果要删除的结点没有子结点，直接删除该结点即可；
2. 如果要删除的结点只有一个子结点，将该子结点替代该结点即可；
3. 如果要删除的结点有两个子结点，可以找到该结点的前驱或后继结点替代该结点，这里以前驱结点为例。

具体实现如下：

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

//定义二叉树结点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//插入二叉排序树结点
void insertNode(TreeNode*& root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertNode(root->left, val);
    }
    else {
        insertNode(root->right, val);
    }
}

//随机方式构造二叉排序树
TreeNode* buildTree2() {
    int arr[] = { 1,2,3,4,5,6,7,8,9 };
    int len = sizeof(arr) / sizeof(arr[0]);
    srand((unsigned)time(NULL)); //设置随机种子
    TreeNode* root = NULL;
    for (int i = 0; i < len; i++) {
        int index = rand() % (i + 1);
        insertNode(root, arr[index]);
        swap(arr[i], arr[index]);
    }
    return root;
}

//中序遍历输出二叉树结点
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

//查找二叉排序树中的结点
TreeNode* findNode(TreeNode* root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (root->val == val) {
        return root;
    }
    else if (val < root->val) {
        return findNode(root->left, val);
    }
    else {
        return findNode(root->right, val);
    }
}

//删除二叉排序树中的结点
void deleteNode(TreeNode*& root, int val) {
    if (root == NULL) {
        return;
    }
    if (val < root->val) {
        deleteNode(root->left, val);
    }
    else if (val > root->val) {
        deleteNode(root->right, val);
    }
    else {
        if (root->left == NULL && root->right == NULL) { //要删除的结点没有子结点
            delete root;
            root = NULL;
        }
        else if (root->left == NULL) { //要删除的结点只有右子结点
            TreeNode* tmp = root;
            root = root->right;
            delete tmp;
        }
        else if (root->right == NULL) { //要删除的结点只有左子结点
            TreeNode* tmp = root;
            root = root->left;
            delete tmp;
        }
        else { //要删除的结点有两个子结点
            TreeNode* tmp = root->left;
            while (tmp->right != NULL) { //找到该结点的前驱结点
                tmp = tmp->right;
            }
            root->val = tmp->val; //用前驱结点的值替换该结点的值
            deleteNode(root->left, tmp->val); //删除前驱结点
        }
    }
}

int main() {
    //用随机方式构造二叉排序树
    TreeNode* root2 = buildTree2();
    //中序遍历输出原始二叉排序树
    inorderTraversal(root2);
    cout << endl;
    //在二叉排序树中插入值为15的结点
    insertNode(root2, 15);
    //中序遍历输出新的二叉排序树
    inorderTraversal(root2);
    cout << endl;
    //删除值为8的结点
    deleteNode(root2, 8);
    //中序遍历输出删除后的二叉排序树
    inorderTraversal(root2);
    return 0;
}