#include<stdio.h>
#include<conio.h>
#include<bios.h>
#include<string.h>
#include<alloc.h>
#define N 50

typedef struct NODE
 {
  struct NODE *rchild;
  struct NODE *lchild;
  int data;
  int rtag;
  int ltag;
 }TREENODE,*TREENODEPTR;

void bianli(TREENODE *root);
void inthreadtree(TREENODE *root);
void creattree(TREENODEPTR Tree);
void outputtree( TREENODEPTR root);

TREENODEPTR pre;



void main()
{
 TREENODEPTR p;
 clrscr();
 printf("Input your tree: ");
 pre=(TREENODEPTR)malloc(sizeof(TREENODE));
 p=(TREENODEPTR)malloc(sizeof(TREENODE));

 creattree(p);
 outputtree(p);
 inthreadtree(p);
 gotoxy(1,9);
 bianli(p);
 getch();
}



void outputtree( TREENODEPTR root)
{
 struct p
{
 int x;int y;
}spot[20];

TREENODEPTR q[20];
TREENODEPTR p;
int font=0,rare=0,num1=1,num2=0,num3=0,sheet=0,x,y;
q[0]=root;
spot[0].x=40;
spot[0].y=3;
gotoxy(40,3);
printf("%d",root->data);

while(rare>=font)
{
 p=q[font];

 if(p->lchild!=NULL)
  {
    rare++;num2++;
    q[rare]=p->lchild;
    x=spot[font].x-12+sheet;
    y=spot[font].y+2;
    spot[rare].x=x; spot[rare].y=y;
    gotoxy(x,y);
    printf("%d",p->lchild->data);
  }



 if(p->rchild!=NULL)
 {
  rare++;num2++;
  q[rare]=p->rchild;
  x=spot[font].x+12-sheet;
  y=spot[font].y+2;
  spot[rare].x=x;
  spot[rare].y=y;
  gotoxy(x,y);
  printf("%d",p->rchild->data);
 }

 font++;
 num3++;
 if(num3==num1)
 {
  sheet+=2;
  num1=num2;
  num2=num3=0;
 }
}
}

void creattree(TREENODEPTR Tree)
{
 char a; int rare=0,font=0;
 TREENODE *p[N],*q,*root;
 scanf("%d",&a);
 root=Tree;

 if(a!=0)
 {
  p[rare]=root;
  (*root).data=a;
 }

 while(rare>=font)
  {
  scanf("%d",&a);
  if(a!=0)
  {
    q=(TREENODEPTR)malloc(sizeof(TREENODE));
   (*q).data=a;
   q->lchild=NULL;
   q->rchild=NULL;
   p[font]->lchild=q; p[font]->ltag=0;
   rare++;
   p[rare]=q;
  }
  else{(*p[font]).lchild=NULL;}

  scanf("%d",&a);

  if(a!=0)
  {
   q=(TREENODEPTR)malloc(sizeof(TREENODE));
   (*q).data=a;
   q->lchild=NULL;
   q->rchild=NULL;
   p[font]->rchild=q; p[font]->rtag=0;
   rare++;
   p[rare]=q;

  }
  else{(*p[font]).rchild=NULL;}

  font++;
 }
}

void inthreadtree(TREENODE *root)
{
 TREENODE *p;

 p=root;
 if(p!=NULL)
 {
  inthreadtree(root->lchild);
  if(p->lchild==NULL)
  {
  p->lchild=pre;p->ltag=1;}
  if(pre->rchild==NULL)
  {
   pre->rchild=p;pre->rtag=1;}
   pre=p;
   inthreadtree(root->rchild);
 }
}


void bianli(TREENODE *root)
{
 TREENODEPTR p;
 p=root;

 printf("\n\nInorder: ");
 while(1)
 {
   while(p->lchild!=NULL&&p->ltag==0)
  {
   p=p->lchild;
  }

  printf("%d ",p->data);


  while(p->rtag==1)
  {
    p=p->rchild;
    printf("%d ",p->data);
  }
  if(p->rchild!=NULL)
  p=p->rchild;
  else break;
 }
}