用二叉樹表示家譜關系并實現各種查找功能

我有借鑒的博客

編寫一個程序exp7-9.cpp，采用一棵二叉樹表示一個家譜關系（由若干家譜記錄構成，每個家譜記錄由父親、母親和兒子的姓名構成，其中姓名是關鍵字），要求程序具有以下功能。
（1）文件操作功能：家譜記錄的輸入，家譜記錄的輸出，清除全部文件記錄和將家譜記錄存盤。要求在輸入家譜記錄時按從祖先到子孫的順序輸入，第一個家譜記錄的父親域為所有人的祖先。
（2）家譜操作功能：用括號表示法輸出家譜二叉樹，查找某人的所有兒子，查找某人的所有祖先（這里的祖先是指所設計的二叉樹結構中某結點的所有祖先結點）。

我的樹是這樣的（借鑒別人的）

文件里存的樹是這樣的

存家庭要存三個人。

保存到文件

我的代碼是這樣的

#include<iostream> #include<bits/stdc++.h> using namespace std; string s[100];//讀文件存節點 int i = 0;//讀文件時記錄節點個數 bool flag = false;//刪除清空后用來確定 創建ancestor struct TreeNode{string name;struct TreeNode *lChild;struct TreeNode *rChild; };//文件操作： //家譜記錄的輸入(要求在輸入家譜記錄時按從祖先到子孫的順序輸入， //第一個家譜記錄的父親域為所有人的祖先。) //輸入存父母孩子 TreeNode *savePerson(){cout<<"輸入父母孩子名字，以空格分開:";string s1,s2,s3;cin>>s1>>s2>>s3;TreeNode *father = new TreeNode;father->lChild = father->rChild = NULL;father->name = s1;TreeNode *mother = new TreeNode;mother->lChild = mother->rChild = NULL;mother->name = s2;TreeNode *son = new TreeNode;son->lChild = son->rChild = NULL;son->name = s3;father->lChild = mother;mother->rChild = son;return father; }//女只用右孩子，男左邊妻子，右邊兒子//遍歷查找人名 TreeNode* Find(TreeNode *node,string name){if(node==NULL)return NULL;if(node->name==name)return node;TreeNode *temp = Find(node->lChild,name);if(temp!=NULL)return temp;temp = Find(node->rChild,name);if(temp!=NULL)return temp;return NULL; }//存小孩父母 如果同一父母 void save(TreeNode *root){//這是家譜中已有祖先的情況TreeNode *fam = savePerson();//父是根節點TreeNode *result = Find(root,fam->name);if(result!=NULL){if(result->lChild==NULL){//沒老婆兒子 result是在家譜找到的父節點result->lChild = fam->lChild;}else{//有妻子兒子TreeNode *temp = result->lChild;//指向父老婆（母）while(temp->rChild!=NULL){temp = temp->rChild;}temp->rChild = fam->lChild->rChild; //fam中的孩子}}else if(result==NULL){cout<<"沒有找到你的祖先,不存入"<<endl;} } //-------------------------------------------------------------------------------------//家譜記錄的輸出 void showFamily(TreeNode *node){if(node==NULL)return;if(node->lChild!=NULL){cout<<node->name<<" ";TreeNode *temp = node->lChild;while(temp!=NULL){cout<<temp->name<<" ";temp = temp->rChild;}cout<<endl;TreeNode *son = node->lChild->rChild;while(son!=NULL){showFamily(son);son = son->rChild;}} }//清除全部文件記錄//釋放樹 void freeTree(TreeNode *node){if(node==NULL)return;freeTree(node->lChild);freeTree(node->rChild);delete(node);node=NULL; } void destroyFile(){fstream file("family.txt",ios::out);cout<<"清除文件完成"<<endl; }//將家譜記錄存盤 // 樹保存到文件夾 void saveInFile(TreeNode *node){ofstream of("family.txt",ios::app);if(node==NULL){ of<<"NULL"<<" ";return;}of<<node->name<<" ";of.close();saveInFile(node->lChild);saveInFile(node->rChild); }//從文件讀樹 void readFile(){//把文件中的樹節點讀進string數組ifstream f("family.txt",ios::in);int i = 0;while(!f.eof()){f>>s[i];i++;}f.close(); } //建樹 TreeNode* BuildTree(){if(s[i]=="NULL"){i++;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!return NULL;}TreeNode *node = new TreeNode;node->lChild = node->rChild = NULL;node->name = s[i];i++;node->lChild = BuildTree();node->rChild = BuildTree();return node; }//-------------------------------------------------------// //用括號表示法輸出家譜二叉樹 void printBinaryTree(TreeNode *node){if(node){cout<<node->name; //根節點存在就輸出}else return; //不存在，則返回if(node->lChild!=NULL||node->rChild!=NULL)cout<<'('; //左右子樹存在任一就輸出（else return; //左右子樹都不存在返回if(node->lChild){printBinaryTree(node->lChild); //左子樹存在}if(node->rChild){cout<<','; printBinaryTree(node->rChild);}cout<<')'; }void ShowSon(TreeNode *node,string name){//這里要判斷父親還是母親 父親肯定有左孩子，母親肯定沒左孩子TreeNode *parent = Find(node,name);if(parent==NULL){cout<<"查無此人"<<endl;return;}TreeNode *temp = NULL;if(parent->lChild==NULL){//bug這樣有要是你的兄弟沒老婆，會把兄弟當成孩子的 temp = parent->rChild;//指向第一個孩子cout<<name<<"的孩子是：";while(temp!=NULL){cout<<temp->name<<" ";temp = temp->rChild;}cout<<endl;}else if(parent->lChild!=NULL){temp = parent->lChild->rChild;cout<<name<<"的孩子是：";while(temp!=NULL){cout<<temp->name<<" ";temp = temp->rChild;}cout<<endl;} }// //查找某人的所有祖先（這里的祖先是指所設計的二叉樹結構中某結點的所有祖先結點） bool ShowAllFather(TreeNode *node,string name){if(node==NULL)return false;if(node->name==name)return true;if(ShowAllFather(node->lChild,name)||ShowAllFather(node->rChild,name)){cout<<node->name<<" ";return true;}return false; }int main(){TreeNode *ancestor = NULL;char a;while(true){cout<<"選擇1創建新家譜，選擇2用文件中存儲的家譜"<<endl; cin>>a;if(a=='1'){ancestor = savePerson(); ;break;}else if(a=='2'){fstream f("family.txt");f.seekg(0,ios::end);streampos fp = f.tellg();if(int(fp)==0){cout<<"文件為空"<<endl;}else{readFile();ancestor = BuildTree();break;}f.close();}else cout<<"輸入錯誤"<<endl;}cout<<"-----------------------------家譜------------------------------"<<endl;while(true){char choose1 = -1;cout<<"按1選擇文件操作，按2選擇家譜操作，按3退出。你的選擇是：";cin>>choose1;if(choose1=='1'){while(true){char choose2 = '-1';cout<<"按1選擇輸入家譜，按2選擇輸出家譜，按3選擇清除記錄返回，按4選擇保存記錄后返回。你的選擇是：";cin>>choose2;if(choose2=='1'){if(flag==false){save(ancestor);}else if(flag==true){ancestor = savePerson();}}else if(choose2=='2'){if(ancestor==NULL){cout<<"家譜為空"<<endl;}else{showFamily(ancestor);cout<<endl;}}else if(choose2=='3'){freeTree(ancestor);destroyFile();ancestor = NULL;flag = true;break;}else if(choose2=='4'){if(ancestor==NULL){cout<<"家譜為空"<<endl;}else{//如果不為空，先清空文件夾fstream f("family.txt",ios::out);f.close();saveInFile(ancestor);cout<<"保存成功"<<endl;break; } }else {cout<<"輸入錯誤"<<endl;}}}else if(choose1=='2'){while(true){char choose3 = '-1';cout<<"按1選擇括號表示法輸出，按2選擇查找某人的所有兒子，按3選擇查找某人的所有祖先，按4選擇返回。你的選擇是：";cin>>choose3;if(choose3=='1'){if(ancestor==NULL){cout<<"家譜為空"<<endl;}else{printBinaryTree(ancestor);cout<<endl;}}else if(choose3=='2'){if(ancestor==NULL){cout<<"家譜為空"<<endl;}else{cout<<"請輸入你要查找誰的兒子的名字"<<endl;string s ;cin>>s;ShowSon(ancestor,s);cout<<endl;}}else if(choose3=='3'){if(ancestor==NULL){cout<<"家譜為空"<<endl;}else{cout<<"請輸入你要查找誰的全部祖先"<<endl;string s;cin>>s;cout<<s<<"的全部祖先是：";ShowAllFather(ancestor,s);cout<<endl;}}else if(choose3=='4'){break;}else {cout<<"輸出錯誤"<<endl;}}}else if(choose1=='3'){break;}else cout<<"輸出錯誤"<<endl;cout<<"----------------------------------------------------------"<<endl;}//------------------------------------------------------------------------system("pause");return 0; }

總結

以上是生活随笔為你收集整理的二叉树家谱关系实验报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。