1、數(shù)據(jù)結(jié)構(gòu)（二叉樹）家譜管理系統(tǒng)摘 要 在本次家譜課程設(shè)計中采用二叉樹來表示家譜關(guān)系,由于在家譜中每個家族成員的子女不止一個,而雙親只有一個,所以采用二叉樹結(jié)構(gòu)來描述家族成員之間的關(guān)系。在家譜課程設(shè)計中還用到單鏈表,在設(shè)計中要將二叉樹存儲在文件中,最終要讀取文件中的記錄,要將文件中的數(shù)據(jù)還原到內(nèi)存中組成二叉樹結(jié)構(gòu),而文件中元素與元素之間的結(jié)構(gòu)是線性,而且直接對文件中的數(shù)據(jù)操作很不方便，所以將文件中的元素存儲在單鏈表中,再對單鏈表操作還原成內(nèi)存中的二叉樹。 在對家譜的文件操作中，為了還原家譜方便，采用按層遍歷的順序保存二叉樹中各結(jié)點的信息，在層次遍歷中，使用隊列來實現(xiàn)二叉樹的層次遍歷。 本家譜主要

2、包括兩個模塊，第一個是文件操作功能模塊，此模塊實現(xiàn)了家譜記錄輸入、讀取存盤記錄、清除家譜存盤記錄、添加成員、存盤 、修改家譜成員信息、刪除家譜成員等七大功能;第二個是家譜操作功能模塊，實現(xiàn)了查找某人記錄、查找某人的孩子、查找某人的祖先、用括號表示法輸出家譜、用凹入表示法輸出家譜等六大功能。 關(guān)鍵詞: Binarytnode save search addRecord del change clear 1 本程序功能框架圖 家譜管理系統(tǒng) 文件操作功能 家譜操作功能 家讀清添存修刪查查查用用譜取除加盤 改除找找找括凹記存家成家家某某某號入錄盤譜員 譜譜人人人表表輸記存成成記的的示示入 錄 盤員員

