1、 设计目的与内容
1.1 问题七：用二叉树表示家谱关系并实现各种查找功能
目的：掌握二叉树遍历算法的应用，熟练使用先序、中序、后序 3 种递
归遍历算法进行二叉树问题的求解。
内容：采用一棵二叉树表示一个家谱关系，要求具有以下功能：①、文
件操作功能，即家谱记录的输入、家谱记录的输出、清除全部文件记录和
将家谱记录存盘。②、家谱操作功能，即用括号表示法输出家谱二叉树、查
找某人的所有儿子、查找某人的所有祖先。
需求分析：
模块 1：功能选择
分析：功能选择模块函数，主要提供 1：文件操作 2：家谱操作 两个
功能模块让用户选择。输入数字 1 的时候，出现界面 1：输入 2：输出 3：
清盘 4：更换始祖 0：存盘返回。返回后输入数字 2，出现界面 1：括号表
示法 2：二叉树表示法 3：找某人的所有儿子 4：找某人所有祖先 ，用户
可以根据自己的需求进行选择。
模块 2：二叉树的建立
分析：二叉树的结点有三个域，数据域和两个指针域，数据域用来存放
数据，两个指针域用来分别存放指向该结点左右孩子的指针。并且还有个
root 结点，称二叉树的根节点。
模块 3：家族成员信息的输入与输出
分析：依次输入一个家庭的父亲、母亲和孩子的姓名，先用定义好的结
构体数组存储数据，并通过 i/o 流将它们保存在相应的文件里。通过循环依
次输出 fam 数组中的数据，即输出每个家庭的父亲、母亲和孩子的姓名。
模块 4：查找某人的儿子
分析：首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就
输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就
输出这个父亲没有妻子，如果存在就查找左孩子的右孩子，没有右孩子就
输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。
模块 5：查找某人的祖先
分析：采用后序非递归遍历方法输入从根结点到*s 结点的路径，首先输
入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它
的所有祖先。
模块 6：二叉树的各种表示法
分析：①、括号表示法：通过先序遍历，先输出根节点，若根节点的左
孩子结点或右孩子结点非空，则先输出（，然后递归左子树；如果根节点的
评论1