《數(shù)據(jù)結(jié)構(gòu)二叉排序樹的實(shí)現(xiàn)(用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu))課程設(shè)計(jì)報(bào)告書(共18頁).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)二叉排序樹的實(shí)現(xiàn)(用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu))課程設(shè)計(jì)報(bào)告書(共18頁).doc（17頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上  一、設(shè)計(jì)題目1、 題目：二叉排序樹的實(shí)現(xiàn)  (用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu) )2、要求（功能）： 1) 以回車('n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排      序樹T； 2) 對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果； 3) 輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操 作2)；否則輸出信息“無x”；2、 需求分析 建立排序二叉樹，主要是建立節(jié)點(diǎn)來存儲(chǔ)輸入的數(shù)據(jù)，需要建立函數(shù)來創(chuàng)造排序二

2、叉樹。該題目包括三方面的內(nèi)容：一個(gè)是二叉排序樹的建立，而是二叉樹的中序遍歷，三是二叉樹元素的查找并刪除。 3、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 在寫算法之前，應(yīng)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)。本體主要會(huì)用到指針變量，插入節(jié)點(diǎn)函數(shù)和建立二叉樹，以及中序遍歷函數(shù)，還有一些輸入輸出語句。四、算法設(shè)計(jì)算法設(shè)計(jì)思想二插鏈表作存儲(chǔ)結(jié)構(gòu)： 建立二插排序樹采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進(jìn)行查找。如果查找成功則不應(yīng)再插入原樹，否則返回當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)。然后利用插入函數(shù)將該元素插入原樹。對(duì)二叉樹進(jìn)行中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點(diǎn)不為空的情況下，先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。 刪除結(jié)點(diǎn)函數(shù)，采用邊查找邊刪

3、除的方式。如果沒有查找到，則不對(duì)樹做任何的修改；如果查找到結(jié)點(diǎn)，則分四種情況分別進(jìn)行討論：1、該結(jié)點(diǎn)左右子樹均為空；2、該結(jié)點(diǎn)僅左子樹為空；3、該結(jié)點(diǎn)僅右子樹為空；4、該結(jié)點(diǎn)左右子樹均不為空。在進(jìn)行算法設(shè)計(jì)時(shí)，應(yīng)將題目分為五個(gè)函數(shù)模塊：1、中序遍歷，符合升序輸出void inorder(node *&root) if(root!=NULL) inorder(root->left); cout<<root->data<<' ' inorder(root->right); 2、在查找樹中插入元素void insert(node *&

4、amp;ptr,int item) if(ptr=NULL) ptr=new node(item); else if(item<ptr->data) insert(ptr->left,item); else insert(ptr->right,item); 3、在查找樹中查找元素 node *find(node *&ptr,int item) if(ptr=NULL) return NULL; if(ptr->data=item) return ptr; else if(item<ptr->data) find(ptr->left,ite

5、m); else find(ptr->right,item); 4、在查找樹中查找肯定存在的元素,并返回其引用node *&findy(node *&ptr,int item) if(ptr->data=item) return ptr; else if(item<ptr->data) findy(ptr->left,item); else findy(ptr->right,item); node* rl()return left; node* rr()return right;5、刪除指定值為所在結(jié)點(diǎn)void dele(node *&

6、;ptr) if(ptr->rl()=NULL&&ptr->rr()=NULL) ptr=NULL; else if(ptr->rr()=NULL) ptr=ptr->rl(); else ptr=ptr->rr(); private: int data; node *left; node *right; ;5、 程序?qū)崿F(xiàn)1、 調(diào)入文件#include <iostream>2、 主函數(shù)int main() int t,i=0,j; cout<<" 10計(jì)科一班 楊 旭（）"<<endl; co

7、ut<<"1.二叉排序樹T的輸入:"<<endl; cout<<"輸入數(shù)字個(gè)數(shù)(結(jié)點(diǎn)個(gè)數(shù)):" cin>>t; cout<<"輸入"<<t<<"個(gè)數(shù)字，數(shù)字之間用空格隔開:" cin>>j; node *x=new node(j); for(;i<t-1;i+) cin>>j; x->insert(x,j); cout<<"中序遍歷為:" x->inorder

8、(x); /作中序遍歷 cout<<"n" cout<<"2.二叉排序樹T的元素查找和刪除:"<<endl; cout<<"n輸入操作(當(dāng)輸入-1時(shí)程序結(jié)束):"<<endl; cin>>j; while(j!=-1) node *t=x->find(x,j); /定位結(jié)點(diǎn) if(t!=NULL) node *&y=x->findy(x,j); x->dele(y); cout<<"中序遍歷為:" x-&g

9、t;inorder(x); else cout<<"無"<<j; cout<<"n輸入操作(當(dāng)輸入-1時(shí)程序結(jié)束):"<<endl; cin>>j; return 0;六、程序編碼#include <iostream>using namespace std;class nodepublic:node(int i):data(i),left(NULL),right(NULL) void inorder(node *&root) /中序遍歷，符合升序輸出 if(root!=NUL

10、L) inorder(root->left); cout<<root->data<<' ' inorder(root->right); void insert(node *&ptr,int item) /在查找樹中插入元素 if(ptr=NULL) ptr=new node(item); else if(item<ptr->data) insert(ptr->left,item); else insert(ptr->right,item); node *find(node *&ptr,int it

11、em) /在查找樹中查找元素,找到返回所在結(jié)點(diǎn)指針，找不到返回空指針。 if(ptr=NULL) return NULL; if(ptr->data=item) return ptr; else if(item<ptr->data) find(ptr->left,item); else find(ptr->right,item); node *&findy(node *&ptr,int item) /在查找樹中查找肯定存在的元素,并返回其引用 if(ptr->data=item) return ptr; else if(item<ptr

12、->data) findy(ptr->left,item); else findy(ptr->right,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /刪除值為item所在結(jié)點(diǎn) if(ptr->rl()=NULL&&ptr->rr()=NULL) ptr=NULL; else if(ptr->rr()=NULL) ptr=ptr->rl(); else ptr=ptr->rr(); private: int data; node *left; /左孩子結(jié)點(diǎn) node *right; /右孩子結(jié)點(diǎn);int main() int t,i=0,j; cout<<" 10計(jì)科一班 楊 旭（）"<<endl; cout<<"1.二叉排序樹T的輸入:"<<endl; cout<<"輸入數(shù)字個(gè)數(shù)(結(jié)點(diǎn)個(gè)數(shù)):" cin>>t; cout<<"輸入"<<t<<"個(gè)數(shù)字，數(shù)字之間用空格隔開:" cin>>