c语言实现+二叉排序树

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。因此，BST的中序遍历结果是一个有序序列。BST的查找、插入、删除操作的时间复杂度均为O(log n)。

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

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

// 二叉排序树结点结构体
typedef struct BSTNode {
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

// 插入结点
BSTNode* insert(BSTNode *root, int data) {
    if (root == NULL) {
        root = (BSTNode*)malloc(sizeof(BSTNode));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
    } else if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// 查找结点
BSTNode* search(BSTNode *root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    } else if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

// 删除结点
BSTNode* delete(BSTNode *root, int data) {
    if (root == NULL) {
        return root;
    } else if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        // 找到要删除的结点
        if (root->left == NULL) {
            BSTNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            BSTNode *temp = root->left;
            free(root);
            return temp;
        }
        // 找到右子树的最小结点
        BSTNode *temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        // 用右子树的最小结点替换要删除的结点
        root->data = temp->data;
        root->right = delete(root->right, temp->data);
    }
    return root;
}

// 中序遍历
void inorder(BSTNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    BSTNode *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal of the given tree: ");
    inorder(root);

    printf("\nDelete 20\n");
    root = delete(root, 20);
    printf("Inorder traversal of the modified tree: ");
    inorder(root);

    printf("\nDelete 30\n");
    root = delete(root, 30);
    printf("Inorder traversal of the modified tree: ");
    inorder(root);

    printf("\nDelete 50\n");
    root = delete(root, 50);
    printf("Inorder traversal of the modified tree: ");
    inorder(root);

    return 0;
}