3、錄 孩祖法法記信子 先 輸輸錄 息 出出家家譜 譜 2 1( 項目總體設(shè)計 1.1 需求分析 (1) 文件操作功能:記錄輸入、記錄輸出、清除全部文件記錄和將家譜記錄存盤。初始化:用戶可輸入一個家族的族譜，輸入完成之后可保存在文件中。在其后的操作中，可從文件里讀取族譜信息、增加新的家族成員、修改已有的家族成員、刪除已存在的家族成員、可清除所有的家族成員信息。操作完成之后可保存在文件中。 (2) 家譜操作功能:用括號表示法和凹入法輸出家譜二叉樹，并能查找某人的配偶、所有孩子、所有祖先、兄弟等功能。 1.2系統(tǒng)功能模塊設(shè)計: 一(問題描述 本課程設(shè)計的主要問題是選擇一種數(shù)據(jù)結(jié)構(gòu)來描述家譜中家族成員之

4、間的關(guān)系，在此數(shù)據(jù)結(jié)構(gòu)上加之一些操作，選用特定的算法來實現(xiàn)家譜操作的功能和文件操作的功能。 二(基本要求 設(shè)計要求:編寫一個程序，采用一棵二叉樹表示一個家譜關(guān)系。 具體要求: (1) 文件操作功能:記錄輸入、記錄輸出、清除全部文件記錄和將家譜記錄存盤。 (2) 家譜操作功能:用括號表示法和凹入法輸出家譜二叉樹，并能查找某人所有的兒子，查找某人的所有祖先。 三(概要設(shè)計 1(數(shù)據(jù)結(jié)構(gòu)的設(shè)計 3 在家譜課程設(shè)計中采用二叉樹來表示家譜關(guān)系,由于在家譜中每個家族成員的子女不止一個,而雙親只有一個,所以采用二叉樹結(jié)構(gòu)來描述家族成員之間的關(guān)系。在家譜課程設(shè)計中還用到單鏈表,在設(shè)計中要將二叉樹存儲在文件中,

5、最終要讀取文件中的記錄,要將文件中的數(shù)據(jù)還原到內(nèi)存中組成二叉樹結(jié)構(gòu),而文件中元素與元素之間的結(jié)構(gòu)是線性,而且直接對文件中的數(shù)據(jù)操作很不方便，所以將文件中的元素存儲在單鏈表中,再對單鏈表操作還原成內(nèi)存中的二叉樹。 在對家譜的文件操作中，為了還原家譜方便，采用按層遍歷的順序保存二叉樹中各結(jié)點的信息，在層次遍歷中，使用隊列來實現(xiàn)二叉樹的層次遍歷。 2(算法的設(shè)計 本設(shè)計從總體上主要分2個模塊，分別是家譜操作模塊和文件操作模塊。 家譜操作模塊: 1)Binarytnode* Binarytree:bulid(Binarytnode* p,int num); /輸入家譜，形參p為二叉樹根結(jié)點的地址，形參

6、num為結(jié)點的編號，建立二叉樹并返回這棵二叉樹的根結(jié)點的地址。 算法:首先先建立一個二叉樹結(jié)點，提示用戶輸入該結(jié)點的姓名，將 用戶輸入的姓名寫入到該結(jié)點的成員變量name中，將形參num寫入到該結(jié)點的成員變量number中，將雙親結(jié)點的地址賦給結(jié)點的成員變量的雙親指針，提示用戶是否有左孩子，若有左孩子則遞歸調(diào)用通過形參將雙親結(jié)點的地址傳遞過去，遞歸調(diào)用返回的地址賦給它的雙親結(jié)點的左孩子指針，右孩子的建立同理可得，通過遞歸來建立整棵二4 叉樹。 2)Binarytnode* Binarytree:searchRecord(string name); /形參name要查找的姓名，按姓名查找某人記錄

7、，若找到記錄則返回該節(jié)點的地址，反之，則返回一個空指針。 算法:通過層次遍歷來和每個結(jié)點的成員變量name比較若姓名匹配則返回該節(jié)點的地址。首先判斷二叉樹的根結(jié)點是否為為空，若為空則不進(jìn)行查找。反之，則將根結(jié)點入隊列，然后進(jìn)入一個循環(huán)體，使循環(huán)為真的條件是隊列不為空，循環(huán)體語句是取隊頭元素，然后對該元素的判斷它的成員變量name是否與查找的姓名相匹配。若匹配則返回該結(jié)點的地址，若不匹配，則刪除隊頭元素將它的左右孩子入隊列(左右孩子不空的情況下)，進(jìn)行循環(huán)。若直到遍歷完整棵子樹都還沒找到，則返回一個空指針。 3)void Binarytree:searchChild(string name);

8、/形參name要查找的姓名，按姓名查找某人的孩子，若找到記錄則顯示該節(jié)點孩子的姓名，反之，則提示未找到信息。 算法:調(diào)用Binarytnode* searchRecord(string name)函數(shù)查找與參數(shù) name相匹配的記錄，然后判斷其返回的地址是否為空，若為空則不進(jìn)行查找其子女，若不為空，則輸出其左右孩子(左右孩子不空的情況下)。 4)void Binarytree:searchParent(string name); /形參name要查找的姓名，按姓名查找某人的祖先，若找到記錄則按輩份從小到大顯示該節(jié)點的祖先，反之，則提示未找到信息。 算法:調(diào)用Binarytnode* searc

9、hRecord(string name)函數(shù)查找與參數(shù) 5 name相匹配的記錄，然后判斷其返回的地址是否為空，若為空則不進(jìn)行查找其雙親，若不為空，則用循環(huán)通過雙親指針按輩分從小到大輸出雙親的姓名，直到雙親的地址為空，結(jié)束循環(huán)。 5)void Binarytree:addRecord(string parent,string name); /插入家族成員記錄，形參parent為要插入的家族成員的雙親姓名，形參name為要插入家族成員的姓名。 算法:調(diào)用Binarytnode* searchRecord(string name)函數(shù)查找與參數(shù) name相匹配的記錄，然后判斷其返回的地址是否為空，

10、若為空則不進(jìn)行插入操作，若不為空，則判斷其是否左子樹是否為空，若為空則建立一個結(jié)點將參數(shù)name賦給結(jié)點的成員變量name中去，然后通過它的雙親結(jié)點的編號計算出它的編號為2*number，將編號、雙親的地址分別賦給它的成員變量number、parent 。若不為空，再判斷它的右子樹是否為空，若為空則按建立左孩子的同樣的方法建立右孩子。若還為空，則說明左右子樹都不為空，則不允許添加記錄。 6)void Binarytree:change(string name); /修改家族成員的信息，行參name為要修改的家族成員的姓名。 算法:調(diào)用Binarytnode* searchRecord(stri

11、ng name)函數(shù)查找與參數(shù) name相匹配的記錄，然后判斷其返回的地址是否為空，若為空則不進(jìn)行修改操作，若不為空，則將參數(shù)name賦給它的成員變量name中。 7)void Binarytree:del(string name); /刪除家族成員，行參為要刪除的家族成員的姓名。 算法:調(diào)用Binarytnode*searchRecord(string name)函數(shù)查找與參數(shù) name相匹配的記錄，然后判斷其返回的地址是否為空，若為空則不進(jìn)6 行刪除操作，若不為空，則判斷其左右子樹是否為空，若左右子樹都為空，則將其雙親結(jié)點的對應(yīng)的左或右孩子指針賦為空，釋放其結(jié)點的空間。反之，則不刪除該結(jié)點

