根据关键字序列构造二叉排序树，二叉排序树删除结点操作例题

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点的值都大于左子树中所有节点的值，并小于右子树中所有节点的值。当我们根据一个关键字序列构建BST时，通常从根开始，每次都选择当前关键字作为新节点的位置，如果该值比根小，就将其插入到左子树；反之则插入到右子树。

删除二叉排序树中的节点也是一个关键操作，有三种情况需要考虑：
1. 删除的节点是叶子节点：直接移除即可。
2. 删除的节点只有一个子节点：将该子节点替换到删除的节点位置。
3. 删除的节点有两个子节点：找到其右子树中最小的节点（或左子树中最大的节点），替换删除节点的值，然后在原子树中删除这个临时节点。

例如，假设我们有关键字序列[50, 30, 70, 20, 40, 60]，我们可以按顺序构建如下BST：

      50
     /  \
   30    70
  / \   / \
20  40 60 null

删除节点40的步骤如下：
1. 找到40，在其左子树中有一个子节点20，所以我们用20替换40，同时删去原来的20节点。

      50
     /  \
   30    70
  /     / \
20    40 60

现在BST看起来像这样，已成功删除了40。

相关问题

假设关键字序列（24，53，45，45，12，24，90），试给出采用此关键字序列构造二叉排序树的过程

首先，选择序列的第一个元素24作为根节点，然后从序列中取下一个元素53与根节点比较，由于53大于24，所以将53作为根节点的右子节点。接下来，取下一个元素45，比较时发现45小于53，于是将它作为53的左子节点。再取下一个元素45，由于45等于53的左子节点，所以将它作为53的左子节点的右子节点。接着取下一个元素12，由于12小于24，所以将它作为24的左子节点。取下一个元素24时，发现24已经在树中存在，因此不需要再插入。最后取下一个元素90，由于90大于24，所以将它作为24的右子节点。构造完成的二叉排序树如下所示：

        24
       /  \
     12   53
         /  \
        45   90

1、对输入的一个任意的关键字序列构造一棵二叉排序树，并且可以将该二叉排序树输出，实现查找算法。 要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作： （1） 任意输入关键字序列，建立二叉排序树，并按照中序遍历输出该二叉树。 （2） 在建立的二叉排序树中查找比数字(输入值,例如36)，查找成功，则返回该数据，若未成功，则返回失败。 （3） 在有序表中查找数据元素(输入值,例如56)，查找成功，则返回该数据，若未成功，则返回失败。 用c语言实现的完整代码

以下是用 C 语言实现的二叉排序树代码：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    } else if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

Node* searchNode(Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    } else if (data < root->data) {
        return searchNode(root->left, data);
    } else if (data > root->data) {
        return searchNode(root->right, data);
    }
}

int main() {
    Node* root = NULL;
    int n, data, key;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    printf("Enter the elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insertNode(root, data);
    }

    printf("Inorder traversal of the binary search tree: ");
    inorderTraversal(root);
    printf("\n");

    printf("Enter the key to search: ");
    scanf("%d", &key);

    Node* result = searchNode(root, key);
    if (result == NULL) {
        printf("Search failed\n");
    } else {
        printf("Search successful, element found: %d\n", result->data);
    }

    return 0;
}

代码中，`Node` 结构体表示二叉排序树的节点，包括一个数据域和左右子树指针；`createNode` 函数用于创建节点；`insertNode` 函数用于向二叉排序树中插入节点；`inorderTraversal` 函数用于中序遍历二叉排序树并输出节点数据；`searchNode` 函数用于在二叉排序树中查找节点；`main` 函数用于读入输入值，调用以上函数实现建立二叉排序树、中序遍历输出该二叉树、在二叉排序树中查找数据元素等操作。