本题要求实现二叉排序树的查找操作。 对于二叉排序树，如下图： 二叉排序树.png 输入样例： 4 1 8 0 9 输出样例： 1 is found 8 is found 0 is not found 9 is not found 其中BSTree结构定义如下： typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree;

以下是二叉排序树查找操作的代码实现：

#include <iostream>
using namespace std;

typedef int ElemType;
typedef struct BSTNode {
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

// 二叉排序树的查找操作，返回查找到的结点指针
BSTree SearchBST(BSTree T, ElemType key) {
    if (T == NULL || T->data == key) { // 根结点为空或等于key，直接返回
        return T;
    } else if (key < T->data) { // key小于根结点，递归查找左子树
        return SearchBST(T->lchild, key); 
    } else { // key大于根结点，递归查找右子树
        return SearchBST(T->rchild, key);
    }
}

int main() {
    BSTree T = NULL; // 初始化为空树
    int n, key;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> key;
        // 将key插入二叉排序树中
        BSTree p = T, pre = NULL; // p指向待插入结点，pre指向p的父结点
        while (p != NULL) {
            pre = p;
            if (key < p->data) {
                p = p->lchild;
            } else {
                p = p->rchild;
            }
        }
        p = new BSTNode;
        p->data = key;
        p->lchild = p->rchild = NULL;
        if (pre == NULL) { // 空树，新结点作为根结点
            T = p;
        } else if (key < pre->data) { // 新结点作为左孩子
            pre->lchild = p;
        } else { // 新结点作为右孩子
            pre->rchild = p;
        }
    }
    // 依次查找每个元素
    while (cin >> key) {
        BSTree p = SearchBST(T, key);
        if (p == NULL) {
            cout << key << " is not found" << endl;
        } else {
            cout << key << " is found" << endl;
        }
    }
    return 0;
}

对于每个需要查找的元素，我们先用SearchBST函数在二叉排序树中查找，返回查找到的结点指针。如果返回的指针为空，则说明该元素在二叉排序树中不存在，输出“not found”；否则输出“found”即可。