#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 5
typedef int Status;
typedef int ElemType;
typedef struct elementtype
{
int key;
char Data;
}Elemtype;
typedef struct bstnode
{
Elemtype Element;
struct bxtnode *LChild,*RChild;
}BSTNode;
typedef struct bsttree
{
struct bstnode *root;
}BSTree;
//初始化
void Creat(BSTree *Bst){
Bst->root=NULL;
}
//查找
BSTNode *SearchRecursion(BSTNode *t,Elemtype Element)
{
if(t==NULL){
printf("ERROR\n");
return NULL;
}
if(t->Element.key==Element.key)
return t;
else if(t->Element.key>Element.key)
return SearchRecursion(t->LChild,Element);
else
return SearchRecursion(t->RChild,Element);
}
Status Search(BSTree *Bst,ElemType Element)
{
BSTNode *t=SearchRecursion(Bst->root,Element);
if(t)
return OK;
else
return ERROR;
}
//插入
BSTNode *CreateNode(ElemType element)
{
BSTNode *p=(BSTNode*)malloc(sizeof(BSTNode));
if(P==NULL)
return NULL;
p->Element.key=element.key;
p->LChild=p->RChild=NULL;
return p;
}
Status Insert(BSTNode *t,ElemType element)
{
if(t==NULL)
t=CreateNode(element);
else if(t->Element.key>element.key)
t->Lchild=Insert(t->LChild,element);
else if(t->Element.key<element.key)
t->RChild=Insert(t->RChild,element);
else if(t->Element.key==element.key)
return Duplicate;
return OK;
}
//删除
Status Delete(BSTNode *t,int key,ElemType Element)
{
if(t==NULL)
{
return NotPresent;
}
BSTNode *p=t,*prev;
while(p&&p->Element.key!=key)
{
prev=p;
if(p->Element.key>key)
p=p->LChild;
else
p=p->LChild;
}
if(p==NULL)
return ERROR;
Element.key=key;
if(p->LChild&&p->RChild)
{
BSTNode *min=p->RChild; //右子树最小的结点
prev=p;
while(min->LChild) //找到右子树最小结点
{
prev=min;
min=min->LChild;
}
p->Element.key=min->Element.key; //把找到的右子树的最小值与p进行值交换
//将min结点的子结点作为prev的子结点，并将min所指向的结点 删除
if(prev->RChild==min)
prev->LChild=min->RChild;
else
prev->LChild=min->RChild;
free(min);
p=NULL;
}else{
if(prev->LChild==p) //p为左子树的情况
prev->LChild=p->LChild ? p->LChild : p->RChild;
else if(prev->RChild==p) //p为右子树的情况
prev->RChild=p->LChild ? p->LChild : p->RChild;
free(p);
p=NULL;
}
return OK; //成功删除
}
//输出运算
void Traverse(BSTNode *t,ElemType Element,int direction)
{
if(t!=NULL)
{
Traverse(t->LChild,t->Element,-1);
printf("%d",t->Element.key);
Traverse(t->RChild,t->Element,1);
}
}
int main()
{
BSTree *Bst;
int e;
Create(Bst);
do{
scanf("%d",&e);
Insert(e)
}while(e!=#);
Search(Bst,35);
//Traverse()
}
