實驗六二叉樹的遞歸遍歷及其應(yīng)用(1)

1、實驗六二叉樹的遞歸遍歷及其應(yīng)用一、實驗?zāi)康?、深入了解二叉樹遞歸的邏輯結(jié)構(gòu)特征及其基本操作。2、了解二叉樹各種存儲結(jié)構(gòu)的特點及其適用范圍，熟練掌握二叉樹的二叉鏈表結(jié)構(gòu)的定義及其遞歸遍歷算法、按層次遍歷算法的c語言實現(xiàn)，能深入了解遞歸算法的執(zhí)行過程。3、熟練掌握二叉樹遞歸遍歷算法的應(yīng)用。一、實驗內(nèi)容和要求2、 設(shè)計并驗證如下算法：與“ 12.7.4參考源程序”類似，按中序序列輸入建立兩棵二 叉樹的二叉鏈表結(jié)構(gòu)，求雙分支結(jié)點數(shù)，判斷兩棵樹是否相等。3、設(shè)計并驗證如下算法：按層次遍歷二叉樹，打印結(jié)點所在的層次，并求該二叉樹的 寬度。二、實驗過程及結(jié)果(第一題)一、需求分析1、從鍵盤輸入二叉樹的序列，

2、但由于建樹是從根結(jié)點往下建立的，故只能輸入先 序序列，則按照中序建樹完成二叉樹的創(chuàng)建。2、從鍵盤輸入一段正確的序列后，按回車鍵自動生成二叉樹，若該序列不能生成 一顆二叉樹，則程序無法繼續(xù)進行，只能退出。3、程序能實現(xiàn)的功能包括：初始化二叉樹；創(chuàng)建一棵完整二叉樹；先中后序遍歷二叉樹;求二叉樹雙分支結(jié)點數(shù)；比較兩棵二叉樹是否相等；、概要設(shè)計1、二叉樹的抽象數(shù)據(jù)類型定義：ADT Bin aryTree數(shù)據(jù)對象D D是具有相同特征的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R若。=空，貝U只=空，稱 BinaryTree 為空二叉樹；若D!=空，則R=H, H是如下二元關(guān)系：(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素ro

3、ot，它在關(guān)系H下無前驅(qū)；(2) 若 D-root!= ，則存在 D-root=D1,Dr ，且 D1A Dr=Q；(3) 若 D1!二貝 D1中存在唯一元素x1 , H,且存在 D1上的關(guān)系H1包含于H;若Dr!=,則Dr中存在唯一的元素， H, 且存在 Dr 上的的關(guān)系 Hr 包含于 H; H=, , H1, Hr；(4) ( D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr,Hr) 是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篒n itBiTree(&BT)操作結(jié)果：構(gòu)造空二叉樹CreateBiTree(&BT)操作結(jié)果：建立二叉樹PreOrder(BT)初始條件：二

4、叉樹 BT已存在操作結(jié)果：先序遍歷In Order(BT)初始條件：二叉樹 BT已存在操作結(jié)果：中序遍歷PostOrder(BT)初始條件：二叉樹 BT已存在操作結(jié)果：后序遍歷Do_Bra nNu mber(BT)初始條件：二叉樹 BT已存在操作結(jié)果：求BT的雙分支結(jié)點數(shù)Same_CompareTree(BT_a,BT1_b)初始條件：二叉樹 BT_a BT_b已存在 操作結(jié)果：比較兩棵樹是否相等ADT Bi naryTree ;3. 本程序模塊結(jié)構(gòu)主函數(shù)模塊void mai n()初始化兩顆二叉樹；創(chuàng)建二叉樹BT_a,返回根結(jié)點 BT_a；getchar();創(chuàng)建二叉樹BT_b,返回根結(jié)點

5、BT_b;getchar();先、中、后序遍歷 BT_a和BT_b;if(兩棵樹相等)printf(相同);elseprintf(不同);輸出BT_a和BT_b的雙分支結(jié)點數(shù)；三、詳細設(shè)計1、基本數(shù)據(jù)類型操作二叉鏈表的存儲結(jié)構(gòu)typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild; /左右孩子指針BiTNode,*BiTree;四、調(diào)試分析1創(chuàng)建兩棵二叉樹程序便不能繼續(xù)運行，只能創(chuàng)建一棵樹，加了getchar()后便能操作，原因可能是換行符造成的。2、進行兩棵樹的比較時

6、不僅要保證各結(jié)點值相等，還要確保結(jié)構(gòu)相同，若結(jié)構(gòu)不 同，兩棵樹則不等，故采用遞歸算法。3、求雙分支結(jié)點數(shù)采用遞歸算法，一定要保證結(jié)束條件，此結(jié)束條件應(yīng)為結(jié)點為 空時返回0。五、用戶說明及測試結(jié)果1兩棵二叉樹不相等T o Create BinaripP Tt*ee Please Input Pvt Order ultli * #f : Ct&afce The Fiist Of Binary Ti?eea - c e id J Itilf ftglc4Create The Second OF Binae Tree : sibc It ltd ttlte ttttThe First OF Binar

7、y PT&Qvder Tvav&rsal = InOrd&r TTriee is cel jf srhlid ijefkerhcdPostOrd&p rpauepsal： jikhgFedcTh&Bin wTree9.and B isTheBinAPuIiees. Nuimbeh1TheBi_nTrees NumJbei?Tlie S&tond Of Binary Tpee PreOrdei Traversal： abcde I nOi*（iev Traveial： cbdaepogztOrideF1 rraweirseil: cdbePjess any key 七口 cont;nLieDif

8、ferent*f Double Branch is: 3f D口ufcle Brandi is -22、兩顆二叉樹相等To CreateTree, Flease Input TreCrder witliCreate The First Of Binary Tree= ceiffJ1tf Cicte The Second Of Binary Tree= ceittjtittf Thts Fipst Of Binary Tt*ee is：PreOrder Trauefsal： ceijfyItiid InOrder rvauetrsal:ijefIshcdPostOrfler Traversal：

9、 jiKhgfedcThe Second Of Binary PreOrder1 Trauersal： InOrder Traversal: FostOrder Trauersal：Tree lchild);(*BT)-data=ch;CreateBiTree(&(*BT)-rchild);/構(gòu)造左子樹/構(gòu)造右子樹else*BT=NULL;讀入#，返回空指針return OK;*PreOrder*Status PreOrder(BiTree BT) / 先序遍歷if(BT)if(!(BT-data)訪問結(jié)點先序遍歷左子樹先序遍歷右子樹return ERROR; prin tf(%c,BT-da

