數據結構課程設計之二叉排序樹的實現＃＃大學數據結構課程設計報告題目： 二叉排序樹的實現 院（系）： 計算機工程學院 學生姓名: 班級：學號: 起迄日期: 2011.6.20-2011.7.1 指導教師: 數據結構課程設計之二叉排序樹的實現全文共數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第1頁。指導教師評語：指導教師評語：成績：簽名：年月日2010—2011年度第2學期數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第2頁。

一、需求分析數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第2頁。1.問題描述：二叉排序樹的實現用順序和二叉鏈表作存儲結構1)以回車('\n')為輸入結束標志,輸入數列L，生成一棵二叉排序樹T；2)對二叉排序樹T作中序遍歷，輸出結果；3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執行操作2)；否則輸出信息“無x”；2.基本功能1)生成一棵二叉排2)對二叉排序樹T作中序遍歷3)查找二叉排序樹T3.輸入輸出輸入:輸入數列L以回車('\n')為輸入結束標志輸出:中序遍歷的二叉樹二、概要設計1.設計思路：首先，要創建一棵二叉排序樹；必須定義二叉排序樹的結點結構數據類型，并定義insert函數，在二叉排序樹中插入結點。要中序遍歷二叉排序樹，必然用到遞歸算法。先根再左再右。要在二叉樹中查找輸入的元素，若存在含x的結點,則刪除該結點,并作中序遍歷。2.數據結構設計：voidinorder(node*&root)中序遍歷，符合升序輸出voidinsert(node*&ptr,intitem)在查找樹中插入元素node*find(node*&ptr,intitem)在查找樹中查找元素,找到返回所在結點指針，找不到返回空指針。node*&findy(node*&ptr,intitem)在查找樹中查找肯定存在的元素,并返回其引用voiddele(node*&ptr)刪除值為item所在結點3.軟件結構設計Main模塊二叉排序樹模塊三、詳細設計1.樹的結點數據類型：數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第3頁。classnode數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第3頁。{public:node(inti):data(i),left(NULL),right(NULL){}2．主函數和其他函數的偽碼算法；voidinorder(node*&root)//中序遍歷，符合升序輸出{if(root!=NULL){inorder(root->left);cout<<root->data<<'';inorder(root->right);}}voidinsert(node*&ptr,intitem)//在查找樹中插入元素{if(ptr==NULL)ptr=newnode(item);elseif(item<ptr->data)insert(ptr->left,item);elseinsert(ptr->right,item);}node*find(node*&ptr,intitem)//在查找樹中查找元素,找到返回所在結點指針，找不到返回空指針。{if(ptr==NULL)returnNULL;if(ptr->data==item)returnptr;elseif(item<ptr->data)find(ptr->left,item);elsefind(ptr->right,item);}node*&findy(node*&ptr,intitem)//在查找樹中查找肯定存在的元素,并返回其引用{if(ptr->data==item)returnptr;elseif(item<ptr->data)findy(ptr->left,item);elsefindy(ptr->right,item);}node*rl(){returnleft;}node*rr(){returnright;}voiddele(node*&ptr)//刪除值為item所在結點數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第4頁。{數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第4頁。if(ptr->rl()==NULL&&ptr->rr()==NULL)ptr=NULL;elseif(ptr->rr()==NULL)ptr=ptr->rl();elseptr=ptr->rr();}private:intdata;node*left;//左孩子結點node*right;//右孩子結點};intmain(){intt,i=0,j;cout<<"輸入結點個數:";cin>>t;cout<<"輸入"<<t<<"個數字，數字之間用空格隔開:";cin>>j;node*x=newnode(j);for(;i<t-1;i++){cin>>j;x->insert(x,j);}cout<<"中序遍歷為:";x->inorder(x);//作中序遍歷cout<<"\n輸入操作(輸入-1時程序結束):"<<endl;cin>>j;while(j!=-1){node*t=x->find(x,j);//定位結點if(t!=NULL){node*&y=x->findy(x,j);x->dele(y);cout<<"中序遍歷為:";x->inorder(x);}elsecout<<"無"<<j;cout<<"\n輸入操作(輸入-1時程序結束):"<<endl;cin>>j;數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第5頁。}數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第5頁。return0;}3.主要函數的程序流程圖創建二叉排序樹的流程圖：i<t-1x->insert(x,j)i<t-1x->insert(x,j)i++i++中序遍歷二叉排序樹的流程圖開始開始root!=NULLroot!=NULLNNYYinorder(root->left)inorder(root->left)輸出輸出root->datainorder(root->right);inorder(root->right);結束結束數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第6頁。數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第6頁。3.dete函數的流程圖開始開始ptr->rl()==NULL&&ptr->rr()==NULLptr->rl()==NULL&&ptr->rr()==NULLYYNNptr->rr()==NULLptr->rr()==NULLYYNNptr=ptr->rr()ptr=ptr->rr()ptr=ptr->rr()ptr=ptr->rr()ptr=NULLptr=NULL結束結束數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第7頁。4.畫出函數之間的調用關系圖。數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第7頁。四、調試分析1.本程序可以生成一棵二叉排，對二叉排序樹T作中序遍歷，查找二叉排序樹T中的元素。2.時空分析:函數node*find(node*&ptr,intitem)的時間復雜度為O（n）.3.上機過程中出現的問題及其解決方案在函數node*find(node*&ptr,intitem)中我開始定義返回類型為整型，編譯時會報錯，所以我將其改為node指針型，然后就沒問題了。在編程時經常忘記分號和“}”，也在編譯時出現了錯誤。五、測試結果1、輸入節點數和數字序列：72341122556192.中序遍歷二叉排序樹；輸出：2512192341563.查找二叉排序樹中的元素。輸入：12輸出：19234156輸入：89輸出：無89六、用戶手冊1、輸入節點數和數字序列，創建二叉排序樹。2.中序遍歷二叉排序樹；數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第8頁。3.查找二叉排序樹中的元素。數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第8頁。七、體會與自我評價通過這次課程設計我也著實又感受了一次編程的樂趣，從中也學到了不少知識。我在學習運用數據結構編程之前，并沒能深刻體會到這一點，直到這次課程設計，我才有所領悟。本課題運用C語言進行開發，C語言能夠簡單的進行編譯一些程序，來實現對一些問題的解決。它雖然比較簡單的處理一些問題，但卻有更高的效率。它能夠被大多數用戶所接受，因為它能夠呈現出清晰的界面，是人們能夠很好的理解。能在一些方面給人們更好的服務，成為人們的好幫手。經過這一個學期對《數據結構》的學習，我們都學到了不少東西，可能有些學的還不夠理想，但無論如何這些知識都為我們的下一步學習打下了堅實的基礎。做這么一個課程設計，一方面是為了檢查我們一個學期以來的學習成果，另一方面也是為了讓我們進一步的掌握和運用它，同時也讓我們認清自己的不足之處和薄弱環節，加以彌補和加強。這次實驗中我也出現過一些比較嚴重的錯誤。在用一維數組順序表結構編寫程序時我錯誤的運用靜態鏈表來實現函數功能。這是我對基本概念理解的模糊不清造成的。我原以為只要采用一維數組作為存儲結構它就一定也是順序表結構，而實質上這根本是兩個不相干的概念。后來在同學的指點下我意識到自己的錯誤。不過收獲也很不少。至少我又練習了運用靜態鏈表來實現同樣的功能，同時我也發現兩者在很多函數上是互通的，只需稍作修改即可移植。另外程序的不足之處是不能實現對0這個數字的存儲，可以通過改變數字的存儲結構方式來實現，如使用二叉鏈表來作為數據的存儲結構，即可實現該功能。總之，我會繼續我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步不斷提高的。源代碼；#include<iostream>數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第9頁。usingnamespacestd;數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第9頁。classnode{public:node(inti):data(i),left(NULL),right(NULL){}voidinorder(node*&root)//中序遍歷，符合升序輸出{if(root!=NULL){inorder(root->left);cout<<root->data<<'';inorder(root->right);}}voidinsert(node*&ptr,intitem)//在查找樹中插入元素{if(ptr==NULL)ptr=newnode(item);elseif(item<ptr->data)insert(ptr->left,item);elseinsert(ptr->right,item);}node*find(node*&ptr,intitem)//在查找樹中查找元素,找到返回所在結點指針，找不到返回空指針。{if(ptr==NULL)returnNULL;if(ptr->data==item)returnptr;elseif(item<ptr->data)find(ptr->left,item);elsefind(ptr->right,item);}node*&findy(node*&ptr,intitem)//在查找樹中查找肯定存在的元素,并返回其引用{if(ptr->data==item)returnptr;elseif(item<ptr->data)findy(ptr->left,item);elsefindy(ptr->right,item);}node*rl(){returnleft;}node*rr(){returnright;}數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第10頁。voiddele(node*&ptr)//刪除值為item所在結點數據結構課程設計之二叉排序樹的實現全文共12頁，當前為第10頁。{if(ptr->rl()==NULL&&ptr->rr()==NULL)ptr=NULL;elseif(ptr->rr()==NULL)ptr=ptr->rl();elseptr=ptr->rr();}private:intdata;node*left;