二叉排序树删除结点C语言算法

二叉排序树删除结点的C语言算法如下：

// 定义二叉排序树结点
typedef struct BSTNode {
    int data;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 查找二叉排序树中值为key的结点
BSTree BST_Search(BSTree T, int key) {
    if (!T || T->data == key) {
        return T;
    } else if (key < T->data) {
        return BST_Search(T->lchild, key);
    } else {
        return BST_Search(T->rchild, key);
    }
}

// 删除二叉排序树中值为key的结点
int BST_Delete(BSTree *T, int key) {
    if (!(*T)) {
        return 0; // 未找到结点
    } else {
        if (key == (*T)->data) {
            BSTree p;
            if (!(*T)->lchild && !(*T)->rchild) { // 情况1：被删除结点为叶子结点
                free(*T);
                *T = NULL;
            } else if (!(*T)->lchild || !(*T)->rchild) { // 情况2：被删除结点只有一个孩子结点
                p = *T;
                *T = (*T)->lchild ? (*T)->lchild : (*T)->rchild;
                free(p);
            } else { // 情况3：被删除结点有两个孩子结点
                p = (*T)->lchild;
                while (p->rchild) {
                    p = p->rchild;
                }
                (*T)->data = p->data;
                BST_Delete(&(*T)->lchild, p->data);
            }
            return 1; // 删除成功
        } else if (key < (*T)->data) {
            return BST_Delete(&(*T)->lchild, key);
        } else {
            return BST_Delete(&(*T)->rchild, key);
        }
    }
}