2
《数据结构与算法》实验报?/p>
专业
班级
姓名
学号
实验项目
实验一
二叉树的应用
实验目的
1
、进一步掌握指针变量的含义及应用?/p>
2
、掌握二叉树的结构特征,以及各种存储结构的特点及使用范围?/p>
3
、掌握用指针类型描述、访问和处理二叉树的运算?/p>
实验内容
题目
1:
编写一个程序,采用一棵二叉树表示一个家谱关系。要求程序具有如下功能:
?/p>
1
)用括号表示法输出家谱二叉树?/p>
?/p>
2
)查找某人的所有儿子,
?/p>
3
)查找某人的所有祖先?/p>
算法设计分析
(一)数据结构的定义
为了能够用二叉树表示配偶、子女、兄弟三种关系,特采用以下存储关系,则能在二叉树?/p>
实现家谱的各项运算?/p>
?/p>
?/p>
?/p>
1
子妻
1
?/p>
2
?/p>
1
子妻
2
?/p>
2
二叉树型存储结构定义为:
typedef
struct
SNODE
{char name[MAX];
//
人名
struct SNODE *left;
//
指向配偶结点
struct SNODE *right;
//
指向兄弟或子女结?/p>
}FNODE;
(二)总体设计
实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函
数、选择界面函数七个函数共同组成。其功能描述如下?/p>
?/p>
1
)主函数:统筹调用各个函数以实现相应功能
void main()
?/p>
2
)家谱建立函数:与用户交互建立家族成员对应关?/p>
void InitialFamily(FNODE *&head) //
家谱建立函数
?/p>
3
)家谱输出函数:用括号表示法输出家谱
输出形式为:父和母(?/p>
1
和子?/p>
1
(孙
1
?/p>
,子
2
和子?/p>
2
(孙
2
?/p>
?/p>
void PrintFamily(FNODE *head)
//
家谱输出函数