#include <stdio.h>
#define maxn 11
struct node
{
int lchild,rchild;
int data;
}Node[maxn];
int Hash[11]={0},n,m;
int change(char c)
{
if(c=='-')
return -1;//没有孩子节点
else
{
Hash[c-'0']=1;//同时标记出现了子节点
return c-'0';
}
}
int getroot()
{
int i;
for(i=0;i<11;i++)
if(Hash[i]==0)
return i;
}
void postOrder(int root)//我们在后序遍历里交换左右孩子节点，就是翻转二叉树
{
int temp;
if(root==-1)
return ;
postOrder(Node[root].lchild);
postOrder(Node[root].rchild);
//我们交换左右孩子节点
temp=Node[root].lchild;
Node[root].lchild=Node[root].rchild;
Node[root].rchild=temp;
}
int num=0;
void inOrder(int root)//我们中序遍历
{
if(root==-1)
return ;
inOrder(Node[root].lchild);
printf("%d",root);
num++;
if(num<n)
printf(" ");
else
printf("\n");
inOrder(Node[root].rchild);
}
void bfs(int root)
{
int queue[maxn],now;//我们来模拟一个队列就好了
int rear=0,front=0,k=0;
queue[rear++]=root;//我们首先将根节点入队列
while(rear!=front)
{
now=queue[front++];//将队首元素出队列
printf("%d",now);
k++;
if(k<n)
printf(" ");
else
printf("\n");
if(Node[now].lchild!=-1)queue[rear++]=Node[now].lchild;
if(Node[now].rchild!=-1)queue[rear++]=Node[now].rchild;
}
}
int main()
{
int i,root;
char c1,c2;
scanf("%d",&n);
for(i=0;i<n;i++)
{
getchar();//吸收上一行的换行符
scanf("%c %c",&c1,&c2);
Node[i].lchild=change(c1);
Node[i].rchild=change(c2);
}
root=getroot();//找到根节点的标号post
postOrder(root);
bfs(root);
inOrder(root);
return 0;
}
