先看实验要求：
项目名称：基于二叉树的家谱系统
项目内容：采用一棵二叉树来表示一个家谱关系，一个家谱可表示为一颗树，首先将其转换成一颗二叉树表示，如下图为红楼梦家谱的一部分：

图1.1 家谱的树形表示

图1.2 家谱的二叉树表示
要求完成的功能如下：
（1）输入一颗二叉树的括号表示法，完成树的构建
（2）使用后序遍历递归算法遍历二叉树并输出
（3）使用先序遍历非递归算法遍历二叉树并输出
（4）指定家谱中的某一成员，输出其所有长辈

由题目可见，我们需要将这个族谱先转化为字符串表示的二叉树，然后再用代码的方式来建立对应的二叉树。
我们先把对应的字符串表示的树表示出来：

然后将已知的图和字符串放在一起：

我们观察其中的规律：

发现：右子树的都是同一个辈分的，左子树的每次有一个分叉，它的辈分就低一级，如：BDE是同一个辈分的，假设我们规定根节点的辈分为1，辈分数依次递增，表示它的实际辈分等级越低的话，那么，BDE处在辈分为2的层次，其中C的辈分为3，最低；
为了方便观察，我们再添加几个节点来理解：



可知：AFH在同一个辈分为1的级别上；
BDEGLM都在辈分为2的级别上；
CK都在辈分为3的级别上；
这样，我们就对这个二叉树的表示家谱的方法有了基本的规律认识，下面就是开始建立我们的族谱二叉树了：
在建立之前，笔者在之前写过一将字符串表示的二叉树转化为代码实现的二叉树的博客，为了更好地理解二叉树的建立，请查看原博文：

除特别声明，本站所有文章均为原创，如需转载请以超级链接形式注明出处：SmartCat's Blog