#include<stdio.h>
/* senkouzyunsousa*/
/*----------------------------------------------------------------------------*/

struct node 
  {char info;struct node *l, *r; };
struct node Z={ 0, &Z, &Z},
            
            i={ 9, &Z, &Z},

	    h={ 8, &Z, &Z},

            g={ 7, &Z, &Z},

            f={ 6, &Z, &Z},

	    e={ 5, &Z, &Z},

            d={ 4, &e, &f},

            c={ 3, &h, &i},
           
            b={ 2, &d, &g}, 

	    a={ 1, &b, &c};


/*----------------------------------------------------------------------------*/

struct tagNODE
    { struct node *key;struct tagNODE *next; };
struct tagNODE *head, *z ,*s;
/*key = (struct node*) malloc(sizeof *key);*/

stackinit()
{
 head = (struct tagNODE*) malloc(sizeof *head);
 z =(struct tagNODE*) malloc(sizeof *z);
 head->next = z;
 z->next =z;
}


push(struct node *v)
{
 s = (struct tagNODE*) malloc(sizeof *s);
 s->key = v; 
 s->next =head->next;
 head->next = s;
 }


struct node *pop()
{
 struct node *x;
 x = (struct node*) malloc(sizeof *x); 
 s = head->next;
 head->next = s->next;
 x = s->key;
 free(s);
 return x;
}


int stackempty()
{ return head->next == z; }


/*----------------------------------------------------------------------------*/

traverse(struct node *t)
  {
    stackinit();
    push(t);
    while (!stackempty())
      {
       t = pop();printf("%d", t->info);
       if (t->r != &Z) push(t->r);
       if (t->l != &Z) push(t->l);
      }
  }


/*----------------------------------------------------------------------------*/
main()
  {  
   traverse(&a);
  }

124567389