```c++
#include<iostream>

using namespace std;
/*-----------二叉排序树的二叉链表的存储表示-----------*/
#define ENDFLAG 999
typedef int KeyType;
typedef int InfoType;
typedef struct {
    KeyType key;//关键子项
    InfoType otherinfo;//其他数据域
} ElemType;
typedef struct BSTNode {
    ElemType data;//每个结点的数据域包括关键字项和其他数据项
    struct BSTNode *lchild, *rchild;//左右孩子指针
} BSTNode, *BSTree;

/*-----------二叉排序树的查找--------------*/
BSTNode *Search_BST(BSTree &T, KeyType key) {
    while (T != NULL && key != T->data.key) {
        if (key < T->data.key) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

/*--------- 二叉排序树的递归查找-----------*/
BSTNode *SearchBST(BSTree T, KeyType key) {
    //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
    //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
    if ((!T) || key == T->data.key) return T;//查找结束
    else if (key < T->data.key) return SearchBST(T->lchild, key);//在左子树中继续查找
    else return SearchBST(T->rchild, key);//在右子树中继续查找
}

/*----------二叉排序树的插入------------*/
void InsertBST(BSTree &T, ElemType e) {
    if (!T) {
        BSTNode *S = new BSTNode;//生成新结点*S
        S->data = e;//新结点*S的数据域置为e
        S->lchild = S->rchild = NULL;//新结点*S作为叶子结点
        T = S;//把新结点*S链接到已找到的插入位置
    } else if (e.key < T->data.key)
        InsertBST(T->lchild, e);//将*S插入左子树
    else if (e.key > T->data.key)
        InsertBST(T->rchild, e);//将*S插入右子树
}

/*------------非递归建立二叉排序树------------*/
BSTNode *nonRecusInsertNode(BSTree &T, ElemType e) {
    BSTNode *p = T;         //用来查找
    BSTNode *q = NULL;                //用来指明当前插入位置的父节点

    //此处用来寻找插入的位置和当前插入位置的父节点
    //q记录插入位置的父节点用来连接插入的孩子
    while (p != NULL) {
        if (p->data.key == e.key) {
            return NULL;            //已经存在，插入失败
        } else if (p->data.key > e.key) {
            q = p;
            p = p->lchild;            //找到对应插入为NULL的位置
        } else {
            q = p;
            p = p->rchild;
        }
    }
    //初始化一个插入结点
    p = (BSTNode *) malloc(sizeof(BSTNode));
    p->data.key = e.key;
    p->lchild = NULL;
    p->rchild = NULL;

    //将插入结点与之父节点相连
    if (!q) {        //要插入根节点，直接用T指针相连
        T = p;
    } else if (q->data.key > e.key) {        //插入父节点的左边，将父节点的左孩子指向插入的结点
        q->lchild = p;
    } else q->rchild = p;                //插入父节点的右边，将父节点的右孩子指向插入的结点
    return p;
}

/*----------二叉排序树的创建-----------*/
void CreatBST(BSTree &T) {
    //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
    T = NULL;//将二叉排序树T初始化为空树
    ElemType e;
    int test_num[] = {6, 10, 45, 32, 55, 68, 100};

    for (int i = 0; i < sizeof(test_num) / sizeof(test_num[0]); ++i) {
        e.key = test_num[i];
        InsertBST(T, e);
    }
}

/*---------二叉排序树的删除----------*/
void DeleteBST(BSTree &T, KeyType key) {
    //从二叉排序树T中删除关键字等于key的结点
    BSTNode *p = new BSTNode;
    BSTNode *f;
    p = T;
    f = NULL;
    /*--------------下面的while循环从根开始查找关键字等于key的结点*p----------*/
    while (p) {
        if (p->data.key == key) break;//找到关键字等于key的结点*p，结束循环
        f = p;//*f为*p的双亲结点
        if (p->data.key > key) p = p->lchild;//在*p的左子树中继续查找
        else p = p->rchild;//在*p的右子树中继续查找
    }
    if (!p) return;//找不到被删结点则返回
    /*------考虑3种情况实现p所指子树内部的处理：
     * *p左右子树均空(为叶子节点)、
     * 左右子树均不空、
     * 无右子树(或无左子树)----*/

    if (p->lchild == NULL && p->rchild == NULL) {//1.*p左右子树均空(为叶子节点)
        p = NULL;
    } else if (p->lchild == NULL) {//2.1.*p左子树为空
        if (f->lchild == p)
            f->lchild = p->rchild;
        else {
            f->rchild = p->rchild;
        }
        delete p;
    } else if (p->rchild == NULL) {//2.2.*p右子树为空
        if (f->lchild == p)
            f->lchild = p->lchild;
        else {
            f->rchild = p->lchild;
        }
        delete p;
    } else {//3.左右子树均不空
        BSTNode *q = p->rchild;//*q为直接后继(*p右子树的最左节点)
        BSTNode *q_f = p;
        while (q->lchild) {
            q_f = q;//*q_f为*q的双亲结点, 如果进入while循环, *q必为*q_f的左孩子
            q = q->lchild;
        }
        p->data = q->data;//将直接后继(*p右子树的最左节点)的值赋给*p
        if (q_f == p) {
            q_f->rchild = q->rchild;//未进入while循环, 代表直接后继*q为*p的右孩子, 此结点*q必无左子树
        } else {
            q_f->lchild = q->rchild;//进入while循环, 代表直接后继为*p的右子树的最左节点, 此结点*q必无左子树
        }
        delete q;
    }

}

/*------------二叉树的中序遍历------------*/
void InorderTree(BSTree T) {
    if (T) {
        InorderTree(T->lchild);
        cout << T->data.key << " ";
        InorderTree(T->rchild);
    }
}

int main() {
    BSTree T = NULL;
    CreatBST(T);//创建一棵二叉排序树
    InorderTree(T);//中序遍历二叉树
    cout << endl;
    cout << "请输入您要查询的元素：" << endl;
    int k = 0;
    cin >> k;
    BSTree T1 = NULL;//定义T1用来接收查找结果
    T1 = SearchBST(T, k);
    if (T1) cout << "存在此元素！" << endl;
    else cout << "不存在此元素！" << endl;
    int key = 0;
    cout << "请输入您要删除的元素：" << endl;
    cin >> key;
    DeleteBST(T, key);//删除元素
    InorderTree(T);//再次中序遍历二叉树
    return 0;
}
```

&nbsp;

&nbsp;