10、ta); PreOrder(BT-lchild); PreOrder(BT-rchild); return OK;/* InO rder*/中序遍歷左子樹訪問結(jié)點中序遍歷右子樹Status In Order(BiTree BT) / 中序遍歷 if(BT) if(!(BT-data) return ERROR;In Order(BT-lchild); prin tf(%c,BT-data); In Order(BT-rchild); return OK;*/后序遍歷/*PostOrder*Status PostOrder(BiTree BT) if(BT)后序遍歷左子樹后序遍歷右子樹訪問結(jié)點i

11、f(!(BT-data) return ERROR;PostOrder(BT-lchild); PostOrder(BT-rchild); prin tf(%c,BT-data); return OK;/*Do Bran Number*/int Do_Bra nNu mber(BiTree BT)if(!BT)return 0;elseif(BT-lchild&BT-rchild)return Do_Bra nNu mber(BT-lchild)+Do_Bra nNu mber(BT-rchild)+1; elsereturn Do_Bra nNu mber(BT-lchild)+Do_Bra nNu mber(BT-rchild);/*Same ompare*/Status Same_CompareTree(BiTree BT,BiTree BT1) 遞歸遍歷并比較 if(BT=NULL&BT1=NULL)return TRUE;兩棵樹均為空時認為相等else if(BT=NULL|BT1=NULL)return FALSE;else if(BT!=NULL&BT1!=NULL)if(BT-data=BT1-data