临近考试，这里先只发一下代码，关于定义，原理什么的等我有时间了会补充上。

#include <iostream>
#include <string>
using namespace std;
typedef int KeyType;    // 关键字类型
typedef string InfoType;    // 其他数据类型


typedef struct ElemType
{
    KeyType key;    // 关键字项
    InfoType info;  // 其他信息项
    // friend ElemType operator >> ( std::istream in, ElemType e)   // 想重载一下，结果发现没效果
    // {
    //     in >> e.key;
    //     in >> e.info;
    // }
} ElemType;         // 每个结点的类型
typedef struct BSTNode
{
    ElemType data;  // 数据域
    struct BSTNode *lchild, *rchild;    // 左右子节点指针
} BSTNode, *BSTree;

BSTree SearchBST(BSTree T, KeyType key)
{
    if( !T || T->data.key == 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)
    {
        BSTree s = new BSTNode;     // 带插入节点
        s->data = e;
        s->lchild = s->rchild = NULL;
        T = s;
    }
    else if(e.key < T->data.key)
        InsertBST(T->lchild, e);    // 调用插入函数
    else
        InsertBST(T->rchild, e);
}
void CreatBST(BSTree &T)
{
    T = NULL;
    ElemType e;
    while(cin >> e.key)     // 输入文件结束符终止
    {
        InsertBST(T, e);
    }
}
void DeleteBST(BSTree &T, KeyType key)
{
    BSTree p = T;   // p为待删除节点
    BSTree f = NULL;    // f为带删除节点的双亲结点
    while(p)      // 查找的非递归写法
    {
        if(p->data.key == key)  // 找到关键字等于key的结点，结束循环
            break;
        f = p;                  // f是待删除结点的父节点
        if(key < p->data.key)   // 在左子树中继续寻找
            p = p->lchild;      
        else
            p = p->rchild;      // 在右子树中继续寻找
    }
    if(!p)  return;     // 没有查找到
    
    BSTree tmp = p;   // 先用tmp保存待删除结点
    if((p->lchild) && (p->rchild))  // 左右子树都存在
    {
        BSTree s = p->lchild;
        while(s->rchild)    /// 在*p的左子树中继续寻找其直接前驱，即最右下结点
        {
            tmp = s;        // 这里tmp是s的父节点
            s = s->rchild;
        }
        p->data = s->data;          // 把*p的前驱结点放到p处，然后删除前驱结点
        if(tmp != p)      // 如果相等了，说明p结点的左子树没有右子树
            tmp->rchild = s->lchild;    // s->lchild可能是一个子树，也可能是NULL
        else
            tmp->lchild = s->lchild;
        delete s;
        return;
    }
    else if( !p->rchild) //被删除结点没有右子树，只需要重接其左子树
        p = p->lchild;
    else if( !p->lchild) //被删除结点没有左子树，只需要重接其右子树
        p = p->rchild;    


    // 修改被删除结点父节点指针的指向
    if(!f)      // 被删除结点是根结点
        T = p;
    else if(tmp == f->lchild)   // 挂接到*f的左子树，被删除结点是被删除结点的父节点的左子树
        f->lchild = p;
    else                        // 挂接到*f的右子树
        f->rchild = p;
    delete tmp;
}

int main()
{
    BSTree T;
    CreatBST(T);

    BSTree t1 = SearchBST(T, 10);
    if(t1)
        cout << t1->data.key << endl;
    DeleteBST(T, 10);
    BSTree t2 = SearchBST(T, 10);
    if(t2)
        cout << t2->data.key << endl;
    else
        cout << "Not Find" << endl;




    return 0;
}