二叉排序树(二叉搜索树，二叉查找树)详细代码实现

//二叉排序数（二叉搜索树，二叉查找树）
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>using namespace std;
#define end 32767 // 定义结束标志//结点结构
typedef struct BiTNode
{
    int data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;//二叉排序树的查找算法
//1.若查找到NULL，则搜索失败，否则：
//2.若x等于b的根节点的数据域之值，则查找成功；否则：
//3.若x小于b的根节点的数据域之值，则搜索左子树；否则：
//4.查找右子树。
bool SearchBST(BiTree T, int key, BiTree f, BiTree* p)
{
    //T为待查找的二叉树的根节点，会随着查找过程移动；//key为待查找的值//f指向T的双亲，如果查找不成功，p=f，供插入过程使用；//p如果查找成功，则指向成功的结点，若不成功，则指向访问的最后一个结点，即fif (!T){
    *p = f;return false;}else if (key == T->data){
    *p = T;return true;}else if (key < T->data){
    return SearchBST(T->lchild, key, T, p);}else if (key > T->data){
    return SearchBST(T->rchild, key, T, p);}
}//二叉排序树的插入算法
//先查找二叉树中有没有待插入的元素，如果有，则不插入；
//如果没有，则插入在访问的最后一个结点即p的左子树或者右子数
bool InsertBST(BiTree* T, int key)
{
    BiTree p, s;if (!SearchBST(*T, key, NULL, &p)) //如果查找失败{
    s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = NULL;s->rchild = NULL;if (!p) // 二叉树为空，插入的s为根结点{
    *T = s;}else if (key < p->data){
    p->lchild = s;}else if (key > p->data){
    p->rchild = s;}return true;}else //如果查找成功{
    return false;}
}//二叉排序树的创建—使用二叉排序树的插入算法进行
void CreateBST(BiTree* T)
{
    *T = (BiTree)malloc(sizeof(BiTNode));(*T)->lchild = NULL;(*T)->rchild = NULL;int c;scanf("%d", &c);if (*T && c != end){
    (*T)->data = c;}while (c != end){
    scanf("%d", &c);if (c != end && *T){
    InsertBST(T, c);}}
}//二叉排序树的删除算法
//两种情况：1、待删除的结点是叶子结点或该结点只有左子树或右子数
//2、待删除的结点既有左子树又有右子树
bool Delete(BiTree* p);
bool DeleteBST(BiTree *T, int key)
{
    if (!(*T)) // 如果没有查找到{
    return false;}else{
    if (key == (*T)->data){
    return Delete(T);}else if (key < (*T)->data){
    return DeleteBST(&(*T)->lchild, key);}else if (key >(*T)->data){
    return DeleteBST(&(*T)->rchild, key);}}
}
bool Delete(BiTree* p)
{
    BiTree q = NULL;BiTree s = NULL;//情况1—左右子树有一个为空或都为空if ((*p)->lchild == NULL){
    q = *p;*p = (*p)->rchild;free(q);}else if ((*p)->rchild == NULL){
    q = *p;*p = (*p)->lchild;free(q);}//情况2—左右子树都不为空else{
    //不是直接删除该结点，而是用该结点的中序遍历前驱（左子树中最大的）替换为该结点q = *p; s = (*p)->lchild;while (s->rchild){
    q = s;s = s->rchild;}(*p)->data = s->data;//然后再删除替换的结点，也分为两种情况//1、如果没有右子树，替换的结点就是待删除结点的左子结点，q = (*p)if (q == (*p)){
    q->lchild = s->lchild;}//2、如果有右子树，q != (*p)else{
    q->rchild = s->lchild;}free(s);}return true;
}int main()
{
    BiTree T = NULL;//创建二叉排序树CreateBST(&T);//查找元素int key = 104;BiTree p = NULL;bool single = SearchBST(T, key, NULL, &p);if (single){
    printf("查找成功");}else{
    printf("查找失败");}//删除元素int k = 105;DeleteBST(&T, k);return 0;
}