一、实验目的与要求

1、掌握二叉树的存储结构，以便在实际背景下灵活运用。
2、掌握二叉树的建立，以及按层次遍历方法。
3、能对二叉树进行常见的应用。

二、实验内容

★★★运用二叉树的存储方法建立一棵二叉家族树，并进行按层次遍历输出，求出指定结点的祖先。

三、实验指导

★★★1．实验描述

王大爷的祖父王威育有两个儿子，大儿子叫王喜，是王大爷的父亲，二儿子叫王嘉，是王大爷的叔叔。王大爷有一个弟弟叫王石，还有两个堂弟妹，分别叫王磊、王燕。王大爷本人有两个儿子和一个孙女，分别叫王波、王涌和王晓蕊。王石有一个儿子叫王海。王磊有一个儿子和一个孙子，分别叫王涛和王晓帆。王大爷本人叫王硕。
（1）王大爷家的家谱按各成员的年龄顺序及父子关系构成的二叉家族树如图5.1所示。请设计算法，帮助王大爷建立他家的二叉家族族谱树，并将家族族谱树以层次遍历的方式输出。
（2）自从王大爷家的家族族谱树建立后，对此感兴趣、喜欢查看家谱的人增多。王海就想查看自己的所有祖先成员都有谁。请设计算法，帮助王海找出他的所有祖先成员。

图5.1 王家的二叉家族树

参考代码