#include <bits/stdc++.h>
using namespace std;

typedef struct BinNode{
	char e;
	struct BinNode* lchild;
	struct BinNode* rchild;
}BinNode,*BinTree;

void create(BinTree &bt){
	char c;
	cin>>c;
	if(c=='0') bt=NULL;
	else{
		bt=(BinTree)malloc(sizeof(BinNode));
		bt->e=c;
		create(bt->lchild);
		create(bt->rchild);
	}
}

void pre_t(BinTree bt){
	if(bt!=NULL){
		cout<<bt->e<<' ';
		pre_t(bt->lchild);
		pre_t(bt->rchild);
	}
}

void mid_t(BinTree bt){
	if(bt!=NULL){
		mid_t(bt->lchild);
		cout<<bt->e<<' ';
		mid_t(bt->rchild);
	}
}

void post_t(BinTree bt){
	if(bt!=NULL){
		post_t(bt->lchild);
		post_t(bt->rchild);
		cout<<bt->e<<' ';
	}
}
/*层序遍历
void level_t(BinTree bt){
	queue<BinTree> q;
	if(bt!=NULL) q.push(bt);
	while(!q.empty()){
		cout<<q.front()->e<<' ';
		if(q.front()->lchild!=NULL)
			q.push(q.front()->lchild);...