//构造二叉树
#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

/*

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

*/

typedef struct node{

    int data;

    node *l;

    node *r;

}*tree;

tree head,t;  //head为头指针，同时为根节点，t为当前的节点

void dis(tree &p)   //删除二叉树

{

    if(p)

    {

        dis(p->l);

        dis(p->r);

        delete p;

    }

}

void build(tree &p) //先读入根节点，再从左到右

{

    int n;

    cin>>n;

    if(n != -)

    {

        p = new node;

        p -> data = n;

        build(p -> l);

        build(p -> r);

    }

    else

    p = NULL;

}

void frontvisit(tree p)

{

    if(p)

    {

        cout<< p->data <<" ";

        frontvisit(p->l);

        frontvisit(p->r);

    }

}

void midvisit(tree p)

{

    if(p)

    {

        midvisit(p->l);

        cout<<p->data<<" ";

        midvisit(p->r);

    }

}

void backvisit(tree p)

{

    if(p)

    {

        backvisit(p->l);

        backvisit(p->r);

        cout<<p->data<<" ";

    }

}

void in(tree &p,int n)

{

    if(p)

    {

        if(n < p->data)

        in(p->l,n);

        if(n > p->data)

        in(p->r,n);

    }

    else

    {

        p = new node;

        p->data = n;

        p->l = p->r =NULL;

    }

}

int main()

{

    int x;

    build(t);

    cin>>x;

    in(t,x);

    cout<<"frontvisit"<<endl;

    frontvisit(t);

    cout<<endl;

    cout<<"midvisit"<<endl;

    midvisit(t);

    cout<<endl;

    cout<<"backvisit"<<endl;

    backvisit(t);

    cout<<endl;

    return ;

}

/*

5 3 2 1 -1 -1 -1 -1 6 -1 7 -1 -1

4

*/