樹(shù)的遍歷實(shí)驗(yàn)報(bào)告

1、 實(shí)驗(yàn)項(xiàng)目： 樹(shù)的遍歷 1. 實(shí)驗(yàn)?zāi)康模簩W(xué)會(huì)創(chuàng)建一棵二叉樹(shù)，以及完成對(duì)樹(shù)的簡(jiǎn)單操作。2. 實(shí)驗(yàn)內(nèi)容： 1） 生成一棵以二叉鏈表存儲(chǔ)的二叉樹(shù)bt（不少于15個(gè)結(jié)點(diǎn)）2） 分別用遞歸和非遞歸方法前序遍歷bt，并以縮格形式打印bt上各結(jié)點(diǎn)的信息。3） 編寫算法，交換bt上所有結(jié)點(diǎn)的左、右子樹(shù)，并以縮格形式打印出交換前后的bt結(jié)點(diǎn)信息。3. 程序簡(jiǎn)介：先創(chuàng)建一棵二叉樹(shù)，遞歸非遞歸前序遍歷，層次遍歷，交換左右子樹(shù)，縮格打印各結(jié)點(diǎn)的信息。4. 算法設(shè)計(jì)介紹：首先按照前序遍歷的順序遞歸創(chuàng)建一棵二叉樹(shù)，然后序遍歷的非遞歸使用堆棧完成的，即訪問(wèn)該結(jié)點(diǎn)的時(shí)候，如果有右孩子，讓右孩子進(jìn)棧，訪問(wèn)左孩子，當(dāng)左孩子為空時(shí)

