《二叉排序樹的操作》課程設(shè)計(jì)報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：31 大?。?.17MB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩30頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　本科生課程設(shè)計(jì)論文　　《數(shù)據(jù)結(jié)構(gòu)與算法》　　題目：二叉排序樹的操作　　課程設(shè)計(jì)任務(wù)書　　目錄

2、;　　目錄2　　第一章需求分析3　　第二章總體設(shè)計(jì)4　　第三章抽象數(shù)據(jù)類型定義5　　3.1 二叉樹BT抽象數(shù)據(jù)類型的設(shè)計(jì)5　　3.2

3、BT抽象數(shù)據(jù)類型的設(shè)計(jì)6　　第四章詳細(xì)設(shè)計(jì)7　　4.1工程視圖7　　4.2類圖視圖7　　4.3函數(shù)的調(diào)用關(guān)系8　　4.4主程序流程圖9<

4、;/p>　　4.5主要算法的流程圖9　　第五章測試13　　第六章總結(jié)20　　附錄：程序代碼21　　需求分析</p

5、>　　二叉排序樹的操作　　以二叉鏈表表示二叉排序樹，在此基礎(chǔ)上實(shí)現(xiàn)二叉排序樹的操作。　　要求設(shè)計(jì)類（或類模板）來描述二叉排序樹，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：　　創(chuàng)建二叉排序樹

6、;　　輸出二叉排序樹　　在二叉排序樹中查找給定值　　在二叉排序樹中插入新結(jié)點(diǎn)　　在二叉排序樹中刪除給定值　　并設(shè)計(jì)主函數(shù)測試該類（或類模板）。<

7、b>　　第二章總體設(shè)計(jì)　　系統(tǒng)的功能結(jié)構(gòu)：設(shè)置二叉排序樹根結(jié)點(diǎn)、添加二排序叉樹結(jié)點(diǎn)、刪除二排序叉樹結(jié)點(diǎn)、查找給定的二叉樹結(jié)點(diǎn)、輸出二排序叉樹、退出。　　功能說明：　　設(shè)置二叉排序樹根結(jié)點(diǎn)：為新創(chuàng)建的二叉排序樹創(chuàng)建根節(jié)點(diǎn)。&l

8、t;p>　　添加二排序叉樹結(jié)點(diǎn)：需要輸入創(chuàng)建節(jié)點(diǎn)的數(shù)目，然后創(chuàng)建一定數(shù)目的二叉排序樹結(jié)點(diǎn)。　　刪除二排序叉樹結(jié)點(diǎn)：給定一個(gè)數(shù)據(jù)(字母)，然后查找，找到后刪除，否則，告知未找到，　　查找給定的二叉樹結(jié)點(diǎn)：給定一個(gè)數(shù)據(jù)(字母)，然后查找，并給出提示。　　輸出二排序叉樹：按照先序遍歷并輸出二叉排序樹的結(jié)點(diǎn)數(shù)據(jù)。&

9、lt;/p>　　退出：退出程序。　　第三章抽象數(shù)據(jù)類型定義　　定義格式如下：　　二叉樹BT抽象數(shù)據(jù)類型的設(shè)計(jì)　　ADT BT{&

10、lt;/p>　　數(shù)據(jù)對象root：先定義一個(gè)二叉樹結(jié)點(diǎn)的結(jié)構(gòu)體：　　typedef struct bst　　{　　char data;　　struct bst *left;<p

11、>　　struct bst *right;　　struct bst *father;　　}BSTree,*BST;　　root是指向二叉樹結(jié)點(diǎn)的指針；　　數(shù)據(jù)關(guān)系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)&g

12、t;表示由運(yùn)算符P結(jié)合起來的表達(dá)式E}　　基本操作：　　BST InitRoot()　　操作結(jié)果：為空二叉排序樹創(chuàng)建一個(gè)根節(jié)點(diǎn)，輸入一個(gè)字符型數(shù)據(jù)，將這個(gè)字符型數(shù)據(jù)存入結(jié)點(diǎn)的數(shù)據(jù)域中同時(shí)給左右孩子指針和父指針置空，并返回一個(gè)結(jié)點(diǎn)的基址給指針。<p

