#include <iostream>
#include <vector>
using namespace std;

typedef struct BinaryTree 
{
    int data;
    struct BinaryTree *rchild, *lchild;
}BinaryTree;

int createBinaryTree( BinaryTree * &T)  //必须用引用 因为内存是在函数里面分配的
{
        int ch;
        scanf("%d", &ch);

        if(ch != 0)
        {
            T = (BinaryTree *)malloc(sizeof(BinaryTree));
            T->data =http://www.mamicode.com/ ch;
            createBinaryTree(T->lchild);
            createBinaryTree(T->rchild);
        }
        else
        {
            T = NULL;
        }
    return 0;
}

int visit(int data)
{
    printf("%d ", data);
    return 0;
}


int PreOrderTraverse(BinaryTree T) //先序遍历  
{
    BinaryTree* p;
    vector<BinaryTree *> Stack;
    Stack.push_back(&T);
    while(!Stack.empty())
    {
        while((p = Stack.back()) != NULL) 
        {
            visit(p->data);
            Stack.push_back(p->lchild);
        }
        Stack.pop_back();
        if(!Stack.empty())
        {
            p = Stack.back(); 
            Stack.pop_back();
            Stack.push_back(p->rchild);
        }
    }
    return 0;
}


int InOrderTraverse(BinaryTree T) //中序遍历
{
    BinaryTree* p;
    vector<BinaryTree *> Stack;
    Stack.push_back(&T);
    while(!Stack.empty())
    {
        while((p = Stack.back()) != NULL) 
            Stack.push_back(p->lchild);
        Stack.pop_back();
        if(!Stack.empty())
        {
            p = Stack.back(); 
            Stack.pop_back();
            visit(p->data);
            Stack.push_back(p->rchild);
        }

    }
    return 0;
}

int main()
{
    BinaryTree * T = NULL;
    createBinaryTree(T);
    PreOrderTraverse(*T);
    InOrderTraverse(*T);
    return 0;
}