设计一个二叉排序树的建立、查找、插入和删除等基本操作的演示程序。

Question

设计一个二叉排序树的建立、查找、插入和删除等基本操作的演示程序。
要求：用C语言实现各函数，函数内要有注释，对函数的调用方法，参数和返回值含义进行说明。

Answer 1

//定义一个结构体类型，表示二叉排序树的节点
typedef struct BiTNode {
    int data; //数据域，存储节点的值
    struct BiTNode * lchild, * rchild; //左右孩子指针
} BiTNode, * BiTree;

//定义一个函数，实现二叉排序树的查找操作
//参数：T表示要查找的二叉排序树，key表示要查找的值，f表示要查找节点的父节点（初始为NULL），p表示要返回的指向查找结果的指针
//返回值：如果查找成功，返回true，并将p指向查找到的节点；如果查找失败，返回false，并将p指向最后访问的节点
bool SearchBST(BiTree T, int key, BiTree f, BiTree * p) {
    //如果T为空，则查找失败，将p指向f，并返回false
    if (!T) {
        *p = f;
        return false;
    }
    //如果key等于T节点的值，则查找成功，将p指向T，并返回true
    else if (key == T->data) {
        *p = T;
        return true;
    }
    //如果key小于T节点的值，则在T的左子树中继续查找
    else if (key < T->data) {
        return SearchBST(T->lchild, key, T, p);
    }
    //如果key大于T节点的值，则在T的右子树中继续查找
    else {
        return SearchBST(T->rchild, key, T, p);
    }
}

//定义一个函数，实现二叉排序树的插入操作
//参数：T表示要插入的二叉排序树，e表示要插入的值
//返回值：如果插入成功，返回true；如果插入失败（已存在相同值），返回false
bool InsertBST(BiTree * T, int e) {
    BiTree p = NULL;
    //如果查找不成功，需要插入新节点
    if (!SearchBST(*T, e, NULL, &p)) {
        //创建一个新节点，存储e的值
        BiTree s = (BiTree)malloc(sizeof(BiTNode));
        s->data = e;
        s->lchild = s->rchild = NULL;
        //如果p为空，说明二叉排序树为空，将新节点作为根节点
        if (!p) {
            *T = s;
        }
        //如果p不为空，根据e的值判断是插入到p的左孩子还是右孩子
        else if (e < p->data) {
            p->lchild = s;
        }
        else {
            p->rchild = s;
        }
        return true; //插入成功
    }
    //如果查找成功，不需要插入，插入失败
    else {
        return false;
    }
}

//定义一个函数，实现二叉排序树的删除操作
//参数：T表示要删除的二叉排序树，key表示要删除的值
//返回值：如果删除成功，返回true；如果删除失败（不存在该值），返回false
bool DeleteBST(BiTree * T, int key) {
    //如果T为空，删除失败
    if (!*T) {
        return false;
    }
    //如果key等于T节点的值，删除该节点
    else if (key == (*T)->data) {
        return Delete(T);
    }
    //如果key小于T节点的值，在T的左子树中继续删除
    else if (key < (*T)->data) {
        return DeleteBST(&(*T)->lchild, key);
    }
    //如果key大于T节点的值，在T的右子树中继续删除
    else {
        return DeleteBST(&(*T)->rchild, key);
    }
}

//定义一个辅助函数，用于删除二叉排序树中的某个节点
//参数：p表示要删除的节点的指针
//返回值：如果删除成功，返回true；如果删除失败，返回false
bool Delete(BiTree * p) {
    BiTree q, s;
    //如果p节点的右子树为空，用左子树代替整个子树
    if (!(*p)->rchild) {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    //如果p节点的左子树为空，用右子树代替整个子树
    else if (!(*p)->lchild) {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    //如果p节点的左右子树都不为空，在p节点的左子树中找到最右下的节点s（即左子树中最大的节点），用s代替p，并在左子树中删除s
    else {
        q = *p;
        s = (*p)->lchild;
        //找到最右下的节点s
        while (s->rchild) {
            q = s;
            s = s->rchild;
        }
        //用s代替p
        (*p)->data = s->data;
        //判断s是q的左孩子还是右孩子，并在q中删除s
        if (q != *p) {
            q->rchild = s->lchild;
        }
        else {
            q->lchild = s->lchild;
        }
        free(s); //释放s的内存空间
    }
    return true; //删除成功
}

//定义一个函数，实现二叉排序树的建立操作
//参数：T表示要建立的二叉排序树，n表示要插入的元素个数，a表示要插入的元素数组
//返回值：无
void CreateBST(BiTree * T, int n, int a[]) {
    //初始化二叉排序树为空
    *T = NULL;
    //依次将数组中的元素插入到二叉排序树中
    for (int i = 0; i < n; i++) {
        InsertBST(T, a[i]);
    }
}