13、>　　void Inserter(root, key)　　初始條件：二叉排序樹不為空，存在根節(jié)點(diǎn)；　　操作結(jié)果：輸入一個(gè)字符型數(shù)據(jù)，先尋找二叉排序樹中是否有此數(shù)據(jù)，有則返回主菜單，沒有則就二叉排序樹的構(gòu)造方法返回要插入旳數(shù)據(jù)應(yīng)該插入位置的父節(jié)點(diǎn)地址，創(chuàng)建一個(gè)新結(jié)點(diǎn)，將這個(gè)字符型數(shù)據(jù)存入結(jié)點(diǎn)的數(shù)據(jù)域中，并將左右孩子指針置空，父指針指向父節(jié)點(diǎn)地址，然后

14、返回主菜單。　　BSTree *SearchKey(root,key)　　初始條件：二叉排序樹不為空，存在根節(jié)點(diǎn)；　　操作結(jié)果：輸入一個(gè)字符型數(shù)據(jù)，先尋找二叉排序樹中是否有此數(shù)據(jù)的，有則返回次數(shù)據(jù)項(xiàng)的地址給指針變量，沒有則就返回該數(shù)據(jù)按照二叉排序樹規(guī)則，應(yīng)該插入位置的父節(jié)點(diǎn)地址。<p

15、>　　void DeleteKey(root,key);　　初始條件：二叉排序樹不為空，存在根節(jié)點(diǎn)；　　操作結(jié)果：輸入一個(gè)字符型數(shù)據(jù)，調(diào)用BSTree *SearchKey(root,key)函數(shù)，先尋找二叉排序樹中是否有此數(shù)據(jù)的，有則返回次數(shù)據(jù)項(xiàng)的地址給指針變量，然后就此節(jié)點(diǎn)的特征分為四類：刪除葉子節(jié)點(diǎn)；刪除只有右孩子的節(jié)點(diǎn)；刪除只有左孩子的節(jié)點(diǎn)

16、；刪除左右孩子都有的節(jié)點(diǎn)，根據(jù)結(jié)點(diǎn)類型進(jìn)入不同刪除模塊，刪除結(jié)點(diǎn)，修改相應(yīng)二叉樹結(jié)點(diǎn)指針，返回主菜單；沒有則就返回提示語句“沒有找到該數(shù)據(jù)”。　　void ChainTree_LDR(root)　　初始條件：二叉排序樹不為空，存在根節(jié)點(diǎn)；　　操作結(jié)果：按照中序遍歷并輸出有序的數(shù)據(jù)序列。&l

17、t;p>　　} ADT BT　　BT抽象數(shù)據(jù)類型的設(shè)計(jì)　　class BT　　{　　private:</p&

18、gt;　　BST root;　　public:　　BT() :root(NULL) {}　　BST InitRoot();　　void Inserter(BSTree *t,

19、char key);　　BSTree *SearchKey(BSTree *t,char key);　　void DeleteKey(BSTree *t,char key);　　void ChainTree_LDR(BSTree *bt);　　};<

20、;/b>　　第四章詳細(xì)設(shè)計(jì)　　4.1工程視圖　　4.2類圖視圖　　4.3函數(shù)的調(diào)用關(guān)系

21、4.4主程序流程圖　　算法：主程序主要用運(yùn)了switch結(jié)構(gòu)，使得主程序更加方便的調(diào)用成員函數(shù)，各個(gè)成員函數(shù)間的關(guān)系也清晰明了。　　4.5主要算法的流程圖　　第五章測試　　1.主界面：</

