#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

struct node{
	struct node * lchild;
	struct node * rchild;
	int data;
};
typedef struct node *BTREE;
typedef node * tree;

//void INORDER  (tree T ); //中根遍歷
//void POSTORDER(tree T ); //后根遍歷
//void EMPTY(tree T); //建立一個空樹
//void CREATEBT (char v, tree* LT , tree* RT);//建立一株新2元樹

BTREE CREATBT();

void PREORDER (BTREE BT); //先根遍歷
//void LCHILD(BTREE BT);//返回左兒子，若無則返回空
//void RCHILD(BTREE BT);//返回右兒子，若無則返回空
//void DATA (BTREE BT);//返回2元樹T根節(jié)點(diǎn)的數(shù)據(jù)域的值
//void ISEMPTY (BTREE T);//判斷2元樹T是否為空

void main ()
{
	BTREE BT;
	BT=CREATBT();
	PREORDER(BT);
}

BTREE CREATBT()
{
	struct node * s[MAX];

	int i ,j ;
	int ch;
	struct node *bt,*p;
	cin>>i>>ch;
	while(i!=0&&ch!=0)
	{
		p=(BTREE)malloc(sizeof(BTREE));
		p->data=ch;
		p->lchild=NULL;
		p->rchild=NULL;
		s[i]=p;
		if(i==1)
			bt=p;
		else
		{
			j=i/2; //父節(jié)點(diǎn)的編號
			if(i%2==0)
				s[j]->lchild=p; //i是j的左兒子
			else
				s[j]->rchild=p; //i是j的右兒子
		}
		cin>>i>>ch;
	}
	return bt;
}
void PREORDER (BTREE BT)
{
	if(BT!=NULL)
	{
		printf("%d",BT->data);
		PREORDER(BT->lchild);
		PREORDER(BT->rchild);
	}
}