12、。該函數(shù)只允許刪除葉子結(jié)點。 8) Binarytnode* Binarytree:load(node* head, Binarytnode* parent) / 讀取存盤記錄，將單鏈表還原為二叉樹，返回該二叉樹的根結(jié)點的地址。 算法:通過遞歸調(diào)用來重建二叉樹。首先，調(diào)用函數(shù)node* node: read()，該函數(shù)的作用是將文件中二叉樹的信息存放在單鏈表中，返回單鏈表的頭指針的地址。若返回的指針為空，則，不進(jìn)行讀取存盤記錄操作，若不空，則建立一個二叉樹結(jié)點，取單鏈表的的一個節(jié)點，將其結(jié)點的信息寫入到二叉樹結(jié)點的相應(yīng)的成員變量中，通過編號計算出該左孩子的的編號(由于孩子的編號肯定小于雙親的編

13、號，而編號在單鏈表是從小到大排列的)從當(dāng)前單鏈表的結(jié)點往下尋找編號相匹配的結(jié)點 若找到，則將該結(jié)點的地址和二叉樹結(jié)點的地址通過函數(shù)的參數(shù)遞歸調(diào)用該函數(shù)返回的地址賦給二叉樹的左孩子指針，右子樹的建立同左子樹的建立同理。建立完整個二叉樹后，返回該二叉樹根結(jié)點的地址。 9)void Binarytree:displaytree1(Binarytnode* root) /括號法顯示, 形參root為根結(jié)點的的地址。 算法:用遞歸來實現(xiàn)二叉樹的括號法表示。首先，判斷二叉樹根結(jié)點是否為空，若為空，則不顯示二叉樹，若不為空，則顯示根結(jié)點的數(shù)據(jù)，輸出(,再遞歸調(diào)用顯示它的左孩子(左孩子不空的情況下)，7 然后

14、輸出，再遞歸調(diào)用顯示它的右孩子(右孩子不空的情況下)，然后輸出)。 10)void Binarytree:displaytree2(Binarytnode* root,int n); /凹入法顯示，形參root為根結(jié)點的地址,行參n為縮進(jìn)量。 算法:用遞歸來實現(xiàn)二叉樹的凹入法表示。首先，判斷二叉樹是否為空，若為空，則不顯示二叉樹，設(shè)置輸出寬度(由形參 n決定)，遞歸顯示它的左孩子輸出寬度為它雙親結(jié)點的輸出寬度的2倍，換行，通力遞歸顯示它的右孩子，換行。 文件操作模塊: 1) void Binarytree:save(Binarytnode* root) /存盤，將家譜保存到文件中，行參為二叉樹

15、根結(jié)點的地址。 算法:為了還原二叉樹方便采用按層次遍歷(其記錄按編號由從小大到大的順序存儲在文件中)的順序來保存二叉樹的信息。首先，先清空原來文件的內(nèi)容，判斷二叉樹根結(jié)點的是否為空，若為空，則不進(jìn)行存盤操作，若不為空，將根結(jié)點入隊列，進(jìn)入循環(huán)，循環(huán)為真的條件是對列為空，循環(huán)體為，取隊頭元素，將對頭元素的姓名和編號寫入文件，然后刪除對頭元素，再將其左子樹和右子樹入隊列(若左右子樹存在的情況下)。當(dāng)循環(huán)結(jié)束的時候，整棵二叉樹都保存在文件中(遍歷結(jié)束)。 2)void Binarytree:clear();/清除文件內(nèi)容。 算法:刪除存檔文件jiapu.txt。并建立一個空文件jiapu.txt。

16、2) node* node: read(); /將文件中二叉樹的信息存放在單鏈表中，返回單鏈表的頭指針的地址 8 算法:首先，判斷文件是否為空，若文件為空，則不進(jìn)行讀取操作，返回一個空指針若不空，則將二叉樹按文件中的排列順序存儲在單鏈表中，并返回該單鏈表的頭指針的地址。 2(詳細(xì)實現(xiàn)步驟、流程圖、代碼: 2.1實現(xiàn)步驟: 收集資料 1)2)概要設(shè)計、詳細(xì)設(shè)計 編碼 3)4)測試 2.2流程圖 開始 Meun Binarytree:bulid(輸入) Save Load/read Clear choose Add record Search Del Change Y Meun N 結(jié)束 9 1)