22、b>　　2.設(shè)置二叉排序樹根節(jié)點(diǎn)：　　在主界面輸入1，進(jìn)入“設(shè)置二叉排序樹根節(jié)點(diǎn)”功能，按提示輸入根節(jié)點(diǎn)數(shù)據(jù)，結(jié)束到主界面。　　3.添加二叉排序樹結(jié)點(diǎn)：　　在主界面時(shí)，輸入2，進(jìn)入“添加二叉排序樹結(jié)點(diǎn)”功能。　　先進(jìn)行判空操

23、作，若二叉排序樹為空，給出提示：　　否則按提示輸入要添加的結(jié)點(diǎn)數(shù)目，并依此添加節(jié)點(diǎn)數(shù)據(jù)：　　4．輸出二叉排序樹：　　在主界面時(shí)，輸入5。　　先進(jìn)行判空操作，若二叉排序樹為空，給出提示：　　否則中序遍歷并輸出二叉排序樹：</p

24、>　　5.刪除二叉排序樹結(jié)點(diǎn)： 　　在主界面，輸入3，進(jìn)入刪除界面。　　先進(jìn)行判空操作，若二叉排序樹為空，給出提示：　　否則按照提示輸入要?jiǎng)h除的結(jié)點(diǎn)數(shù)據(jù)：　　（1）若輸入數(shù)據(jù)在二叉排序樹中沒有：　?。?

25、）若輸入數(shù)據(jù)在二叉排序樹中存在，則刪除：　　如圖所示結(jié)點(diǎn)L已刪除：　　6.查找給定二叉排序樹結(jié)點(diǎn)： 　　在主界面，輸入4，進(jìn)入查找界面。　　先進(jìn)行判空操作，若二叉排序樹為空，給出提示：　　然后按照提示輸入要查找的結(jié)點(diǎn)數(shù)據(jù)：<

26、/p>　　有的話：　　沒有的話：　　7.退出程序：　　在主界面，輸入0，退出程序。　　第六章總結(jié)</b&

27、gt;　　這次課程設(shè)計(jì)花費(fèi)了將近20天時(shí)間，這次課程設(shè)計(jì)在有了前幾次課設(shè)的經(jīng)驗(yàn)，困難減少了不少，但也是很艱辛的，從最初定稿到最后完成換了三版代碼，　　從一開始的二叉鏈表加遞歸操作，遞歸函數(shù)返回值總是出錯(cuò)，到第二次的二叉鏈表加非遞歸操作時(shí)的操作繁瑣，直到最后用了三叉鏈表加非遞歸操作，前前后后修改，換思路繼續(xù)修改，好多回，又逢各種考試堆疊到一起，確實(shí)也是苦

28、不堪言。　　非常感謝**老師的指導(dǎo)，沒有老師陪我一坐就是兩個(gè)小時(shí)的幫我糾正錯(cuò)誤，估計(jì)現(xiàn)在也完不成這收尾工作。　　今年有意的培養(yǎng)自己在編程方面的興趣，果然是很有成效的，這次的課設(shè)獨(dú)立完成使我很是振奮，嗯。。。。。。沒啥可說的了，還是那句話，有付出有回報(bào)。　　附錄：程序代碼<

29、;/p>　　#include<stdio.h>　　#include<stdlib.h>　　#include<process.h>　　#include<iostream>　　#include<

30、iomanip>　　#include<ctime>　　using namespace std;　　typedef struct bst　　{　　char data;</

31、p>　　struct bst *left;　　struct bst *right;　　struct bst *father;　　}BSTree,*BST;　　class BT<

32、p>　　{　　private:　　BST root;　　public:　　BT() :root(NULL) {}&

33、lt;/p>　　~BT(){};　　BST InitRoot();　　void Inserter(BSTree *t,char key);　　BSTree *SearchKey(BSTree *t,char key);<

34、;p>　　void DeleteKey(BSTree *t,char key);　　void ChainTree_LDR(BSTree *bt);　　};　　BSTree* BT::InitRoot()　　{&

35、lt;/b>　　BST node;　　if(node=new BSTree)　　{　　cout<<" 輸入根節(jié)點(diǎn)的數(shù)據(jù):";</p&g

36、t;　　cin>>node->data;　　node->left=NULL;　　node->right=NULL;　　node->father=NULL;　　return node;<

37、p>　　}　　}//初始化根節(jié)點(diǎn)　　void BT::Inserter(BSTree *t,char key)　　{　　BSTree *p,*paren

