#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode{
	int data;
	BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


//	查找 
void InsBST(BiTree *T,int data){
	BiTNode *f,*p;
	p=(*T);
	while(p){
		if(p->data==data){
			printf("不需要插入已存在");
			return; 
		}
		f=p;
		p=(data<p->data)?p->lchild:p->rchild; 
	}
	p=(BiTree)malloc(sizeof(BiTNode));
	p->data=data;
	p->lchild=p->rchild=NULL;
	if((*T)==NULL)(*T)=p;
	else if(data<f->data) f->lchild=p;
		else f->rchild=p; 
	}
 
//	创建二叉排序树 
BiTree CreatBST(){
	BiTree T=NULL;
	int data;
	printf("输入整数关键字，0结束\n");
	scanf("%d",&data);
	while(data){
		InsBST(&T,data);
		printf("输入下一个整数关键字，0结束\n");
		scanf("%d",&data);
	} 
	return T;
}
//	查找 
void SearchBST(BiTree T,int data){
	BiTNode *p=T;
	while(p){
		if(p->data==data){
			printf("已找到");
			return; 
		}
		p=(data<p->data)?p->lchild:p->rchild; 
	}
	printf("没有找到你输入的数据");
}
//	删除 
void DelBSTNode(BiTree *T,int data){
	BiTNode *parent=NULL,*p,*q,*child;
	p=*T;
	while(p){
		if(p->data==data)break;
		parent=p;
		p=(data<p->data)?p->lchild:p->rchild;
	}
	if(!p){
		printf("没有找到要删除的结点");
		return ; 
	}
	p=q;
	if(q->lchild&&q->rchild)
		for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
		child=(p->lchild)?p->lchild:p->rchild;
		if(!parent) *T=child;
		else{
			if(p==parent->lchild) parent->lchild=child;
			else parent->rchild=child;
			if(p!=q) q->data=p->data;
		}
		delete(p);
} 
//	中序遍历 
void InOrderBST(BiTree T){
	if(T!=NULL){
		InOrderBST(T->lchild);
		printf("%3d",T->data);
		InOrderBST(T->rchild);
	}
} 

int main(){
	BiTree T;
	T=CreatBST();
	InOrderBST(T);
	SearchBST(T,5);
	
}