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

typedef struct TreeNode *SearchTree;

typedef struct TreeNode
{
	char s;
	SearchTree left;
	SearchTree right;
} TreeNode; 

void preorderTraversal(TreeNode *node) {
	if (node == NULL) {
        return;
    }
    printf("%c", node->s);
    preorderTraversal(node->left);
    preorderTraversal(node->right);
}

int main()
{
	int n;
	char s[3];
	scanf("%d",&n);
	TreeNode *root;
	TreeNode *array[26];
    for(int i = 0; i < 26; i++) {
    	array[i] = (TreeNode*)malloc(sizeof(struct TreeNode));
    	array[i]->s = i + 'a';
		array[i]->left = array[i]->right = NULL;
	}
	scanf("%s",s);
	root = array[s[0] - 'a'];
	root->left = s[1] == '*' ? NULL : array[s[1] - 'a'];
	root->right = s[2] == '*' ? NULL : array[s[2] - 'a'];
	for(int i = 0; i < n - 1; i++) {
		scanf("%s",s);
		array[s[0] - 'a']->left = s[1] == '*' ? NULL : array[s[1] - 'a'];
		array[s[0] - 'a']->right = s[2] == '*' ? NULL : array[s[2] - 'a'];
	}
	preorderTraversal(root);
	for (int i = 0; i < 26; i++) {
    	free(array[i]);
    }
	return 0;
}

调了好几个数据点都没找出问题（哭脸）