#include"stdlib.h"
#include"stdio.h"
#include"conio.h"
#define   MAX   100
//btree's struct
struct  Thtreenode;
typedef struct Thtreenode  *Pthtreenode;
struct  Thtreenode
{
   char     info;
   Pthtreenode  llink,rlink;
   int          ltag,rtag;
};

//stack's struct
struct seqstack
{
  Pthtreenode     s[MAX];
  int             t;
};
typedef   struct seqstack  *Pseqstack;


Pseqstack  Createmptystack(void);
void       Push(Pseqstack  st,Pthtreenode  p);
void       Pop(Pseqstack   st );
void       Visit(Pthtreenode  p);
Pthtreenode Top(Pseqstack  st);
Pthtreenode Creat_btree(void);
void	   Thread(Pthtreenode  t);
void	   Ninorder(Pthtreenode   t);
int        Isempty(Pseqstack  st);

Pthtreenode   Creat_btree(void)
{
   Pthtreenode  pbnode;
   char         ch;
   printf("intput the  data!!\n");
   scanf("\n%c",&ch);
   if(ch=='#')
      return;
   if(ch=='.')
      pbnode=NULL;
   else
   {
     pbnode=(Pthtreenode)malloc(sizeof(struct  Thtreenode));
     if(pbnode==NULL)
     {
       printf("\nout of space!!");
       return  (pbnode);
     }
     else
     {
	pbnode->info=ch;
	pbnode->ltag=0;
	pbnode->rtag=0;
	pbnode->llink=Creat_btree();
	pbnode->rlink=Creat_btree();
    }
  }
  return (pbnode);
}

void   Thread(Pthtreenode  t)
{
   Pseqstack   st;
   Pthtreenode p;
   Pthtreenode pr;
   if(t==NULL)  return;
   st=Createmptystack();
   p=t;
   pr=NULL;
   do
   {
     while(p!=NULL)
     {
       Push(st,p);
       p=p->llink;
     }
     while(p==NULL&&(!Isempty(st)))
     {
       p=Top(st);
       Pop(st);
       if(pr!=NULL)
       {
         if(pr->rlink==NULL)
          {
             pr->rlink=p;
             pr->rtag=1;
          }
        if(p->llink==NULL)
        {
          p->llink=pr;
          p->ltag=1;
        }
      }
     pr=p;
     p=p->rlink;
    }
  }while(!Isempty(st)||p!=NULL);
   free(st);
} 

//zhou you shu
void  Ninorder(Pthtreenode  t)
{
   Pthtreenode  p;
   if(t==NULL)
     return;
   p=t;
   while(p->llink!=NULL&&p->ltag==0)
      p=p->llink;
   while(p!=NULL)
   {
      Visit(p);
      if(p->rlink!=NULL&&p->rtag==0)
      {
         p=p->rlink;
         while(p->llink!=NULL&&p->ltag==0)
           p=p->llink;
      }
      else
        p=p->rlink;
   }
 }     
void   Visit(Pthtreenode  p)
{
  if(p->llink==NULL)
    printf("   -  ");
  else
    printf("   %c  ",p->llink->info);
  printf("\t  %d ",p->ltag);
  printf("\t  %c ",p->info);
  printf("\t  %d ",p->rtag);
  if(p->rlink==NULL)
    printf("\t   -  ");
  else
    printf("\t   %c  ",p->rlink->info);
  printf("\n");
}

//creat empty stack

Pseqstack  Createmptystack(void)
{
   Pseqstack  st;
   st=(Pseqstack)malloc(sizeof(struct seqstack));
   if(st==NULL)
     printf("\nout of space!!");
   else
     st->t=-1;
   return (st);
}


void  Push(Pseqstack st,Pthtreenode  p)
{
   if(st->t>=MAX-1)
     printf("\nover flow!!");
   else
   {
      st->t=st->t+1;
      st->s[st->t]=p;
   }
}


void  Pop(Pseqstack  st)
{
   if(st->t<0)  printf("\nover flow!!");
   else
     st->t=st->t-1;
}

Pthtreenode  Top(Pseqstack  st)
{
  return (st->s[st->t]);
}

int  Isempty(Pseqstack  st)
{
   return(st->t==-1);
}

void main()
{
    Pthtreenode  t;
    t=Creat_btree();
    Thread(t);
    printf("\nthe result is:\n");
    printf("Lchild\tLtag\tData\tRtag\tRchild\n");
    Ninorder(t);
    getch();
 }