exercies.md

# 柯里昂家族树

在《教父》中，柯里昂家族是一个著名的黑手党家族，由家族的首领柯里昂（Don Corleone）和他的四个儿子构成。柯里昂家族的家谱是一棵二叉树，其中柯里昂是根节点，他的儿子们分别是他的左儿子和右儿子。

现在，你需要编写一个程序，读入一个包含若干行的字符串，每行表示一个人的信息。每行的格式如下：

<人物名称> is the <父亲名称>`s <儿子>

其中，人物名称是一个不包含空格的字符串，父亲名称和儿子也是一个不包含空格的字符串。

例如，下面是一棵柯里昂家族的家谱：

Don Corleone is the Don`s son
Fredo Corleone is the Don`s son
Michael Corleone is the Don`s son
Tom Hagen is the Don`s adopted son

你的程序需要按照这些信息建立一棵二叉树，并输出这棵树的前序遍历。

例如，对于上面的家谱，输出应该是：

Don Corleone Fredo Corleone Michael Corleone Tom Hagen

你的程序需要支持以下功能：

 - 建立二叉树。你需要定义一个结构体表示一个节点，包含人物名称、左儿子和右儿子三个字段。你需要编写一个函数，读入若干行字符串，根据字符串中的信息建立二叉树。

 - 输出前序遍历。你需要编写一个函数，输出给定二叉树的前序遍历。
## 输入格式
输入的第一行包含一个整数 n（1 <= n <= 1000），表示字符串的行数。

接下来的 n 行，每行包含一个字符串，表示一个人的信息。字符串的格式如上文所述。

## 输出格式
输出给定二叉树的前序遍历，每个人物名称占一行。

## 输入样例

4
Don Corleone is the Don`s son
Fredo Corleone is the Don`s son
Michael Corleone is the Don`s son
Tom Hagen is the Don`s adopted son

## 输出样例

Don Corleone
Fredo Corleone
Michael Corleone
Tom Hagen

## 提示

1. 人物名称和父亲名称均由不超过 100 个字符组成，且不包含空格；

2. 儿子的值可能是 "son" 或 "adopted son"；

3. 输入中可能会出现重名的人物，你的程序需要处理这种情况；

4. 输入的字符串保证是合法的，不会出现父亲名称找不到的情况。