2、，拋出棧頂?shù)脑兀L問(wèn)出棧的這個(gè)元素的左右孩子。縮格打印和層次遍歷想法類似，都是借助隊(duì)列完成的，把當(dāng)前結(jié)點(diǎn)的左右孩子進(jìn)隊(duì)列之后，讓這個(gè)結(jié)點(diǎn)出隊(duì)列。交換左右子樹(shù)，就是當(dāng)某個(gè)結(jié)點(diǎn)的左右子樹(shù)不同時(shí)為空時(shí)，定義一個(gè)中間變量交換。5. 困難及解答一開(kāi)始創(chuàng)建二叉樹(shù)的參數(shù)我想用指向結(jié)構(gòu)體的指針，后來(lái)才意識(shí)到得用指向指針的指針，想了好一段時(shí)間才想明白，因?yàn)槟硞€(gè)結(jié)點(diǎn)的左右孩子是指向結(jié)點(diǎn)的指針，要想再指向一個(gè)指針，只能用指針的指針了。6. 心得樹(shù)這一章我聽(tīng)得亂七八糟，上課能聽(tīng)懂，但就是不會(huì)編程，要不是書上有算法，我估計(jì)我肯定編不出來(lái)，看來(lái)還是得多編啊。程序清單/*/ 我真誠(chéng)地保證： / 我獨(dú)立完成了整個(gè)程序從分析

3、、設(shè)計(jì)到編碼的所有工作。/ 如果在上述過(guò)程中，我遇到了什么困難而求教于人，那么，我將在程序?qū)嵙?xí)報(bào)告中/ 詳細(xì)地列舉我所遇到的問(wèn)題，以及別人給我的提示。 / 我的程序里中凡是引用到其他程序或文檔之處，/ 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段,/ 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。/ 我從未沒(méi)抄襲過(guò)別人的程序，也沒(méi)有盜用別人的程序，/ 不管是修改式的抄襲還是原封不動(dòng)的抄襲。/ 我編寫這個(gè)程序，從來(lái)沒(méi)有想過(guò)要去破壞或妨礙其他計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn)。 文件名稱：創(chuàng)建者：創(chuàng)建時(shí)間：2011.5.3最后修改時(shí)間：2011.5.6功能：s樹(shù)的創(chuàng)建、遞歸和非遞歸前序遍歷、層次遍

4、歷、縮格打印、數(shù)的高度（根結(jié)點(diǎn)為第一層）、樹(shù)的葉子數(shù)、交換左右子樹(shù)文件中的函數(shù)名稱和簡(jiǎn)單功能描述：bool CreateBT(BiTree *T)-創(chuàng)建一棵二叉樹(shù)，并用二叉鏈表存儲(chǔ)，bool Recursion_PreOrder(BiTree T)-遞歸前序遍歷bool Non_Recursion_Preorder(BiTree T)-非遞歸前序遍歷int Height(BiTree T)-計(jì)算樹(shù)的高度void Indented_Printed(BiTree T)-縮格打印void Hierarchy_Traversal(BiTree T)-層次遍歷void swap(BiTree T)-交換

5、左右孩子文件中定義的全局變量和簡(jiǎn)單功能描述：leaf，計(jì)算樹(shù)的葉子文件中用到的他處定義的全局變量及其出處：無(wú)與其他文件的依賴關(guān)系：2.關(guān)于類的說(shuō)明：類名稱： BiTNode定義該類的目的：結(jié)點(diǎn)類的結(jié)構(gòu)體，組成二叉樹(shù)類屬性：類中函數(shù)及功能：無(wú)與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對(duì)象中的什么函數(shù)）：3. 關(guān)于函數(shù)的說(shuō)明 (1) 函數(shù)名稱：bool CreateBT(BiTree *T)函數(shù)功能描述：創(chuàng)建一棵二叉樹(shù)，并用二叉鏈表存儲(chǔ)函數(shù)調(diào)用之前的預(yù)備條件：指向結(jié)構(gòu)體的指針的指針?lè)祷睾蟮奶幚恚簞?chuàng)建了一棵二叉樹(shù)返回值（如果有的話）：true or false函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)(2) 函數(shù)名

6、稱：bool Recursion_PreOrder(BiTree T)函數(shù)功能描述：前序遞歸遍歷二叉樹(shù)函數(shù)調(diào)用之前的預(yù)備條件：指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚捍蛴《鏄?shù)上結(jié)點(diǎn)的信息返回值（如果有的話）true or false函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)(3) 函數(shù)名稱：bool Non_Recursion_Preorder(BiTree T)函數(shù)功能描述：非前序遞歸遍歷二叉樹(shù)函數(shù)調(diào)用之前的預(yù)備條件：指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚捍蛴《鏄?shù)上結(jié)點(diǎn)的信息返回值（如果有的話）true or false函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)(4) 函數(shù)名稱：int Height(BiTree T)函

7、數(shù)功能描述：計(jì)算樹(shù)的高度函數(shù)調(diào)用之前的預(yù)備條件：一個(gè)指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚悍祷刂担ㄈ绻械脑挘簶?shù)的高度函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)(5)函數(shù)名稱：void Indented_Printed(BiTree T)函數(shù)功能描述：縮格打印二叉樹(shù)上各結(jié)點(diǎn)的信息函數(shù)調(diào)用之前的預(yù)備條件：一個(gè)指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚悍祷刂担ㄈ绻械脑挘簑無(wú)函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)(6)函數(shù)名稱：void Hierarchy_Traversal(BiTree T)函數(shù)功能描述：層次遍歷二叉樹(shù)函數(shù)調(diào)用之前的預(yù)備條件：一個(gè)指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚悍祷刂担ㄈ绻械脑挘簾o(wú)函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的

8、輸出參數(shù)：無(wú)(7)函數(shù)名稱：void swap(BiTree T)函數(shù)功能描述：交換二叉樹(shù)的左右孩子函數(shù)調(diào)用之前的預(yù)備條件：一個(gè)指向結(jié)點(diǎn)的指針?lè)祷睾蟮奶幚恚悍祷刂担ㄈ绻械脑挘簾o(wú)函數(shù)的輸入?yún)?shù)：無(wú)函數(shù)的輸出參數(shù)：無(wú)*/#include"iostream"#include"stack"#include"queue"using namespace std;int leaf=0;/二叉樹(shù)的葉子數(shù)typedef struct BiTNode/創(chuàng)建二叉樹(shù)所需的結(jié)構(gòu)體結(jié)點(diǎn) char data;/結(jié)點(diǎn)里存的信息 struct BiTNode *l

