编写一个程序exp7-9.cpp，采用一棵二叉树表示一个家谱关系（由若干家谱记录构成，每个家谱记录由父亲、母亲和儿子的姓名构成，其中姓名是关键字），要求程序具有以下功能。
（1）文件操作功能：家谱记录的输入，家谱记录的输出，清除全部文件记录和将家谱记录存盘。要求在输入家谱记录时按从祖先到子孙的顺序输入，第一个家谱记录的父亲域为所有人的祖先。
（2）家谱操作功能：用括号表示法输出家谱二叉树，查找某人的所有儿子，查找某人的所有祖先（这里的祖先是指所设计的二叉树结构中某结点的所有祖先结点）。

加入了一个indentiy来区分身份，这样可以便于查找儿子和祖先

借鉴了相关的博客，对博主的showson（）函数作出了修改，通过在结构体里添加identify来辨别节点的身份，以实现该功能。参考文章：

用二叉树表示家谱关系并实现各种查找功能

家谱树的存储方式为：父亲的左节点为其妻子，无右节点；母亲无左节点，右节点为她的儿子。题目未做要求，忽略了家谱中存在女儿的情况。

#include<iostream>
#include <fstream>  
using namespace std;
typedef struct TNode{
	string data;
	TNode*left;
	TNode*right;
	int identify;//父亲为1，母亲为2,儿子为0
}TNode,*Tree;

bool onleft(TNode* T,string name){
	if (T == NULL) return 0;
	else if (T->data == name) return 1;
	else if (onleft(T->left,name)||onleft(T->right,name))return 1;
	else return false;
}
TNode*Find(Tree T,string name){
	if(T==NULL)return NULL;
	else if(T->data==name)return T;
	else if(onleft(T->left,name))return Find(T->left,name);
    else if(onleft(T->right,name))return Find(T->right,name);
	else return NULL;
}

void person(TNode*&father,string da,string mu,string so){
	father=new TNode();TNode*mum=new TNode();TNode*child=new TNode();
	father->data=da;father->left=mum;father->right=NULL;father->identify=1;
	mum->data=mu;mum->left=NULL;mum->right=child;mum->identify=2;
	child->data=so;child->left=child->right=NULL;child->identify=0;
}
void Add(Tree&T){
	string name1,name2,name3;
	cout<<"请依次输入父亲母亲孩子的姓名,用空格分开:";
	cin>>name1>>name2>>name3;
	//家谱为空
	if(T==NULL){person(T,name1,name2,name3);}
	else{
		TNode*father=Find(T,name1);
		if(father!=NULL){//若添加成员的父亲存在于家谱中
			if(father->left==NULL){
				//只有父亲（此时父亲还是作为孩子）则需添加母亲和孩子
				father->identify=1;//身份从儿子变为父亲
				TNode*mum=new TNode();TNode*child=new TNode();
				father->left=mum;
				mum->data=name2;mum->left=NULL;mum->right=child;mum->identify=2;
				child->data=name3;child->left=child->right=NULL;child->identify=0;
			}
			else {//家谱中有父亲母亲还有兄弟
				TNode*p=father->left;
				while(p->right!=NULL){
					p=p->right;
				}
				TNode*child2=new TNode();
				child2->data=name3;
				child2->left=child2->right=NULL;
				child2->identify=0;
				p->right=child2;
			}
			
			//不存在只有父母没有儿子的情况
		}
		else {
			cout<<"未找到祖先";
			return;
		}
	}
}
//家谱记录的输出
void DispTree1(Tree b){	//先序遍历
	if (b!=NULL){
		cout<<b->data;
		if (b->left!=NULL || b->right!=NULL){
			cout<<"(";
			DispTree1(b->left);
			if (b->right!=NULL) 
				cout<<",";
			DispTree1(b->right);
			cout<<")";			
		}
	}
	
}

void findsons(Tree T,string name){
	TNode*parent=Find(T,name);TNode*p=NULL;
	if(parent==NULL){cout<<"家谱中没有此人";return;}
	cout<<name<<"的所有儿子：";
	//parent为父亲、母亲、儿子的情况,p指向母亲
	if(parent->identify==1){p=parent->left;}
	if(parent->identify==2){p=parent;}
	if(parent->identify==0){cout<<"无儿子";return;}
	while(p->right){p=p->right;cout<<p->data<<" ";}
}

void findances(TNode* T, string name){
	TNode*p=T;
	if (p==NULL) {cout<<"家谱为空";return;}
	//如果要查找最开始的祖先及其妻子，自然他们俩无祖先
	if(p->data==name||p->left->data==name){
		cout<<"无祖先";
		return;
	}
	cout<<name<<"的祖先:";
	while(p){
		if(p->identify==1&&onleft(p->left,name)){
			cout<<p->data<<" ";
			p=p->left;
		}
		
		if(p->identify==2&&onleft(p->right,name)){
			cout<<p->data<<" ";
			//p=p->right;
		}
		if(p->data==name){return;}
		p=p->right;
		
	}
}

void ClearFile(const std::string& filename) {  
	std::ofstream file(filename, std::ios::out);  
	if (file.is_open()) {  
		file.close();  
	} else {  
		std::cout << "无法打开文件 " << filename << std::endl;  
	}  
}  
void SaveNode(ofstream& file, TNode* node) {  
	if (node == NULL) return;  
	file << node->data << " "; 
	if (node->left != NULL)  SaveNode(file, node->left);  	
	if (node->right != NULL) SaveNode(file, node->right);
}
void SaveToFile(const string& filename, Tree T) {  
	ofstream file(filename, ios::out);  
	if (file.is_open()) {  
		if (T != NULL) {  
			// 递归保存父亲节点信息  
			SaveNode(file, T);  
			
		} // 如果家谱树为空，则输出一个提示信息。  
		else {  
			file << "家谱为空" << endl;  
		}  
		file << endl;  
		file.close();  
	} 
	else {  
		cout << "无法打开文件 " << filename << endl;  
	}  
} 

int main(){
	Tree T=NULL;int choice;string name,name6;
	while(1){
		cout<<"1.输入家谱  2.输出家谱  3.查找儿子  4.查找祖先  5.清除文件  6.保存家谱并退出\n";
		cin>>choice;
		string filename = "family_tree.txt";
		switch (choice) {
		case 1:
			Add(T);
			break;
		case 2:
			DispTree1(T);
			break;
		case 3:
			cout<<"请输入你要查找＿＿的儿子：";
			cin>>name;
			findsons(T,name);
			break;
		case 4:{
			cout<<"请输入你要查找＿＿的祖先：";
			cin>>name6;
			findances(T,name6);
			break;
		}	
		case 5:
			ClearFile(filename);
			break;
		case 6:
			SaveToFile(filename,T);
			return 0;
			break;
		default:
			break;	
		}
		cout<<"\n";
	}
}