//查找，插入，建立，删除

#include<iostream.h>

#include<stdlib.h>

typedef int   KeyType;//关键字类型

typedef int Status;

#define OK 1

#define ERROR 0

//关键字域

typedef struct  

{

KeyType key;

}ElemType,TElemType;

//结点类型

typedef struct BiTNode

{

TElemType data; //结点信息

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//二叉树查找(递归)(中序)

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)

{//其中f为当前指向结点的双亲，p为当前指向结点

//查找成功则p返回当前结点，否则返回上一个结点

if (!T) //查找失败

{

p=f;

return false;

}

else if(key==T->data.key) //查找成功

{

p=T;

return true;

}

else if (key<T->data.key)

SearchBST(T->lchild,key,T,p); //在左子树上查找

else

SearchBST(T->rchild,key,T,p); //在右子树上查找

return false;

}//SearchBST

//插入结点

Status InsertBST(BiTree &T,ElemType e)

{

BiTree p,s;

if(!SearchBST(T,e.key,NULL,p)) //查找树中是否有该结点，若没有则插入

{

s=(BiTree)malloc(sizeof(BiTNode)); //注意，通过查找p这时指向为将要插入的上一结点的位置

s->data=e;

s->lchild=s->rchild=NULL;

if(!p)

T=s; //插入s为新的根结点

else if(e.key<p->data.key) //插入左子树

p->lchild=s;

else

p->rchild=s; //插入右子树

return true;

}

else

return false;

}//InsertBST

//删除结点

void Delete(BiTree &p);

Status DeleteBST(BiTree &T,KeyType key)

{

if(!T) return false;

else

{

if(key==T->data.key)

Delete(T); //找到关键字等于key的数据元素

else if(key<T->data.key)

DeleteBST(T->lchild,key); //继续在左子树进行查找

else

DeleteBST(T->rchild,key); //在右子树进行查找

return true;

}

}

void Delete(BiTree &p)

{

BiTree q,s;

if(!p->rchild) //右子树空则只需要重接它的左子树

{

q=p;

p=p->lchild;

free(q); //释放结点空间

}

else if(!p->lchild) //左子树为空则重接其右子树

{

q=p;

p=p->rchild;

free(q);

}

else //左右子树均不为空

{

q=p;

s=p->lchild; //找p的前驱

while (!s->rchild)

{

q=s;

s=s->rchild;

}

p->data=s->data;

//s指向被删结点的前驱

if(q!=p)

q->rchild=s->lchild;

else

q->lchild=s->lchild;

//重接q的左子树

free(s);

}

}//Delete

//遍历二叉树

Status InOrderBST(BiTree T)

{

if(T)

{

InOrderBST(T->lchild);

cout<<T->data.key<<"    ";

InOrderBST(T->rchild);

}

return true;

}

//主函数中通过循环调用插入函数来创建排序二叉树