資源描述：
《叉樹的存儲結(jié)構(gòu)和遍歷算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、五、遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲結(jié)構(gòu)作業(yè)：6.3,6.5,6.13,6.14,6.33,6.37,6.4311、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點”的操作改為：若是葉子，則計數(shù)器增1。2voidCountLeaf(BiTreeT,int*count){//求葉子結(jié)點的個數(shù)，T為根結(jié)點的指針if(T)
2、{if((!T->lchild)&&(!T->rchild))(*count)++;//若T是葉子結(jié)點，對其計數(shù)CountLeaf(T->lchild,count);//對左子樹中葉結(jié)點計數(shù)CountLeaf(T->rchild,count);}//if}//CountLeaf（方法1：利用參數(shù)返回結(jié)果）注：在主調(diào)函數(shù)中應(yīng)將count所指單元賦初值為0。3intLeafCount_BiTree(BitreeT)//求二叉樹中葉子結(jié)點的數(shù)目{if(!T)return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchil
3、d)return1;//葉子結(jié)點elsereturnLeafCount_BiTree(T->lchild)+LeafCount_BiTree(T->rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)}//LeafCount_BiTree（方法2：利用函數(shù)返回值得到結(jié)果）42、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加1。首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。5
4、intBiTreeDepth(BiTreeT){//返回二叉樹的深度,T為樹根的指針if(!T)depthval=0;else{depthLeft=BiTreeDepth(T->lchild);depthRight=BiTreeDepth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}后序遍歷求深度64、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法至少掌握一種建樹算法7?以字符串的形式根左子樹右子樹定
5、義一棵二叉樹例如:ABCD以空白字符“”表示空樹ABCD只含一個根結(jié)點的二叉樹A以字符串“A”表示以下列字符串表示8StatusCreateBiTree(BiTree&T){//按先序次序輸入結(jié)點信息scanf(&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//生成根結(jié)點CreateBiTree(T->lchild);//構(gòu)造左子樹CreateBiTree(T->rchild);//構(gòu)造右子樹}r
6、eturnOK;}//CreateBiTree,無頭結(jié)點//在先序遍歷過程中完成，對根結(jié)點的訪問是“生成一個結(jié)點”9ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^看隨書光盤DSDemoW演示10?由原始表達(dá)式建樹算法這個算法如有同學(xué)感興趣，可以上網(wǎng)搜索收看嚴(yán)蔚敏本人的教學(xué)視頻，有詳細(xì)介紹（其中還有其他一些本書沒介紹的建樹算法）。同學(xué)們可以聽聽嚴(yán)的教學(xué)，補缺補差。由二叉樹的廣義表表示建立存儲結(jié)構(gòu)的算法請參考徐孝凱編寫的《數(shù)據(jù)結(jié)構(gòu)課程實驗》第59頁。此作為上機操作的一個內(nèi)容。11對于一個完全二叉樹來說，利用先序序列、中序序列和后序序列
7、可以確定此樹。然而，對于一個一般的二叉樹，僅知二叉樹的先序序列“abcdefg”不能唯一確定一棵二叉樹。如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？?由二叉樹的先序和中序序列建樹二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根121.根據(jù)先序序列的第一個元素建立根結(jié)點；2.在中序序列中找到該元素，確定根結(jié)點的左右子樹的中序序列；3.在先序序列中確定左右子樹的先序序列；4.由左子樹的先序序列和中序序列建立左子樹；5.由右子樹的先序序列和中序序列建立右子樹。已知一棵二叉樹的先序序列和中序序列，構(gòu)造該二叉樹的過程如下：
8、abcdefgcbdaegf先序序列中序序列13abcdefgcbdaegf例如:abcdefg^^^^^^^^先序序列中序序列14例1.已知樹的先序次序為abdcegf中序次序為bdaegc
