#include <iostream>
//#include<stdio.h>
using namespace std;
typedef struct node //二叉树结点的类型
{
int data;
struct node* lchild,*rchild;
}bintnode,*bitree;
//typedef bintnode *bintree;
//bintree root;
bitree create()//先序创建
{
bitree root=NULL;
int c;
cin>>c;
if(c!='#')
//else
//while(c=='#')
{
root=(node*)malloc(sizeof(node));
root->data=c;
root->lchild=create();
root->rchild=create();
}
return root;
}
typedef struct stack //栈结构定义
{
bitree data[100]; //data 元素类型为 指针
int top; //栈顶指针
}*seqstack;
/*void push(seqstack* s,bintree t) //进栈
{
s->data[++s->top]=t;
}*/
bitree pop(seqstack s) //出栈
{
if(s->top!=-1) //非递归遍历中，top初始值为-1
{
s->top--;
return (s->data[s->top+1]);
}
else
return NULL;
}
void visit(int ch)
{cin>>ch>>" ";}
void preorder(bitree t)
{
seqstack s;
s->top=-1; //top初始值为-1
while((t!=NULL)||(s->top!=-1)) // 当前 处理的 子树 不为空，或栈不为空，则循环
{
while(t)
{
visit(t->data); //访问当前子树根结点
s->top++;
s->data[s->top]=t; //当前子树根结点进栈(因为还要访问右子树)
t=t->lchild; //访问此根结点 左孩子
} //循环直到遍历完 当前子树 根结点，和其 左 孩子
if(s->top>-1)
{
t=pop(s); //当前子树跟结点出栈
t=t->rchild; //访问其右孩子
}
}
}
int main()
{
bitree t;
t=create();
preorder(t);
return 0;
}