二叉樹遍歷--實驗報告

1、數據結構實驗報告報告題目：一叉樹的基本操作學生班級:學生姓名：學號:.實驗目的1、基本要求：深刻理解二叉樹性質和各種存儲結構的特點及適用范圍；掌 握用指針類型描述、訪問和處理二叉樹的運算；熟練掌握二叉樹的遍歷算 法；。2、 較高要求 : 在遍歷算法的基礎上設計二叉樹更復雜操作算法；認識哈夫曼樹、哈夫曼編碼的作用和意義 ; 掌握樹與森林的存儲與便利。二 . 實驗學時：課內實驗學時： 3 學時課外實驗學時： 6 學時三實驗題目1 以二叉鏈表為存儲結構，實現二叉樹的創(chuàng)建、遍歷(實驗類型：驗證型)1) 問題描述： 在主程序中設計一個簡單的菜單， 分別調用相應的函數功能： 1建立樹2前序遍歷樹3中序遍歷

2、樹4后序遍歷樹5求二叉樹的高度6求二叉樹的葉子節(jié)點7非遞歸中序遍歷樹0結束2) 實驗要求：在程序中定義下述函數，并實現要求的函數功能：CreateBinTree(BinTree &T):按從鍵盤輸入的前序序列，創(chuàng)建樹Preorder(BinTree &T) ：前序遍歷樹(遞歸)Inorder(BinTree &T) ：中序 ( 遞歸 ) 遍歷樹Postorder(BinTree &T):后序遍歷樹(遞歸)PostTreeDepth(BinTree &T) ：樹的高度 leaf(BinTree &T): 樹的葉子節(jié)點InorderN(BinTree

3、 &T) ：中序(非遞歸)遍歷樹3) 數據結構二叉鏈表存儲數據類型定義typedef struct nodeTElemType data;struct node *lchild,*rchild;BinTNode;元素類型：int CreateBinTree(BinTree &T);void Preorder(BinTree &T);void Inorder(BinTree &T);void Postorder(BinTree &T);void InorderN(BinTree &T);int PostTreeDepth(BinTree &

4、T);int leaf(BinTree &T);2、編寫算法實現二叉樹的非遞歸中序遍歷和求二叉樹高度。1) 問題描述：實現二叉樹的非遞歸中序遍歷和求二叉樹高度2) 實驗要求：以二叉鏈表作為存儲結構3) 實現過程：1、實現非遞歸中序遍歷代碼：void CBiTree:InorderN(BinTree &T)BinTree stackMAX,p;int top=0;p=T;do while(p!=NULL) stacktop=p; top=top+1; p=p->lchild;if(top>0)top=top-1; p=stacktop;printf("%3c

5、",p->data ); p=p->rchild;while(p!=NULL|top!=0);2、求二叉樹高度：int CBiTree:PostTreeDepth(BinTree &T)int l,r,max;if(T!=NULL)l=PostTreeDepth(T->lchild ); r=PostTreeDepth(T->rchild ); max=l>r?l:r;return(max+1);else return(O);實驗步驟：1) 新建一個基于 Con sole Applicatio n的工程，工程名稱 BiTreeTest ;2) 新

6、建一個類CBiTree二叉樹類。3) 在類CBiTree的頭文件上方定義二叉鏈表存儲數據類型結構體BiTNode。4) 在類 CBiTree 中定義函數 CreateBinTree ()； Preorder() ； Inorder()； Postorder();PostTreeDepth();l norderN()；5) 實 現函數 CreateB in Tree ( )； Preorder() ； In order()；Postorder();PostTreeDepth();I norderN()；6) 在主函數中定義對象，通過對象調用函數，實現各個函數的操作。運行結果：二叉樹建立ii歸先序

7、囑廳遞歸巾序遍廳非遞歸中序遍歷I-逵歸后序遍歷求二叉樹的直度?求二叉樹的子葉個數8退岀i育輸入要進行的操作:該二叉樹的噁陀先斤遍歷序列為: Ahri.cf q遞歸先序逼歷遞歸中序遍歷非遞歸口序遍歷遞歸后庫逼歷求二叉樹的高度農二對對的子葉個數退出青輸入要進行的操作， 核二叉樹的遞歸中序遍歷序列為: C:UscrsAd rniri5trotorDc5ktopBiTreeTc5tBiTrceTcstCebugvBiTrcc.exee1二叉樹建立2遡先序遍歷3噁中序遍歷4非遞歸中癢遍歷5遞啟序遍歷6農二義樹的昌度7求二叉樹的子葉個數8退出請輸人雯進行的操作：4該二叉樹的非遞歸中序遍歷序列為d b o a f c cf2遞歸先序遍歷3遞歸中序遍歷4非遞歸中庫漏力5噬歸后序遍歷6求二叉樹的髙.變V求二叉樹的子】廿遨8退出詩