#include<stdio.h>
#include<stdlib.h>
#define MaxSize 30
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node *Lchild;
struct Node *Rchild;
} BiTNode, *BiTree;
typedef struct Stacknode
{
char data[MaxSize];
int top;
}SeqStack;
SeqStack *InitStack()
{
SeqStack *s;
s=malloc(sizeof(SeqStack));
s->top=-1;
return s;
}
int IsEmpty(SeqStack *s)
{
if(s->top==-1) return 1;
else return 0;
}
int Push(SeqStack *s, char x)
{
if(s->top==MaxSize-1) return 0;
else{
s->top++;
s->data[s->top]=x;
return 1;
}
}
int Pop(SeqStack *s,char *x)
{
if(IsEmpty(s)) return 0;
else {
*x=s->data[s->top];
s->top--; return 1;
}
}
void CreateBiTree(BiTree *root)
{
char ch;
ch=getchar();
if(ch=='#')
*root=NULL;
else
{
*root=(BiTree)malloc(sizeof(BiTNode));
(*root)->data=ch;
CreateBiTree(&((*root)->Lchild));
CreateBiTree(&((*root)->Rchild));
}
}
void PreOrder(BiTree root)
{
SeqStack *s;
BiTree p;
InitStack(s);
p=root;
while(p!=NULL||!IsEmpty(s))
{
while (p!=NULL)
{
printf("%c",p->data);
Push(s,p);
p=p->Lchild;
}
if(!IsEmpty(s))
{
Pop(s,&p);
p=p->Rchild;
}
}
}
int main()
{
BiTree root;
CreateBiTree(root);
PreOrder(root);
}