#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode
{
    int data;
    BiTNode * right,*left;
}BiTNode,*BiTree;

void create_bi_tree(BiTNode * &t)
{
    int a;
    scanf("%d",&a);
    if( a == 0)
    {
        t = NULL;
    }
    else
    {
        t = new BiTNode;
        t->data = a;
        create_bi_tree(t->left);
        create_bi_tree(t->right);
    }
}

void pre_order_traverse(BiTree t)
{
    if(t)
    {
        printf("%d\n",t->data);
        pre_order_traverse(t->left);
        pre_order_traverse(t->right);
    }
}

//先序非递归遍历 
void preorder(BiTNode *BST)
{
    BiTNode * p,*s[100];
    int top = 0;
    p = BST;
    while((p != NULL) || (top > 0))
    {
        while(p != NULL)
        {
            printf("%d   ",p->data);
            s[++top] = p;
            p = p->left;
        }
        p = s[top--];
        p = p->right;
    }
}

void main()
{
    BiTree t;
    create_bi_tree(t);
    //pre_order_traverse(t);
    preorder(t);
    system("pause");
}