#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define N 100
#define null 0
#define maxstack 50
typedef struct node
{ char data;
  node *lchild;
  node *rchild;
}* bitree;

struct stackitem
{struct node *a;
 int b;
};

struct stack
{int top;
 struct stackitem A[maxstack];
}s;

char e[N+1];

int setup(bitree &t)
{char ch=' ';
 scanf("%c",&ch);
 if(ch==' ')t=null;
 else{
	 if(!(t=(node *)malloc(sizeof(node))))return 0;
	 t->data=ch;          //建立根節點
	 printf("%c",t->data);
	 setup(t->lchild);//建立左子樹
	 setup(t->rchild);//建立右子樹
 }
 return 1;
}


void push(struct stackitem x)//進棧
{int p;
 p=s.top;
 if(p==maxstack)
	 printf("stack overflow");
 else
 {s.top=p+1;
  s.A[s.top]=x;
 }
}
 struct stackitem pop()//出棧
{int p;
 struct stackitem n;
 p=s.top;
 if(p==-1)
	 printf("stack underflow");
 else
 {n=s.A[p];
  s.top=p-1;
  return(n);
 }
}

void travl(bitree t)//先序非遞歸調用
{int b1;
 struct stackitem p;
 b1=0;
 p.b=b1;
 p.a=t;
 s.top=-1;
 while(t!=null||s.top!=-1)
	 if(t!=null)
	 {printf("%c",t->data);
          p.a=t;               //方問根節點
	  push(p);
	  t=t->lchild;        //訪問左子樹    
	 }
	 else
	 {t=pop().a;
          t=t->rchild;        //訪問右子樹
         }
}

void main()
{bitree t=null;
 printf("輸入數值:");
 setup(t);
 printf("\n先序遍歷非遞歸遍歷結果為:");
 travl(t);
}