1 实验目的 （1）掌握查找的不同方法，并能用高级语言实现查找算法； （2）熟练掌握二叉排序树的构造和查找方法； 2 实验内容 设计一个算法读入一串整数，然后构造二叉排序树，进行查找。 3 实验步骤 （1）从空的二叉树开始，每输入一个节点数据，就建立一个新节点插入到当前已生成的二叉排序树中； （2）在二叉排序树中查找某一结点； （3）删除任一指定的结点 4 类型定义 typedef struct Node /*二叉排序树节点结构*/ { KeyType key ; /*关键字值*/ struct node *lchild, *rchild; /*左右指针*/ }BSTNode;

下面是一个关于实现算法读入一串整数，构造二叉排序树，并进行查找和删除的C语言程序，其中包含了给出的节点结构体类型定义：

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef int KeyType;
typedef struct Node {
    KeyType key;
    struct Node *lchild, *rchild;
} BSTNode;

BSTNode *createBST() {
    return NULL;
}

BSTNode *insertBST(BSTNode *root, KeyType key) {
    if (root == NULL) {
        BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
        newNode->key = key;
        newNode->lchild = newNode->rchild = NULL;
        return newNode;
    } else if (key < root->key) {
        root->lchild = insertBST(root->lchild, key);
    } else if (key > root->key) {
        root->rchild = insertBST(root->rchild, key);
    }
    return root;
}

BSTNode *searchBST(BSTNode *root, KeyType key) {
    if (root == NULL || root->key == key) {
        return root;
    } else if (key < root->key) {
        return searchBST(root->lchild, key);
    } else {
        return searchBST(root->rchild, key);
    }
}

BSTNode *findMin(BSTNode *root) {
    if (root == NULL) {
        return NULL;
    } else if (root->lchild == NULL) {
        return root;
    } else {
        return findMin(root->lchild);
    }
}

BSTNode *deleteBST(BSTNode *root, KeyType key) {
    if (root == NULL) {
        return NULL;
    } else if (key < root->key) {
        root->lchild = deleteBST(root->lchild, key);
    } else if (key > root->key) {
        root->rchild = deleteBST(root->rchild, key);
    } else if (root->lchild && root->rchild) {
        BSTNode *tmp = findMin(root->rchild);
        root->key = tmp->key;
        root->rchild = deleteBST(root->rchild, root->key);
    } else {
        BSTNode *tmp = root;
        if (root->lchild == NULL) {
            root = root->rchild;
        } else if (root->rchild == NULL) {
            root = root->lchild;
        }
        free(tmp);
    }
    return root;
}

void preOrder(BSTNode *root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

void inOrder(BSTNode *root) {
    if (root != NULL) {
        inOrder(root->lchild);
        printf("%d ", root->key);
        inOrder(root->rchild);
    }
}

void postOrder(BSTNode *root) {
    if (root != NULL) {
        postOrder(root->lchild);
        postOrder(root->rchild);
        printf("%d ", root->key);
    }
}

int main() {
    BSTNode *root = createBST();
    int n, i;
    KeyType key;
    printf("请输入数字个数：");
    scanf("%d", &n);
    printf("请输入数字：");
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        root = insertBST(root, key);
    }
    printf("前序遍历：");
    preOrder(root);
    printf("\n");
    printf("中序遍历：");
    inOrder(root);
    printf("\n");
    printf("后序遍历：");
    postOrder(root);
    printf("\n");
    printf("请输入要查找的数字：");
    scanf("%d", &key);
    BSTNode *p = searchBST(root, key);
    if (p != NULL) {
        printf("查找成功，数字%d存在于树中！\n", p->key);
    } else {
        printf("查找失败，数字%d不存在于树中！\n", key);
    }
    printf("请输入要删除的数字：");
    scanf("%d", &key);
    root = deleteBST(root, key);
    printf("删除后的中序遍历：");
    inOrder(root);
    printf("\n");
    return 0;
}

在这个程序中，我们首先定义了二叉排序树节点的结构体类型，包括关键字值和左右指针。然后，我们实现了创建二叉排序树、插入节点、查找节点、删除节点等操作。最后，我们采用前序、中序、后序遍历的方式输出二叉排序树中所有节点的关键字值，并给出了查找和删除的示例。

希望这个程序能够帮助您理解二叉排序树的构造和操作，如有任何问题和疑问，欢迎继续追问。