#include<stdio.h>
#define null 0
int counter=0;
typedef struct btreenode
{
int data;
struct btreenode  *lchild;
struct btreenode  *rchild;
}bnode;

bnode  *create(int x,bnode *lbt,bnode *rbt)
{
bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{
q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
/*if(p->lchild!=null)
q->rchild=p->lchild;*/
p->lchild=q;
}
}

bnode *ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
/*if(p->rchild!=null)
q->lchild=p->rchild;*/
p->rchild=q;
}
}


void prorder(bnode *p)
{
if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild);
if(p->lchild!=null)
prorder(p->lchild);
if(p->rchild!=null)
prorder(p->rchild);
}


 main()
 {
 bnode *bt,*p,*q;
 int x;
 printf("Input root:");
 scanf("%d",&x);
 p=create(x,null,null);
 bt=p;
 scanf("%d",&x);
 while(x!=-1)
 {
 p=bt;
 q=p;
 while(x!=p->data&&q!=null)

{
 p=q;
 if(x<p->data)
 q=p->lchild;
 else
 q=p->rchild;
 }
 if(x==p->data)
 {
 printf("The number is always egxit.");
 return;
 }


 else
 if(x<p->data)
 ins_lchild(p,x);
 else
 ins_rchild(p,x);
 scanf("%d",&x);
 }
 p=bt;
 printf("structure of the binary tree:\n");
 printf("number\t address\t data\t lchild\t rchild\n");
 prorder(p);
 }