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

6.4.1二叉排序樹(shù)基本操作的實(shí)現(xiàn) 專(zhuān)業(yè)：*姓名：*學(xué)號(hào)：*日期：2011-9-17一， 問(wèn)題描述二， 需求分析三， 概要設(shè)計(jì)四， 詳細(xì)設(shè)計(jì)五， 測(cè)試分析六， 源程序清單七， 用戶使用手冊(cè)八， 心得體會(huì)一、 問(wèn)題描述從鍵盤(pán)讀入一組數(shù)據(jù)，建立二叉排序樹(shù)并對(duì)其進(jìn)行查找、遍歷、格式化輸出操作。二、 需求分析1. 讀入給定的數(shù)據(jù)，構(gòu)造二叉排序樹(shù)，實(shí)現(xiàn)初始化。2. 給定數(shù)據(jù)的格式為，第一行為元素個(gè)數(shù)，遇0退出程序。3. 提供菜單功能，選項(xiàng)包括查找、插入、刪除和打印等。三、 概要設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)：struct nodeint num;node *chl,*chr;分別定義了指向左右子樹(shù)的指針。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ù)或者沒(méi)有指定元素的非法刪除以及查找，所以會(huì)在函數(shù)內(nèi)部直接進(jìn)行判斷，以及狀態(tài)返回判斷等。3. 函數(shù)形參部分形參使用引用的方式進(jìn)行傳遞，還有些使用的是指針的指針，這樣保傳入的指針指向的內(nèi)容可以被修改，并且函數(shù)返回之后可以繼續(xù)指向原有內(nèi)容。四、 詳細(xì)設(shè)計(jì)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ù)，使用遞歸的方式進(jìn)行插入，并動(dòng)態(tài)創(chuàng)建對(duì)象。void Delete(const int &key,node *p)if( *p=NULL )cout刪除錯(cuò)誤，不存在該元素！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ī)則，分三種情況進(jìn)行刪除，最后還會(huì)銷(xiāo)毀指針指向的對(duì)象。如果某個(gè)元素不在其中，那么最后指向的指針必然為空。另外之前沒(méi)考慮到刪除失敗的狀態(tài)返回情況，所以后面使用了一個(gè)全局變量來(lái)作為補(bǔ)救標(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)前比較的指針，但卻沒(méi)有具體實(shí)現(xiàn)輸出其指向的信息，覺(jué)得即便輸出對(duì)本程序意義不大，所以沒(méi)有具體關(guān)注。depth為查找需要的次數(shù)。void Print(const node *p)if( p=NULL )return;coutnumchl);Print(p-chr);/ 只提供了中序遍歷輸出的情況，其他情況沒(méi)考慮。五、 測(cè)試分析1. 測(cè)試環(huán)境：Code：Blocks 10.05.2. 輸入過(guò)程：課本提供數(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刪除錯(cuò)誤，不存在該元素！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-二叉排序樹(shù)演示-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二叉樹(shù)為空，查找失??！endl;elsedepth = 0;net = NULL;suc = Find(num,*root,net,depth);if( suc )cout查找成功。endl;elsecout查找失敗，沒(méi)有該元素。endl;cout查找深度 : depthendl;break;case 3:cout中序遍歷二叉排序樹(shù)endl;if( *root=NULL )cout二叉樹(shù)為空！endl;elsePrint(*root);break;case 4:cout輸入要?jiǎng)h除的數(shù)字：num;flagdel = true;Delete(num,&(*root);if( flagdel ) cout刪除成功！endlendl;break; case 5: return false;default:cout錯(cuò)誤選擇。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依