#include <stdio.h>
#include <stdlib.h>
#define MAX 26
typedef struct _Node {
char name;
struct Node * left;
struct Node * right;
} Node;
Node * root;
char nodeList[MAX][3];
Node* createNode (char name) {
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->name = name;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void initTreeMemory (Node * node) {
if (node == NULL) {
return;
}
initTreeMemory(node->left);
initTreeMemory(node->right);
free(node);
}
Node* searchParentNode (Node * parent, char targetNode) {
Node * targetParent = NULL;
if (parent == NULL) {
return NULL;
}
if (parent->name == targetNode) {
return parent;
}
targetParent = searchParentNode(parent->left, targetNode);
if (targetParent == NULL) {
targetParent = searchParentNode(parent->right, targetNode);
}
return targetParent;
}
void showPreNode (Node * parent) {
if (parent == NULL) {
return;
}
printf("%c", parent->name);
showPreNode(parent->left);
showPreNode(parent->right);
}
void showInNode (Node * parent) {
if (parent == NULL) {
return;
}
showInNode(parent->left);
printf("%c", parent->name);
showInNode(parent->right);
}
void showPostNode (Node * parent) {
if (parent == NULL) {
return;
}
showPostNode(parent->left);
showPostNode(parent->right);
printf("%c", parent->name);
}
void startMakeTree (int N) {
root = createNode(nodeList[0][0]);
for (int y = 0; y < N; y++) {
Node * parentNode = NULL;
for (int x = 0; x < 3; x++) {
char targetNode = nodeList[y][x];
if (targetNode == '.') {
continue;
}
if (x == 0) {
parentNode = searchParentNode(root, targetNode);
} else if (x == 1) {
if (parentNode != NULL) {
parentNode->left = createNode(targetNode);
}
} else {
if (parentNode != NULL) {
parentNode->right = createNode(targetNode);
}
}
}
}
}
int main(void) {
int N = 0;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
scanf("%s", &nodeList[i][j]);
}
}
startMakeTree(N);
showPreNode(root);
printf("\n");
showInNode(root);
printf("\n");
showPostNode(root);
initTreeMemory(root);
return 0;
}
