二叉樹遍歷--實(shí)驗(yàn)報(bào)告

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

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

3、 &T) ：中序(非遞歸)遍歷樹3) 數(shù)據(jù)結(jié)構(gòu)二叉鏈表存儲數(shù)據(jù)類型定義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、編寫算法實(shí)現(xiàn)二叉樹的非遞歸中序遍歷和求二叉樹高度。1) 問題描述：實(shí)現(xiàn)二叉樹的非遞歸中序遍歷和求二叉樹高度2) 實(shí)驗(yàn)要求：以二叉鏈表作為存儲結(jié)構(gòu)3) 實(shí)現(xiàn)過程：1、實(shí)現(xiàn)非遞歸中序遍歷代碼：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);實(shí)驗(yàn)步驟：1) 新建一個(gè)基于 Con sole Applicatio n的工程，工程名稱 BiTreeTest ;2) 新

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

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