38、t,*head;　　if(!(p=new BSTree))　　{　　cout<<"申請內(nèi)存是出錯(cuò)!!!";　　exit(0);<p&g

39、t;　　}　　p->data=key;　　p->left=NULL;　　p->right=NULL;　　p->father=NULL;　　head=t

40、;　　while(head)　　{　　parent=head;　　if(key<head->data)　　head=head->left;</p&g

41、t;　　else if(key>head->data)　　head=head->right;　　else if(key==head->data)　　{　　cout<<"

42、;該數(shù)據(jù)已存在!!!";　　break;　　}　　}　　if(key<parent->data)

43、;　　{　　parent->left=p;　　p->father=parent;　　}　　else if(key>parent->data)<

44、p>　　{　　parent->right=p;　　p->father=parent;　　}　　}

45、　BST BT::SearchKey(BSTree *t,char key)　　{　　BSTree *parent=NULL,*head;　　head=t;　　while(head)</p&

46、gt;　　{　　parent=head;　　if(key==head->data)　　{　　parent=head;<b

47、>　　break;　　}　　else if(key<head->data)　　{　　head=head->left;<p&

48、gt;　　}　　else if(key>head->data)　　{　　head=head->right;　　}&l

49、t;p>　　}　　return parent;　　}　　void BT::DeleteKey(BSTree *t,char key)　　{</p&

50、gt;　　BSTree *p=NULL,*q=NULL,*r=NULL;　　p=SearchKey(t,key); 　　if(p->data==key)　　{　　{&

51、lt;/p>　　if(p->left==NULL&&p->right==NULL) //刪除葉子節(jié)點(diǎn)　　{　　if(p->father->left->data==key)

52、{　　r=p;p->father->left=NULL;　　}　　else if(p->father->right->data==key)　　{</

53、b>　　p->father->right=NULL;　　free(p);　　}　　}　　els

54、eif(p->left==NULL&&p->right!=NULL)//刪除只有右孩子的節(jié)點(diǎn)　　{　　if(t->data==key)　　{

55、　q=t;　　t->right->father=NULL;　　t=q->right;　　free(q);　　}

56、else if(p->father->left==p)　　{　　q=p;　　p->right->father=p->father;　　p->father-&

57、gt;left=p->right;　　free(q);　　}　　else if(p->father->right==p)　　{</p&

58、gt;　　q=p;　　p->right->father=p->father;　　p->father->right=p->right;　　free(q);

59、　　}　　}　　elseif(p->left!=NULL&&p->right==NULL)//刪除只有左孩子的節(jié)點(diǎn)　　{&

60、lt;p>　　if(t->data==key)　　{　　q=t;　　t->left->father=NULL;　　t=t->left;<

61、p>　　free(q);　　}　　else if(p->father->left==p)　　{　　q=p;</b&g

62、t;　　p->left->father=p->father;　　p->father->left=p->right;　　free(q);　　}

63、;　　else if(p->father->right==p)　　{　　q=p;　　p->left->father=p->father;　　p

64、->father->right=p->right;　　free(q);　　}　　}　　elseif(p->left!=NULL&a

65、mp;&p->right!=NULL)//刪除左右孩子都有的節(jié)點(diǎn)　　{BSTree *b;　　q=p->right;　　while(q)　　{b=q;</p&

66、gt;　　q=q->left;　　}　　p->data=b->data;　　if(b->right!=NULL)　　{&l

67、t;p>　　b->right->father=b->father;　　b->father->right=b->right;　　}　　else if(b->right==NULL)&l

68、t;b>　　{　　b->father->right=NULL;　　free(b);　　}　　}

69、　　}　　}　　else if(p->data!=key)　　{cout<<"沒有找到該數(shù)據(jù)!!!";}　　}&l

