#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
void main()
{
void InsertBST(BSTree *Tptr,KeyType key);
BSTree CreateBST(void);
void Inorder(BSTree T);
void DelBSTNode(BSTree *Tptr,KeyType key);
BSTNode *SearchBST(BSTree T,KeyType key);
BSTree T;
BSTNode *p;
int key;
printf("qingshuruguanjianzi(shuru0weijieshu) \n");
T=CreateBST();
printf("\n");
Inorder(T);
printf("\n");
printf("qingshuruyucharuguanjianzi:");
scanf("%d",&key);
InsertBST(&T,key);
printf("\n");
printf("qingshuruyushanchuguanjianzi:");
scanf("%d",&key);
DelBSTNode(&T,key);
printf("\n");
printf("qingshuruyuchazhaoguanjianzi:");
scanf("%d",&key);
p=SearchBST(T,key);
if(p==NULL)
printf("meiyouzhaodao%d!\n",key);
else
printf("zhaodao%d!\n",key);
printf("\n");
getch(0);
}
void InsertBST(BSTree *Tptr,KeyType key)
{
BSTNode *f,*p=*Tptr;
while(p)
{
if(p->key==key) return;
f=p;
p=(key<p->key)? p->lchild:p->rchild;
}
p=(BSTNode * )malloc(sizeof(BSTNode));
p->key=key;p->lchild=p->rchild=NULL;
if(*Tptr==NULL)
*Tptr=p;
else
if(key<f->key)
f->lchild=p;
else f->rchild=p;
}
BSTree CreateBST(void)
{
BSTree T=NULL;
KeyType key;
scanf("%d",&key);
while(key)
{
InsertBST(&T,key);
scanf("%d",&key);
}
return T;
}
void DelBSTNode(BSTree *Tptr,KeyType key)
{
BSTNode *parent=NULL,*p=*Tptr,*q,*child;
while(p){
if(p->key==key)break;
parent=p;
p=(key<p->key)? p->lchild:p->rchild;
}
if(!p)return;
q=p;
if(q->lchild&&q->rchild)
for(parent=q,p=q->lchild;p->rchild;parent=p,p=p->lchild);
child=(p->lchild)?p->lchild:p->rchild;
if(!parent)
*Tptr=child;
else
{if(p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
if(q!=p)
q->key=p->key;
}
free(p);
}
BSTNode *SearchBST(BSTree T,KeyType key)
{
if(T==NULL||key==T->key)
return T;
if(key<T->key)
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key);
}
void Inorder(BSTree T)
{
if(T)
{
Inorder(T->lchild);
printf("%c",T->key);
Inorder(T->rchild);
}}