




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱: 實(shí)驗(yàn)三題目1二叉樹姓名: 班級(jí): 班內(nèi)序號(hào):學(xué)號(hào): 2013210465 1實(shí)驗(yàn)要求根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義,使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹。 二叉樹的基本功能:1、二叉樹的建立2、前序遍歷二叉樹3、中序遍歷二叉樹4、后序遍歷二叉樹5、按層序遍歷二叉樹6、求二叉樹的深度7、求指定結(jié)點(diǎn)到根的路徑8、二叉樹的銷毀9、其他:自定義操作編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)lch data rch使用二叉鏈表實(shí)現(xiàn)二叉樹的存儲(chǔ),其示意圖如下圖所示: data rchlch data data data 2.2
2、關(guān)鍵算法分析前序遍歷:訪問(wèn)根節(jié)點(diǎn)遍歷左子樹遍歷右子樹具體算法:template<class T>void BiTree<T>:PreOrder(BiNode<T>* R)/前序遍歷if(R!=NULL)cout<<R->data; /訪問(wèn)結(jié)點(diǎn)PreOrder(R->lch); /遍歷左子樹PreOrder(R->rch); /遍歷右子樹中序遍歷:template<class T>void BiTree<T>:Inorder(BiNode<T>*R) if(R!=NULL) Inorder(R-
3、>lchild); /遍歷左子樹 cout<<R->data; /訪問(wèn)結(jié)點(diǎn) Inorder(R->rchild); /遍歷右子樹 后序遍歷template<class T>void BiTree<T>:Postorder(BiNode<T>*R) if(R!=NULL) Postorder(R->lchild); /遍歷左子樹 Postorder(R->rchild); /遍歷右子樹 cout<<R->data; /訪問(wèn)結(jié)點(diǎn) 層序遍歷: template<class T>void BiT
4、ree<T>:LevelOrder(BiNode<T>* R)/層序遍歷BiNode<T>* queue100; /創(chuàng)建隊(duì)int f=0,r=0; /r為隊(duì)尾指針,f為對(duì)頭指針if(R!=NULL)queue+r=R; /頭結(jié)點(diǎn)入隊(duì)while(f!=r) /如果隊(duì)不為空,做此循環(huán)BiNode<T>* p=queue+f; /出隊(duì)cout<<p->data;if(p->lch!=NULL) /出隊(duì)結(jié)點(diǎn)若有左右孩子,則左右孩子依次入隊(duì)queue+r=p->lch;if(p->rch!=NULL)queue+r=p-
5、>rch;求深度:template<class T> int BiTree<T>:Depth(BiNode<T>* R,int d) /求二叉樹的深度 if (R=NULL) /如果二叉樹為空,返回0return d; if (R->lch=NULL)&&(R->rch=NULL) /如果二叉樹沒(méi)有孩子,返回二叉樹深度return d+1; else /如果二叉樹有孩子,做遞歸循環(huán),并返回二叉樹的最長(zhǎng)路徑,即二叉樹深度 int m=GetDepth(R->lch,d+1); int n=GetDepth(R->r
6、ch,d+1); return n>m?n:m; 求路徑:template<class T>bool BiTree<T>:Getpath(BiNode<T>*R,int d) if(R=NULL)return false; if(R->data=d|Getpath(R->lchild,d)|Getpath(R->rchild,d) cout<<R->data<<" " return true; 時(shí)間復(fù)雜度: 前序遍歷:O(n) 層序遍歷:O(n) 求二叉樹深度:O(n)3. 程序運(yùn)行結(jié)
7、果3.1 測(cè)試主函數(shù)流程 開(kāi)始創(chuàng)建字符數(shù)組創(chuàng)建二叉樹前序遍歷中序遍歷后序遍歷層序遍歷求二叉樹深度求指定結(jié)點(diǎn)到二叉樹根節(jié)點(diǎn)路徑結(jié)束 4. 總結(jié)該次試驗(yàn)中,二叉樹的建立,前序遍歷,中序遍歷,后序遍歷,求二叉樹的深度以及二叉樹的銷毀都涉及到遞歸函數(shù)的巧妙應(yīng)用。二叉樹的層序遍歷則利用“隊(duì)”的概念來(lái)實(shí)現(xiàn)根節(jié)點(diǎn)入隊(duì),出隊(duì),并讓其孩子按順序入隊(duì)。個(gè)人覺(jué)得最難的部分莫過(guò)于求指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于尋找指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑,首先覺(jué)得應(yīng)該是一個(gè)一個(gè)節(jié)點(diǎn)地尋找,直到找到要求的結(jié)點(diǎn),尋找過(guò)程即用到二叉樹的遍歷,比如該實(shí)驗(yàn)中用到的前序遍歷;再者,關(guān)于路徑,想到“迷宮問(wèn)題”,即使用“?!贝鎯?chǔ)尋找到指定結(jié)點(diǎn)的正確路徑
8、,并一一出棧,就可得到指定結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。對(duì)于編程,有些巧妙而經(jīng)典的方法需要記憶,獨(dú)自想出每種問(wèn)題的算法比較困難,也浪費(fèi)時(shí)間,而借鑒一些經(jīng)典算法,有利于加快工作,也啟迪我們一些算法的創(chuàng)新。所以,我們需要記憶一些經(jīng)典算法。源程序:#include<iostream>using namespace std;template<class T>struct BiNodeT data;BiNode<T>*lchild;BiNode<T>*rchild;template<class T>class BiTreeprivate:void Cre
9、ate(BiNode<T>*&R,T data,int i,int n);/創(chuàng)建二叉樹void Release(BiNode<T>*R);/釋放二叉樹public:BiNode<T>*root; /根節(jié)點(diǎn)BiTree(T data,int n); /構(gòu)造函數(shù)void Preorder(BiNode<T>*R); /前序遍歷void Inorder(BiNode<T>*R); /中序遍歷void Postorder(BiNode<T>*R); /后序遍歷void Leveorder(BiNode<T>*R
10、); /層序遍歷BiTree(); /析構(gòu)函數(shù) int Count(BiNode<T>*R); /結(jié)點(diǎn)數(shù)bool Getpath(BiNode<T>*R,int d); /路徑int GetDepth(BiNode<T>*R,int d); /深度;template<class T>void BiTree<T>:Create(BiNode<T>*&R,T data,int i,int n) /表示位置,從開(kāi)始,表示數(shù)組的長(zhǎng)度if(i<=n)R=new BiNode<T> /創(chuàng)建根節(jié)點(diǎn)R->d
11、ata=datai-1;Create(R->lchild,data,2*i,n); /創(chuàng)建左子樹Create(R->rchild,data,2*i+1,n); /創(chuàng)建右子樹else R=NULL;template<class T>BiTree<T>:BiTree(T data,int n)Create(root,data,1,n);/前序遍歷template<class T>void BiTree<T>:Preorder(BiNode<T>*R)if(R!=NULL)cout<<R->data; /訪問(wèn)節(jié)
12、點(diǎn)Preorder(R->lchild); /遍歷左子樹Preorder(R->rchild); /遍歷右子樹/中序遍歷template<class T>void BiTree<T>:Inorder(BiNode<T>*R)if(R!=NULL)Inorder(R->lchild); /遍歷左子樹cout<<R->data; /訪問(wèn)結(jié)點(diǎn)Inorder(R->rchild); /遍歷右子樹/后序遍歷template<class T>void BiTree<T>:Postorder(BiNode&
13、lt;T>*R)if(R!=NULL)Postorder(R->lchild); /遍歷左子樹Postorder(R->rchild); /遍歷右子樹cout<<R->data; /訪問(wèn)結(jié)點(diǎn)/層序遍歷template<class T>void BiTree<T>:Leveorder(BiNode<T>*R)BiNode<T>*queue100;int f=0;int r=0; /初始化空隊(duì)列if(R!=NULL) queue+r=R; /根節(jié)點(diǎn)入隊(duì)while(f!=r)BiNode<T>*p=que
14、ue+f; /對(duì)頭元素出隊(duì)cout<<p->data; /出隊(duì)打印if(p->lchild!=NULL) queue+r=p->lchild; /左孩子入隊(duì)if(p->rchild!=NULL) queue+r=p->rchild; /右孩子入隊(duì)/析1函數(shù)template<class T>void BiTree<T>:Release(BiNode<T>*R)if(R!=NULL)Release(R->lchild); 釋放左子樹Release(R->rchild); /釋放右子樹delete R; /釋放
15、根節(jié)點(diǎn)/釋放二叉樹template<class T>BiTree<T>:BiTree()Release(root);/求結(jié)點(diǎn)總數(shù)template<class T>int BiTree<T>:Count(BiNode<T> *R)if(R=NULL)return 0;elseint m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;/求深度template<class T>int BiTree<T>:GetDepth(BiNode<T&
16、gt; *R,int d)if(R=NULL)return d;if(R->lchild=NULL)&&(R->rchild=NULL)return d+1;elseint m=GetDepth(R->lchild,d+1);int n=GetDepth(R->rchild,d+1);return n>m?n:m; /查詢結(jié)點(diǎn)路徑? template<class T>bool BiTree<T>:Getpath(BiNode<T>*R,int d) if(R=NULL)return false;if(R->
17、data=d|Getpath(R->lchild,d)|Getpath(R->rchild,d)cout<<R->data<<" "return true;void main() char data50="abcdefgh"BiTree<char>tree(data,8);cout<<"前序遍歷為:"tree.Preorder(tree.root);cout<<endl;cout<<"中序遍歷為:"tree.Inorder(tree.root);cout<<endl;cout<<"后序遍歷為:"tree.Postorder(tree.root);cout<<endl;cout<<"層序遍歷為:"tree.Leveorder(tree.root);cout<<endl;
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 化工廠施工危險(xiǎn)點(diǎn)識(shí)別及防范預(yù)控措施
- 一年級(jí)上冊(cè)書法課學(xué)生能力提升計(jì)劃
- 公務(wù)出差批準(zhǔn)回復(fù)函范文
- 以案說(shuō)警酒店行業(yè)服務(wù)規(guī)范心得體會(huì)
- 人教版小學(xué)四年級(jí)數(shù)學(xué)下冊(cè)微課制作計(jì)劃
- 機(jī)場(chǎng)航站樓網(wǎng)架高空散裝安全防護(hù)措施
- 大班幼小銜接的勞動(dòng)習(xí)慣培養(yǎng)計(jì)劃
- 機(jī)械電子一體化專業(yè)畢業(yè)實(shí)習(xí)報(bào)告范文
- 成人本科自考自我鑒定范文
- 精密儀表成品保護(hù)措施
- 小學(xué)數(shù)學(xué)教學(xué)中如何培養(yǎng)學(xué)生數(shù)感
- 數(shù)學(xué) 2024-2025學(xué)年人教版(2024)七年級(jí)數(shù)學(xué)下冊(cè)期末考試測(cè)試卷
- 貴州省貴陽(yáng)市部分學(xué)校2024-2025學(xué)年高二下冊(cè)期末聯(lián)考數(shù)學(xué)試卷(附答案)
- 2025至2030中國(guó)二手車市場(chǎng)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 《機(jī)床電氣與PLC控制技術(shù)》課件 2 S7-1200PLC數(shù)據(jù)的存儲(chǔ)及訪問(wèn)
- 多模態(tài)人機(jī)交互優(yōu)化-洞察闡釋
- T/CAR 7-2021綠色高效自攜式商用冷藏陳列柜技術(shù)要求和評(píng)價(jià)方法
- 合作賬號(hào)合伙協(xié)議書
- 五年級(jí)數(shù)學(xué)下冊(cè)期末必考應(yīng)用題母題
- 山東省濟(jì)南市2025屆高三三模生物試卷(含答案)
評(píng)論
0/150
提交評(píng)論