数据结构，二叉树遍历，孩子兄弟表示法，算法设计题
设有一家谱树，用二叉链表结构存储（孩子兄弟表示法），树中的结点信息为成员名字，编写函数，输出家谱中共有多少代以及最后一代人数和成员名字。要求先给出算法思想，再写出相应代码。
对于一般的家谱树(一般的多叉树)来说，我们可以很清楚的看出层次关系，树的层数表示代数（一共多少代人），树的最后一层表示最后一代人，由于多叉链表法表示的不方便，因此被迫无奈采用孩子兄弟表示法(二叉链表法).
假设我的家谱是这样的：
转换成孩子兄弟表示法后是这样的：
我们要做的是：这时我们要找有多少代人，以及最后以一代人出来。
如果根据第一个图来说找代数就是树的高度，最后一代人就是树的最后一层，二叉链表法中却不如第一个图来的直观，但是只要把握二叉链表法的本质还是很清晰的，根据孩子兄弟表示法的特性，（看二叉链表法的图）结点3的左子树保存的是其孩子，结点3的右子树保存的是其堂兄弟(对照第一个图来看)。假设我们每一个节点都有一个变量用来存储它是第几代的，那么从结点1开始，我们要找结点10是第几代的话，应该这么做：结点1是第一代，然后经过结点5是第二袋，然后看到结点10是第三代。因为第i个结点的左子树是他的孩子，既然是孩子，代数必须+1，而右子树是和第i结点同辈份的（堂兄弟），因此不能加1。本质来说就是往左走代数+1，向右走代数不变。这就是这题目的思路，通过这个方法你就可以知道有多少代人了，且每个节点都有保存了代数信息（用变量存起来了），再次遍历树把最后一代的结点输出即可。清晰了吗？清晰了我就开始写程序。
追问我知道了，重新定义一个二叉树。加上int generation;
麻烦写一下程序吧，谢谢
你急不急，我能不能过两天给你程序，我大四了要赶着做课程设计，然后复习基础课出去实习，现在是搞安卓课程设计，气死我了，那老师太掉了。
追问拜托了，我也大四，考计算机研究生
追答程序我用递归来写，要是你说你考研我肯定不拖你那么久，早说么，考研大过天，祝你考研顺利，12月份考呢，我微积分好的话我也想考QAQ，问题是（呵呵）。。程序我上传，不懂可以问我，用递归函数写的，思路就是我之前给你分析的一样，往左右generation+1，往右走代数不变，你在递归函数里好好想想。。
int num = 0;//最后一代的个数
void DFS1(CSTree tree,int high)
{
if(tree == NULL)
return;
if(tree->nextsibling != NULL)
{
cstree_high = max(cstree_high,high); //兄弟 高度不能变
DFS1(tree->nextsibling,high);
}
if(tree->firstchild != NULL)//孩子节点不为空 未访问过
{
cstree_high = max(cstree_high,high+1);//高度加一 去最大值
DFS1(tree->firstchild,high+1);
}
}
void DFS2(CSTree tree,int high)
{
if(tree == NULL)
return;
else if(high == cstree_high)
{
num++;
printf("%d ",tree->data);
}
if(tree->nextsibling != NULL)
{
DFS2(tree->nextsibling,high);
}
if(tree->firstchild != NULL)//孩子节点不为空 未访问过
{
DFS2(tree->firstchild,high+1);
}
}
void HomeTree(CSTree tree)// 2014年829和922真题 求共有多少代人，最后一代的人数并输出
{
/*
算法思想：第一次dfs搜索，找出共有多少代。
注意的是左边是孩子节点，代数要加一，右边是兄弟节点，代数不变 。
第二次搜索，找到最后一代，输出并计数
*/
DFS1(tree,1);//第一次搜索 找出共有多少代人
printf("家谱中共有%d代\n",cstree_high);
DFS2(tree,1);//总结最后一代人数和输出最后一代
printf("\n最后一代人个数是%d",num);
}