1 #include <cstdio>

 2 using namespace std;

 3

 4 struct Node{

 5     int lsh = -1 , rsh = -1;　　//左子树和右子树

 6 };

 7

 8 bool vis[30];　　//由于数组不是连续的，通过vis判断是否有值

 9 bool isNotRoot[100];　//不是根，最后只有一个节点的值是false

10 char s[5];

11 Node tree[50];　　//五十个节点

12

13 void build(int P,int l,int r)

14 {

15     vis[P] = true;

16     if (l >= 0)

17     {

18         tree[P].lsh = l;

19         isNotRoot[l] = true;

20         vis[l] = true;

21     }

22     if (r >= 0)

23     {

24         tree[P].rsh = r;

25         isNotRoot[r] = true;

26         vis[r] = true;

27     }

28 }

29

30 void dfs(int n)

31 {

32     if (n<0) return;

33     printf("%c",char(n+'a'));//前序遍历的递归写法，中序和后序调整位置即可

34     dfs(tree[n].lsh);

35     dfs(tree[n].rsh);

36 }

37

38 int main()

39 {

40     int n =0;

41     scanf("%d",&n);

42

43     for (int i=0;i<n;i++)

44     {

45         scanf("%s",s);

46         build(s[0]-'a',s[1]-'a',s[2]-'a');

47     }

48

49     for (int i=0;i<=26;i++){

50         if (vis[i] && !isNotRoot[i])　　//如果有值并且是根节点就遍历

51         {

52             dfs(i);

53             break;　　//考虑到只有一个根节点，一个循环结束就不用继续了

54         }

55     }

56     printf("\n");

57     return 0;

58 }