Question

有关数据结构中树的问题，不会，拜托各位解答一下，不一定要给出代码，希望能给出详细的思路！不胜感激~

给出一张族谱，判断两人的关系，是亲戚，还是谁是谁的祖先。例如，第一行输入为n,表示有n个人，接着每行输入格式为第一个数为i,代表第i个人，接着输入为k,代表有几个儿子，接着输入儿子的代号。最后任意输入两个数，判断他们的关系。
例：
Input:
5
1 3 2 3 4
2 1 5
3 0
4 0
5 0
2 5
output:
2是5的祖先
也不一定要用树解决，只要能解决这道题就OK了

Answer 1

用树来做比较简单：
根据每一行的输入创建一个树，然后合并到主树上，完后后，判断起来就简单了，都是树的标准操作。

还有一种做法，定义一个二维数组d，第一维表示第几个人，第二维表示这个人的儿子，没有儿子则初始化为长度为0的空数组，最后的数组是这样的：
2 3 4
5
-
-
-（最后三个为空数组）
然后根据输入的两个数d1,d2，按下面的方式寻找关系：
(1) 递归遍历数组d[d1]，如果能够找到d2，表示d1是d2的祖先
(2) 否则，递归遍历d[d2]，如果能够找到d1，表示d2是d1的祖先
(3) 否则，d1和d2没有关系
这里主要是递归遍历，例如输入1,5，先遍历d[1]，也就是数组2,3,4，当遍历到2时，还要查看d[2]，结果找到了5，说明1是5的祖先。
其实这里的数组就是一颗简易的树，遍历时采用的是深度优先策略。
另外，为了描述方便，这里假设数组序号是从1而不是从0开始的，即数组的第一项为d[1]

Answer 2

用括号的方式来存储。例如，本例可以存为1（2（5），3，4）。
判断是祖先关系的：一个数在另一个数所属括号的前面
亲戚关系的：非祖先关系的都是亲戚关系。