遍历算法分析与设计论文

对于一般的家谱(一般的多分支树)，我们可以清楚地看到等级关系。树的层数代表代数(有多少代)，树的最后一层代表最后一代。由于多分支链表方法不方便，我们被迫采用子兄弟表示法(二叉链表法)。

假设我的家谱是这样的:

转换为子兄弟表示法后，它是这样的:

？我们需要做的是:这个时候，我们需要搞清楚到底有多少代，最后作为一代走出来。

？如果按照第一张图代数就是树的高度，那么最后一代就是树的最后一层，但是二叉链表法没有第一张图那么直观，但是只要抓住了二叉链表法的本质还是很清楚的。根据子兄弟表示的特点，(见二叉链表方法的示意图)节点3的左子树保存其子节点，节点3的右子树保存其表兄弟节点(见第一个示意图)。假设我们的每个节点都有一个变量存储它是哪一代，那么从节点1开始，如果我们要找到节点10是哪一代，我们应该这样做:节点1是第一代，那么经过节点5是第二代，然后我们看到节点10是第三代。因为第I个节点的左子树是他的孩子，既然是孩子，代数就一定是+1，而右子树和第I个节点(表亲)是同一代，所以不能加1。本质上是代数+1往左，代数往右不变。这就是这个题目的思路。通过这个方法可以知道有多少代，每个节点都保存了代数信息(用变量保存)。只需再次遍历树，输出最后一代节点。清楚了吗？我清楚的时候就开始写程序了。