#include<stdio.h>
#include<malloc.h>
#define true 1;
#define false 0;
typedef struct BSTNode{
int data;
struct BSTNode *lchild,*rchild;
}CSTNode,*BSTNode;

BSTNode CreatBinary(BSTNode T)
{
int e;
scanf("%d",&e);
if(e==0) T=NULL;
else{
if(!(T=(BSTNode)malloc(sizeof(CSTNode)))) printf("Error");
T->data=e;
T->lchild=CreatBinary(T->lchild);
T->rchild=CreatBinary(T->rchild);
}
return T;
}

void PrintBinary(BSTNode T)
{
if(T)
{
PrintBinary(T->lchild);
printf("%5d",T->data);
PrintBinary(T->rchild);
}
}
Search_BST(BSTNode T,BSTNode p2,BSTNode p1,int key)
{
p1=T;
while(p1){
if(key==p1->data) {return true;}
else if(key<p1->data){
p2=p1;
p1=p1->lchild;
}
else{
p2=p1;
p1=p1->rchild;
}
}
return false;
}
int Insert_BST(BSTNode T,int key)
{
BSTNode S,p2,p1;
if(Search_BST(T,p2,p1,key))
{return false;}
else
{
S=(BSTNode)malloc(sizeof(CSTNode));
S->lchild=NULL;
S->rchild=NULL;
S->data=key;
if(!p2) T=S;
else if(key<p2->data) p2->lchild=S;
else p2->rchild=S ;
return true;
}

}

void main()
{
BSTNode T,p1,p2;
int key,a,b;
printf("\ninput the list:\n");
T=CreatBinary(T);
printf("\ninput key:\n");
scanf("%d",&key);
printf("\nbefore zhong xu:\n");
PrintBinary(T);
printf("\n output the result:\n");
a=Search_BST(T,p2,p1,key);
printf(" %d ",a);
b=Insert_BST(T,key);
printf("\n output the result:\n");
printf(" %d ",b);
printf("\nafter zhong xu:\n");
PrintBinary(T);
}