c语言数据结构二叉排序树

二叉排序树是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。这个特性使得二叉排序树非常适合用于查找操作。在C语言中，我们可以使用结构体来实现二叉排序树。

以下是C语言实现二叉排序树的基本操作：

1.定义二叉排序树的结构体

typedef struct BSTNode {
    int data; // 节点的值
    struct BSTNode *left; // 左子树
    struct BSTNode *right; // 右子树
} BSTNode, *BSTree;

2.创建二叉排序树

void createBSTree(BSTree *T, int data) {
    if (*T == NULL) {
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->data = data;
        (*T)->left = NULL;
        (*T)->right = NULL;
    } else if (data < (*T)->data) {
        createBSTree(&((*T)->left), data);
    } else if (data > (*T)->data) {
        createBSTree(&((*T)->right), data);
    }
}

3.查找二叉排序树中的节点

BSTree searchBSTree(BSTree T, int key) {
    if (T == NULL || T->data == key) {
        return T;
    } else if (key < T->data) {
        return searchBSTree(T->left, key);
    } else {
        return searchBSTree(T->right, key);
    }
}

4.插入节点到二叉排序树中

void insertBSTree(BSTree *T, int data) {
    if (*T == NULL) {
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->data = data;
        (*T)->left = NULL;
        (*T)->right = NULL;
    } else if (data < (*T)->data) {
        insertBSTree(&((*T)->left), data);
    } else if (data > (*T)->data) {
        insertBSTree(&((*T)->right), data);
    }
}

5.删除二叉排序树中的节点

void deleteBSTree(BSTree *T, int key) {
    if (*T == NULL) {
        return;
    }
    if (key < (*T)->data) {
        deleteBSTree(&((*T)->left), key);
    } else if (key > (*T)->data) {
        deleteBSTree(&((*T)->right), key);
    } else {
        if ((*T)->left == NULL && (*T)->right == NULL) {
            free(*T);
            *T = NULL;
        } else if ((*T)->left == NULL) {
            BSTree temp = *T;
            *T = (*T)->right;
            free(temp);
        } else if ((*T)->right == NULL) {
            BSTree temp = *T;
            *T = (*T)->left;
            free(temp);
        } else {
            BSTree temp = (*T)->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            (*T)->data = temp->data;
            deleteBSTree(&((*T)->right), temp->data);
        }
    }
}