70、t;/b>　　void BT::ChainTree_LDR(BSTree *bt)　　{　　if(bt)　　{

71、　　ChainTree_LDR(bt->left);　　cout<<setw(3)<<bt->data;　　ChainTree_LDR(bt->right);　　}　　ret

72、urn;　　}//先序遞歸遍歷二叉樹　　int main()　　{　　system("color 0E");　　BT a;</b

73、>　　BSTree *root=NULL;　　int select1,n,i;　　char key,key1,key2;　　do{　　long t;

74、　　time(&t);　　cout<<endl;　　cout<<" 當(dāng)前時(shí)間：";　　cout<<ctime(&t)<<

75、endl;　　cout<<"\n >>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<

76、<<<<<<<< ";　　cout<<"\n >>>> 1.設(shè)置二叉排序樹根結(jié)點(diǎn) <<<< ";　　cout<<"\n

77、 >>>> 2.添加二排序叉樹結(jié)點(diǎn) <<<< ";　　cout<<"\n >>>> 3.刪除二排序叉樹結(jié)點(diǎn) <<<< ";<p

78、>　　cout<<"\n >>>> 4.查找給定二叉樹結(jié)點(diǎn) <<<< ";　　cout<<"\n >>>> 5.輸出二排序叉樹 <<<

79、< ";　　cout<<"\n >>>> 0.退出 <<<< ";　　cout<<"\n

80、請選擇:";　　cin>>select1;　　switch(select1)　　{　　case 1:cout<<endl;　　root=a.Ini

81、tRoot();　　break;　　case 2:cout<<endl;　　if(root==NULL)　　{　　cout<<&q

82、uot; 空樹!!!禁止操作!!!";　　cout<<endl;　　}　　else{　　cout<<&

83、quot; 請輸入你要添加的結(jié)點(diǎn)數(shù)目:";　　cin>>n;　　fflush(stdin);　　for(i=0;i<n;i++)　　{</p&

84、gt;　　cout<<" 請輸入你要添加的結(jié)點(diǎn)數(shù)據(jù):";　　cin>>key;　　a.Inserter(root,key);　　fflush(stdin);<p

85、>　　}　　}　　break;　　case 3:cout<<endl;　　if(root==NULL)<p&g

86、t;　　{　　cout<<" 空樹!!!禁止操作!!!";　　cout<<endl;　　}&

87、lt;b>　　else{　　cout<<" 請輸入你要?jiǎng)h除的結(jié)點(diǎn)數(shù)據(jù):";　　fflush(stdin);　　cin>>key1;　　a.DeleteKey(root,key1);&

88、lt;/p>　　cout<<endl;　　}　　break;　　case 4:cout<<endl;　　if(root==NULL)</p

89、>　　{　　cout<<" 空樹!!!禁止操作!!!";　　cout<<endl;　　}

90、;　　else{　　BSTree *key;　　cout<<" 請輸入你要查找的結(jié)點(diǎn)數(shù)據(jù):";　　fflush(stdin);　　cin>>key2

91、;　　key=a.SearchKey(root,key2);　　if(key->data==key2)　　{　　cout<<"二叉樹中有此數(shù)據(jù)!!!";<p&

92、gt;　　cout<<endl;　　}　　else　　{　　cout<<"二叉樹中沒有此數(shù)據(jù)!!!";&l

93、t;/p>　　cout<<endl;　　}　　}　　break;　　case 5:cout<<endl;&

94、lt;/p>　　if(root==NULL)　　{　　cout<<" 空樹!!!禁止操作!!!";　　cout<<endl;

95、　　}　　else{　　a.ChainTree_LDR(root);　　cout<<endl;　　}

96、　　break;　　case 0:exit(0);　　break;　　};system("pause");　　cout<<endl;</p&

97、gt;　　cout<<endl;　　cout<<endl;　　cout<<endl;　　}while(select1!=0);　　return 0;&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

《二叉排序樹的操作》課程設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評論

《二叉排序樹的操作》課程設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載