17、主菜單 代碼: #include Binarytree.h #include #include void menu() coutendl; cout *歡迎使用家譜管理系統(tǒng)*endl; cout * *endl; cout * &文件操作功能& &家譜操作功能& *endl; cout * *endl; cout * 家譜記錄輸入-1 * 查找某人記錄-8 *endl; cout * 讀取存盤記錄-2 * 查找某人的孩子-9 *endl; cout * 清除家譜存盤記錄-3 * 查找某人的祖先-c *endl; cout * 添加成員-4 * 用括號表示法輸出家譜-k *endl; cout

18、* 存盤-5 * 用凹入表示法輸出家譜-n *endl; cout * 修改家譜成員信息-6 * *endl; cout * 刪除家譜成員-7 * *endl; cout * 10 *endl; cout *顯示菜單-m*endl; cout *退出-0*endl; coutendl; void main() char s; menu(); /顯示菜單 string name,str,name2; Binarytree tree; /建立一個二叉樹對象 node f; /建立一個單鏈表 while(1) cout請選擇相應(yīng)功能的序號按enter進(jìn)入操作:str; if(str.size()!=

19、1)s=m; else s=str0; /用于判斷用戶是否有錯誤操作 switch(s) case 1 : cout輸入姓名:; tree.outroot()=tree.bulid(NULL,1);break;/輸入家譜 case 2 : if(f.read()=NULL) cout文件內(nèi)容為空!無法讀取數(shù)據(jù)!endl;/判斷單鏈表是否為空 else tree.outroot()=tree.load(f.read(); cout家譜已載入!endl; break; /將文件中內(nèi)容還原為二叉樹 case 8 : coutname; Binarytnode* p; p=tree.searchRec

20、ord(name); if(p!=NULL)coutGetname()endl;break;/查找某人的信息 case 9 : coutname; tree.searchChild(name);break;/查找某人孩子的信息 case c : coutname; tree.searchParent(name);break;/查找某人祖先信息 case k : tree.displaytree1(tree.outroot();coutendl;break;/用括號法表示 case n : tree.displaytree2(tree.outroot(),0);break;/用凹入法表示 cas

21、e 5 : if(tree.outroot()=NULL) cout你沒有輸入家譜記錄!無法保存家譜記錄!endl; else tree.save(tree.outroot();break;/家譜保存 case 3 : tree.clear(); cout家譜記錄清除成功!endl; break;/刪除記錄文件 case m : menu();break; case 4 : if(tree.outroot()!=NULL) cout請輸入要添加成員的姓字:name; cout請輸入該成員雙親的姓名:name2; tree.addRecord(name2,name); else cout家譜記錄

22、為空!無法完成添加操作!endl;break; case 6 : if(tree.outroot()!=NULL) 11 cout輸入要修改成員的姓名:name; tree.change(name);/調(diào)用 else cout家譜記錄為空!無法完成修改操作!endl;break; case 7 : if(tree.outroot()!=NULL) cout輸入要刪除成員的姓名:name; tree.del(name);/調(diào)用刪除函數(shù) else cout家譜記錄為空!無法完成刪除操作!endl;break; case 0 : exit(0); /退出 default: cout錯誤操作!name

23、; /輸入姓名 m-Getname()=name; m-parent()=p; /存放雙親結(jié)點的地址 12 m-Getnumber()=num; /獲取節(jié)點的編號 coutGetname()n; if(n=Y|n=y) /判斷是否有右子樹 cout輸入他左孩子的姓名:left()=bulid(m,2*num);/遞歸調(diào)用建立左子樹 else m-left()=NULL;/無左子樹則左孩子指針賦為空 coutGetname()是否有右孩子(Y/N):n; if(n=Y|n=y)/判斷是否有左子樹 cout輸入他右孩子的姓名:right()=bulid(m,2*num+1);/遞歸調(diào)用建立右子樹

24、else m-right()=NULL;/無左子樹則左孩子指針賦為空 return m; 3) 添加成員 13 主要實現(xiàn)代碼 void Binarytree:addRecord(string parent,string name)/(功能4的主要實現(xiàn)函數(shù)) /插入家族成員記錄，形參parent為要插入的家族成員的雙親姓名，形參name為要插入家族成員的姓名 Binarytnode* q; q=searchRecord(parent); if(q!=NULL) Binarytnode* p;/定義指針 p=new Binarytnode; if(q-left()=NULL)/左子樹 q-left

25、()=p; p-Getname()=name;/新加結(jié)點的值 p-Getnumber()=2*(q-Getnumber();/新加結(jié)點編號 p-parent()=q; cout添加成功!right()=NULL)/右子樹操作 q-right()=p; p-Getname()=name; p-Getnumber()=2*(q-Getnumber()+1; p-parent()=q; cout添加成功!right()!=NULL&q-left()!=NULL)/左子樹不等于空值 cout無法添加成員!endl; 4) 存盤 14 主要實現(xiàn)代碼: void Binarytree:save(Binar

26、ytnode* root)/以層次遍歷的順序保存二叉樹各結(jié)點(功能5的主要實現(xiàn)函數(shù)) fstream outfile;/定義文件 outfile.open(jiapu.txt,ios:out); outfile.close(); system(del jiapu.txt);/清空文件內(nèi)容 queueQ;/Q為隊列,隊列元素是二叉樹結(jié)點指針 Binarytnode* p; if(root!=NULL) Q.push(root);/根結(jié)點入隊列 while(!Q.empty()/判斷文件 p=Q.front();/取隊頭元素 outfile.open(jiapu.txt,ios:app|ios:o

27、ut); if(!outfile) cout文件不能打開!endl; abort(); outfileGetname() Getnumber()left()!=NULL) Q.push(p-left();/左孩子結(jié)點入隊列 15 if(p-right()!=NULL) Q.push(p-right();/右孩子節(jié)點入隊列 cout已保存到文件!endl; 5) 修改家譜成員信息 主要實現(xiàn)代碼: void Binarytree:change(string name)/修改家譜成員的姓名(功能6的主要實現(xiàn)函數(shù)) string str; Binarytnode* p; p=searchRecord(

28、name); if(p!=NULL) cout請輸入修改后的姓名:str; p-Getname()=str; cout記錄修改成功!left()=NULL&p-right()=NULL) q=p-parent(); if(q-left()=p) q-left()=NULL; else q-right()=NULL; delete p; cout記錄已刪除!Getnext(); p-Getname()=head-Getname(); p-Getnumber()=head-Getnumber(); p-parent()=parent; while(m!=NULL&m-Getnumber()!=2*

29、(head-Getnumber() m=m-Getnext(); if(m!=NULL) p-left()=load(m,p);/用遞歸建立左子樹 else p-left()=NULL; m=head-Getnext(); while(m!=NULL&m-Getnumber()!=2*(head-Getnumber()+1) 18 m=m-Getnext(); if(m!=NULL) p-right()=load(m,p);/用遞歸建立右子樹 else p-right()=NULL; return p; 8)查找某人記錄 主要實現(xiàn)代碼: Binarytnode* Binarytree:sear

30、chRecord(string name)/用層次遍歷來查找某個記錄(功能8的主要實現(xiàn)函數(shù)) queueQ; /Q為隊列,隊列元素是二叉樹結(jié)點指針 Binarytnode* p; if(this-outroot()!=NULL) Q.push(this-outroot();/根結(jié)點入隊列 while(!Q.empty() p=Q.front();/取隊頭元素 if(p-Getname().compare(name)=0)/判斷是否找到結(jié)點的值相同 19 return p; Q.pop();/刪除隊頭元素 if(p-left()!=NULL) Q.push(p-left();/左孩子結(jié)點入隊列

31、if(p-right()!=NULL) Q.push(p-right();/右孩子節(jié)點入隊列 cout未找到相匹的姓名!left()!=NULL) coutGetname()的左孩子的姓名為:endl; coutleft()-Getname()endl;/顯示它的左孩子 else coutGetname()無左孩子!right()!=NULL) coutGetname()的右孩子的姓名為:endl; coutright()-Getname()endl;/顯示它的右孩子 else coutGetname()無右孩子!parent()=NULL)cout此人沒有雙親!endl; else cout

32、此人的祖先按輩份從小到大排序為:parent(); 21 while(p!=NULL) coutGetname()parent();/指針移動到它的雙親節(jié)點 coutendl; 11)括號輸出法 主要實現(xiàn)代碼: void Binarytree:displaytree1(Binarytnode* root) /用遞歸來實現(xiàn)括號法表示(功能k的主要實現(xiàn)函數(shù)) if(root!=NULL) coutGetname();/輸出根結(jié)點 if(root-right()!=NULL|root-left()!=NULL)/判斷左子樹或者右子樹是否為空 coutleft(); coutright(); cout); 22 12)用凹入法輸出家譜 主要實現(xiàn)代碼: void Binarytree:displaytree2(Binarytnode* root,int n)/