數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-二叉排序樹.doc

6.4.1二叉排序樹基本操作的實現(xiàn) 專業(yè)：*姓名：*學(xué)號：*日期：2011-9-17一， 問題描述二， 需求分析三， 概要設(shè)計四， 詳細設(shè)計五， 測試分析六， 源程序清單七， 用戶使用手冊八， 心得體會一、 問題描述從鍵盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進行查找、遍歷、格式化輸出操作。二、 需求分析1. 讀入給定的數(shù)據(jù)，構(gòu)造二叉排序樹，實現(xiàn)初始化。2. 給定數(shù)據(jù)的格式為，第一行為元素個數(shù)，遇0退出程序。3. 提供菜單功能，選項包括查找、插入、刪除和打印等。三、 概要設(shè)計1.數(shù)據(jù)結(jié)構(gòu)：struct nodeint num;node *chl,*chr;分別定義了指向左右子樹的指針。2.函數(shù)介紹void Insert(const int &temp,node *root);void Delete(const int &key,node *p);bool Find(const int &key,node *p,node *net,int &depth);void Print(const node *p);bool Menu(node *root);函數(shù)如其名，功能也亦如其名。另外為了防止邊界情況，如空樹或者沒有指定元素的非法刪除以及查找，所以會在函數(shù)內(nèi)部直接進行判斷，以及狀態(tài)返回判斷等。3. 函數(shù)形參部分形參使用引用的方式進行傳遞，還有些使用的是指針的指針，這樣保傳入的指針指向的內(nèi)容可以被修改，并且函數(shù)返回之后可以繼續(xù)指向原有內(nèi)容。四、 詳細設(shè)計void Insert(const int &temp,node *root)if( *root=NULL )*root = new node;(*root)-chl = (*root)-chr = NULL;(*root)-num = temp;else if( (*root)-numchr);elseInsert(temp,&(*root)-chl);/ 插入函數(shù)，使用遞歸的方式進行插入，并動態(tài)創(chuàng)建對象。void Delete(const int &key,node *p)if( *p=NULL )cout刪除錯誤，不存在該元素！num=key )if( (*p)-chl=NULL )temp = *p;*p = (*p)-chr;delete temp;else if( (*p)-chr=NULL )temp = *p;*p = (*p)-chl;delete temp;elsetemp = (*p)-chl;node *front=NULL;while( temp-chr )front = temp;temp = temp-chr;front-num = temp-num;if( front!=temp )front-chr = temp-chl;elsefront-chl = temp-chl;delete temp;else if( (*p)-numkey )Delete(key,&(*p)-chl);elseDelete(key,&(*p)-chr);/ 刪除函數(shù)。按照規(guī)則，分三種情況進行刪除，最后還會銷毀指針指向的對象。如果某個元素不在其中，那么最后指向的指針必然為空。另外之前沒考慮到刪除失敗的狀態(tài)返回情況，所以后面使用了一個全局變量來作為補救標(biāo)記。bool Find(const int &key,node *p,node *net,int &depth)if( p=NULL )return false;depth+;net = p;if( p-num=key )return true;else if( p-numkey )return Find(key,p-chl,net,depth);elsereturn Find(key,p-chr,net,depth);/ 查找函數(shù)，參數(shù) *net用以指向當(dāng)前比較的指針，但卻沒有具體實現(xiàn)輸出其指向的信息，覺得即便輸出對本程序意義不大，所以沒有具體關(guān)注。depth為查找需要的次數(shù)。void Print(const node *p)if( p=NULL )return;coutnumchl);Print(p-chr);/ 只提供了中序遍歷輸出的情況，其他情況沒考慮。五、 測試分析1. 測試環(huán)境：Code：Blocks 10.05.2. 輸入過程：課本提供數(shù)據(jù)：711 33 44 55 58 79 88兩種查找情況 刪除操作 插入操作 六、 源程序清單#include #include #include #include #include using namespace std;struct nodeint num;node *chl,*chr;bool flagdel;ifstream in(sort.txt);void Insert(const int &temp,node *root)if( *root=NULL )*root = new node;(*root)-chl = (*root)-chr = NULL;(*root)-num = temp;else if( (*root)-numchr);elseInsert(temp,&(*root)-chl);void Delete(const int &key,node *p)if( *p=NULL )cout刪除錯誤，不存在該元素！num=key )if( (*p)-chl=NULL )temp = *p;*p = (*p)-chr;delete temp;else if( (*p)-chr=NULL )temp = *p;*p = (*p)-chl;delete temp;elsetemp = (*p)-chl;node *front=NULL;while( temp-chr )front = temp;temp = temp-chr;front-num = temp-num;if( front!=temp )front-chr = temp-chl;elsefront-chl = temp-chl;delete temp;else if( (*p)-numkey )Delete(key,&(*p)-chl);elseDelete(key,&(*p)-chr);bool Find(const int &key,node *p,node *net,int &depth)if( p=NULL )return false;depth+;net = p;if( p-num=key )return true;else if( p-numkey )return Find(key,p-chl,net,depth);elsereturn Find(key,p-chr,net,depth);void Print(const node *p)if( p=NULL )return;coutnumchl);Print(p-chr);bool Menu(node *root)int choice,num,depth;node *net;bool suc;coutendltt-二叉排序樹演示-endl;coutendlendltttt菜單endlendl;coutt 1.插入 t2.查找endlendl;coutt 3.遍歷 t4.刪除endlendl;coutt 5.退出菜單endlendlendl;coutchoice;if( choice=5 )return false; coutendlendl;switch( choice )case 1:cout輸入要插入的數(shù)字：num;Insert(num,&(*root);cout插入成功！endl;break;case 2:cout輸入查找元素：num;if( *root=NULL )cout二叉樹為空，查找失敗！endl;elsedepth = 0;net = NULL;suc = Find(num,*root,net,depth);if( suc )cout查找成功。endl;elsecout查找失敗，沒有該元素。endl;cout查找深度 : depthendl;break;case 3:cout中序遍歷二叉排序樹endl;if( *root=NULL )cout二叉樹為空！endl;elsePrint(*root);break;case 4:cout輸入要刪除的數(shù)字：num;flagdel = true;Delete(num,&(*root);if( flagdel ) cout刪除成功！endlendl;break; case 5: return false;default:cout錯誤選擇。endl;coutendlendl;return true;int main()int i;int num,depth;bool first=true;couttttt*初始化*endlnum,num )first = false;node *root= NULL;depth=0;vector ve(num+1);coutendl依