9、child,*rchild;/結(jié)點(diǎn)的左右孩子BiTNode,*BiTree;/bool CreateBT(BiTree *T)/創(chuàng)建一棵二叉樹(shù) char ch; cin>>ch; if(ch='/') *T=NULL; else if(!(*T=(BiTree)malloc(sizeof(BiTNode) return false;/申請(qǐng)結(jié)點(diǎn)空間，若申請(qǐng)失敗，返回false (*T)->data=ch; CreateBT(&(*T)->lchild);/遞歸創(chuàng)建左孩子 CreateBT(&(*T)->rchild);/遞歸創(chuàng)建右孩子

10、 return true;/bool Recursion_PreOrder(BiTree T)/樹(shù)的遞歸遍歷 if(T)/若結(jié)點(diǎn)不為空 cout<<T->data<<' '/打印結(jié)點(diǎn)上的信息 if (!T->lchild&&!T->rchild) leaf+=1;/當(dāng)左右孩子都沒(méi)有時(shí)，是葉子 Recursion_PreOrder(T->lchild);/遞歸遍歷左孩子 Recursion_PreOrder(T->rchild);/遞歸遍歷右孩子 return true;/bool Non_Recursion_

11、Preorder(BiTree T)/樹(shù)的非遞歸遍歷stack<BiTree> s;/定義一個(gè)堆棧,當(dāng)訪問(wèn)左孩子時(shí)，用來(lái)存放右孩子/s.makeempty();s.push(NULL);/while循環(huán)結(jié)束的條件BiTNode *p;p=T;/p指向根結(jié)點(diǎn)while(p)/當(dāng)結(jié)點(diǎn)不為空時(shí)cout<<p->data<<' '/打印結(jié)點(diǎn)上的信息 if(p->rchild) s.push(p->rchild);/如果這個(gè)結(jié)點(diǎn)又右孩子，先讓右孩子進(jìn)棧if(p->lchild) p=p->lchild;/如果有左孩子，訪問(wèn)

12、左孩子elseif(!s.empty() p=s.top();s.pop();/沒(méi)有左孩子，棧非空的時(shí)候拋出棧頂元素return true;/int Height(BiTree T)if(T=NULL) return 0;int l=Height(T->lchild);/遞歸訪問(wèn)左子樹(shù)int r=Height(T->rchild);/遞歸訪問(wèn)右子樹(shù)if(l>r) return l+1;/左子樹(shù)的高度大于右子樹(shù)的高度，左子樹(shù)的高度加1，返回左子樹(shù)的高度else return r+1;/右子樹(shù)的高度大于左子樹(shù)的高度，右子樹(shù)的高度加1，返回右子樹(shù)的高度/void Indented_

13、Printed(BiTree T)/縮格打印queue<BiTree> q;BiTNode *p;if(T=NULL) cout<<" empty tree"<<endl;/若樹(shù)空，打印提示信息elsewhile(q.empty()/當(dāng)創(chuàng)建的隊(duì)列為空時(shí)q.push(T);/將根結(jié)點(diǎn)進(jìn)隊(duì)列q.push(NULL);/空 是用來(lái)區(qū)分當(dāng)前訪問(wèn)結(jié)點(diǎn)是不是其所在的層的最后一個(gè)結(jié)點(diǎn)cout<<' 'p=T;while(p)if(p->lchild) q.push(p->lchild);/有左孩子，左孩子進(jìn)隊(duì)列i

14、f(p->rchild) q.push(p->rchild);/有右孩子，右孩子進(jìn)隊(duì)列cout<<p->data<<' 'q.pop();/將p的左右孩子進(jìn)隊(duì)列之后，將p出隊(duì)列if(q.front()=NULL) q.push(NULL);cout<<endl<<' 'q.pop();/此時(shí)，若隊(duì)頭元素為空，說(shuō)明剛才出隊(duì)列的元素是某一層的最后一個(gè)元素，打印空格，將空拋出if(!q.empty() p=q.front();/p指向隊(duì)頭else break;/void Hierarchy_Traver

15、sal(BiTree T)/層次遍歷，與縮格打印的思想一樣，就是沒(méi)有放空的操作queue<BiTree> q;BiTNode *p;if(T=NULL) cout<<"empty tree"<<endl;elsewhile(q.empty()q.push(T);p=T;while(p)if(p->lchild) q.push(p->lchild);if(p->rchild) q.push(p->rchild);/p左右孩子都進(jìn)隊(duì)列之后，將p出隊(duì)列cout<<p->data<<'

16、 'q.pop();if(!q.empty() p=q.front();/移動(dòng)指針pelse break;/void swap(BiTree T)/交換左右孩子BiTree w;if(T!=NULL)&&(T->lchild!=NULL)|(T->rchild!=NULL)/當(dāng)左右孩子不全為空時(shí)，交換左右孩子w=T->lchild;T->lchild=T->rchild;T->rchild=w;swap(T->lchild);swap(T->rchild);/int main() BiTree bt;cout<<

17、;"Please input data:"<<endl; CreateBT(&bt);/創(chuàng)建一棵二叉樹(shù)cout<<endl<<"Non_Recursion_Preorder:"Non_Recursion_Preorder(bt); cout<<endl<<"Recursion_PreOrder :"Recursion_PreOrder(bt);cout<<endl<<"Hierarchy_Traversal :"Hierar

18、chy_Traversal(bt);cout<<endl<<"Indented_Printed :"<<endl<<endl;Indented_Printed(bt);swap(bt);cout<<endl<<"The Tree has been swapped."<<endl;cout<<endl<<"Hierarchy_Traversal :"Hierarchy_Traversal(bt);cout<<endl<<"Swapped_Indented_Printed:"<<endl&