樹的遍歷實驗報告

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

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

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

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

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

6、稱：bool Recursion_PreOrder(BiTree T)函數(shù)功能描述：前序遞歸遍歷二叉樹函數(shù)調(diào)用之前的預(yù)備條件：指向結(jié)點的指針返回后的處理：打印二叉樹上結(jié)點的信息返回值（如果有的話）true or false函數(shù)的輸入?yún)?shù)：無函數(shù)的輸出參數(shù)：無(3) 函數(shù)名稱：bool Non_Recursion_Preorder(BiTree T)函數(shù)功能描述：非前序遞歸遍歷二叉樹函數(shù)調(diào)用之前的預(yù)備條件：指向結(jié)點的指針返回后的處理：打印二叉樹上結(jié)點的信息返回值（如果有的話）true or false函數(shù)的輸入?yún)?shù)：無函數(shù)的輸出參數(shù)：無(4) 函數(shù)名稱：int Height(BiTree T)函

7、數(shù)功能描述：計算樹的高度函數(shù)調(diào)用之前的預(yù)備條件：一個指向結(jié)點的指針返回后的處理：返回值（如果有的話）：樹的高度函數(shù)的輸入?yún)?shù)：無函數(shù)的輸出參數(shù)：無(5)函數(shù)名稱：void Indented_Printed(BiTree T)函數(shù)功能描述：縮格打印二叉樹上各結(jié)點的信息函數(shù)調(diào)用之前的預(yù)備條件：一個指向結(jié)點的指針返回后的處理：返回值（如果有的話）：w無函數(shù)的輸入?yún)?shù)：無函數(shù)的輸出參數(shù)：無(6)函數(shù)名稱：void Hierarchy_Traversal(BiTree T)函數(shù)功能描述：層次遍歷二叉樹函數(shù)調(diào)用之前的預(yù)備條件：一個指向結(jié)點的指針返回后的處理：返回值（如果有的話）：無函數(shù)的輸入?yún)?shù)：無函數(shù)的

8、輸出參數(shù)：無(7)函數(shù)名稱：void swap(BiTree T)函數(shù)功能描述：交換二叉樹的左右孩子函數(shù)調(diào)用之前的預(yù)備條件：一個指向結(jié)點的指針返回后的處理：返回值（如果有的話）：無函數(shù)的輸入?yún)?shù)：無函數(shù)的輸出參數(shù)：無*/#include"iostream"#include"stack"#include"queue"using namespace std;int leaf=0;/二叉樹的葉子數(shù)typedef struct BiTNode/創(chuàng)建二叉樹所需的結(jié)構(gòu)體結(jié)點 char data;/結(jié)點里存的信息 struct BiTNode *l

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

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

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

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

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

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

15、sal(BiTree T)/層次遍歷，與縮格打印的思想一樣，就是沒有放空的操作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左右孩子都進隊列之后，將p出隊列cout<<p->data<<'

16、 'q.pop();if(!q.empty() p=q.front();/移動指針pelse break;/void swap(BiTree T)/交換左右孩子BiTree w;if(T!=NULL)&&(T->lchild!=NULL)|(T->rchild!=NULL)/當左右孩子不全為空時，交換左右孩子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)建一棵二叉樹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&