【正文】 e0TElem *rt, TElem *e)：廣義表串行化。將以 rt為根的二出叉樹中各結(jié)點的內(nèi)容的地址，按廣義表形式輸出到 e，返回 g廣義表的元素個數(shù)。 167。 操作的實現(xiàn) 167。 作的實現(xiàn) ? (一 ) 前序遞歸算法 ? 由于二叉樹的前序遍歷的定義是按遞歸方式描述的，所以它的算法的描述采用遞歸方式是自然且簡潔的，具體的C++語言描述見下面的程序 template class TElemlong TBinTreeTElem:: ClusterPre(TBinTreeNode0TElem* pNode, TElem ** e, longamp。 t) {//前序遍歷以 pNode為根的二叉樹樹，將遍歷到的結(jié)點的指針存放在指針數(shù)組 e中 , //將遍歷到的結(jié)點的個數(shù)存放在 t，并將其作為返回值。調(diào)用該函數(shù)前，實參 t應(yīng)為 0值。 if (pNode==NULL) return 0。 e[t++]=amp。(pNode GetElem())。 //訪問根結(jié)點 ClusterPre(pNodeGetSon(1), e, t)。 //前序遍歷根 的左子樹 ClusterPre(pNodeGetSon(2), e, t)。 //前序遍歷根 的右子樹 return t。 //返回遍歷到的結(jié)點的數(shù)目 } 在 ClusterPre中增加的參數(shù) t不屬于函數(shù)接口，只是為了函數(shù)的實現(xiàn)而引入的，所以參數(shù) t的出現(xiàn)，破壞接口的“ 友好性 ” 。為解決該問題，我們對 ClusterPre進行 “ 包裝 ” ： template class TElem longTBinTreeTElem::ClusterPre(TBinTreeNode0 TElem* pNode, TElem ** e) { long t=0。 return ClusterPre(pNode, e, t)。 } 這樣，我們就可避免直接調(diào)用 ClusterPre(pNode, e, t)。 這種 “ 包裝 ” 方法很常用，特別是對遞歸程序 (二 ) 遞歸算法的跟蹤 為了便于對遞歸算法的理解，這里用證明樹的形式給出遞歸算法對圖 60所示樹的執(zhí)行過程的示意圖（ 圖 60）。 在圖 60中，用 C(x)表示前序遍歷算法，它表示前序遍歷以 x為根的子樹，用 P(x)表示輸出 /訪問結(jié)點 x. 方框中左邊括號中的數(shù)字表示子程序調(diào)用序號。某方框的各個下屬方框表示該方 框?qū)?yīng)的子程序的執(zhí)行的各個主要步驟（一次子程序調(diào)用）。 從圖中知，在步驟 14中分別輸出了結(jié)點 a、 b、d、 e、 c，這正是前序遍歷結(jié)果。 a b c d e 圖 一棵二叉數(shù) (1) C(a) (2) P(a) 輸出 : a (3) C(alc) (13) C(arc) (6) C(brc) (4) P(b) 輸出 : b (5) C(blc) (14) P(c) 輸出 : c (7) P(d) 輸出 : d (8) C(dlc) (12) C(drc) (9) P(e) 輸出 : e (10) C(elc) (11) C(erc) (16) C(crc) (15) C(clc) 圖 所示二叉樹的前序遍歷遞歸算法執(zhí)行過程 (三 ) 前序遍歷非遞歸算法 ? 一般而言，遞歸算法的效率比非遞歸低。對遍歷算法，如果不采用高級語言的遞歸機制，遍歷算法描述要復(fù)雜一些。由前序遍歷的定義知，遍歷某樹時，是從根起，順左分枝往下搜索，每搜索到一個結(jié)點，就訪問該結(jié)點，直到遇到?jīng)]有左分枝的結(jié)點為止。然后，返回到已搜索過的最近一個有右兒子的且該右兒子尚未被訪問過的結(jié)點處，按同樣的方法順著它的右分枝往下搜索（訪問），如此一直進行，直到所有結(jié)點均已處理完。 ? 在訪問完某結(jié)點后，不能立即放棄它，因為遍歷完它的左子樹后，要從它的右兒子起遍歷，所以在訪問完某結(jié)點后，應(yīng)保存它的指針，以便以后能從它找到它的右兒子。由于較先訪問到的結(jié)點較后才重新利用，故應(yīng)將訪問到的結(jié)點按棧的方式保存。具體的實現(xiàn)程序如下。 template class TElemlong TBinTreeTElem:: ClusterPre2(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pNodes) {//前序遍歷非遞歸程序。前序遍歷以 pNode為根的樹，將遍歷到的結(jié)點的指針存于 pNodes //返回遍歷到的結(jié)點的數(shù)目 long t=0。 long nNodes。 long top=0。 TBinTreeNodeTElem** sk。 TBinTreeNodeTElem* p。 nNodes=GetHeight(pNode)。 //調(diào)用成員函數(shù)求樹高，以確 定棧的大小 if (nNodes=0) return 0。 sk =new (nothrow) TBinTreeNodeTElem *[nNodes+1]。 //分配?？臻g，棧元素為結(jié)點指針 if (sk==NULL) throw TExcepComm(3)。 p =(TBinTreeNodeTElem *) pNode。 //令 p開始時指向根 while (p!=NULL || top!=0) { if (p!=NULL) { pNodes[t++]= p。 //訪問元素（存入 pNodes） top++。 sk[top]=p。 //p進棧 p = (TBinTreeNodeTElem *)pGetSon(1)。 //令 p指 向 p的左兒子 } else {//已走到左分枝的底，返回到父親或其他祖輩的右兒子（結(jié)點）處 //若該結(jié)點無右兒子，則 p==NULL，從而在下次循環(huán)時，右進入該分枝，繼續(xù)回退 p = sk[top]。 top。 //退棧 p = (TBinTreeNodeTElem *)pGetSon(2)。 //令 p指向原棧頂元素的右兒子 } } //while delete[] sk。 //釋放所分配的?？臻g return t。 //返回所訪問到的結(jié)點數(shù)目 } ? 為了容易理解該算法，下面我們展示該算法的執(zhí)行過程，如表 61所示。表中的步驟 i是指第 i次循環(huán)剛剛執(zhí)行完，而第 (i+1)次尚未開始。 ? 上一小節(jié)和這里分別針對遞歸算法和非遞歸算法，給出了跟蹤執(zhí)行過程的示例。雖然是具體例子，但它們的方法具有普遍意義。當(dāng)一個算法很難理解或出了難以發(fā)現(xiàn)的錯誤，都可用這些方法試驗。 ? 時空復(fù)雜度分析 ：該算法每循環(huán)一次， p指向一個結(jié)點或空目標(biāo)，所指向的空目標(biāo)是無左兒子或無右兒子的結(jié)點的空鏈域，因此所指向的空目標(biāo)的次數(shù)為 (n+1)， n為結(jié)點個數(shù)，故循環(huán)次數(shù)為 n+(n+1)=2n+1，從而算法的時間復(fù)雜度為 O(n)。由于每個結(jié)點恰好進棧 1次，所以?？臻g最大需求量是 n（當(dāng)樹蛻化為線性鏈時達到最大）。 表 61 二叉樹非遞歸算法執(zhí)行過程 步驟 P所指 棧中內(nèi)容 訪問到的結(jié)點 說明 0 A 空 進入循環(huán)前 1 B a a a進棧 ， p指向 a的左兒 (b) 2 ^ a b b b進棧 ， p指向 b的左兒 (空 ) 3 D a b出棧 ， p指向 b的右兒 (d) 4 E a d d d進棧 ， p指向 d的左兒 (e) 5 ^ a d e e e進棧 ， p指向 e的左兒 (空 ) 6 ^ a d e出棧 ， p指向 e的右兒 (空 ) 7 ^ a d出棧 ， p指向 d的右兒 (空 ) 8 C 空 a出棧 ， p指向 a的右兒 (c) 9 ^ c c c進棧 ， p指向 c的左兒 (空 ) 10 ^ 空 定義 1. c出棧 ， p指向 c的右兒 (空 ) 11 結(jié)束 167。 中序遍歷操作的實現(xiàn) (一 ) 遞歸算法 中序遍歷的遞歸算法也是很直接的，具體描述見下面的程序。該程序與前面介紹的前序遍歷遞歸程序類似，主要不同是，該程序中，訪問結(jié)點的操作出現(xiàn)在遍歷左子樹和遍歷右子樹的兩個操作之間。 template class TElem long TBinTreeTElem::ClusterIn (TBinTreeNode0TElem* pNode, TElem ** e, longamp。 t) { if (pNode==NULL) return 0。 ClusterIn(pNodeGetSon(1), e, t)。 e[t++]=amp。(pNodeGetElem())。 //訪問根結(jié)點 ClusterIn(pNodeGetSon(2), e, t)。 return t。 } template class TElem ClusterIn(TBinTreeNode0TElem* pNode, TElem ** e) { long t=0。 return ClusterIn(pNode, e, t)。 } (二 ) 非遞歸算法 中序遍歷非遞歸算法與前序遍歷非遞歸很相似。在前序遍歷中，每搜索到一個結(jié)點，就訪問它，并將它推進棧。但在中序遍歷中，搜索到結(jié)點時并不能立即訪問，只是將它推進棧，等到左分枝搜索完后再從棧中彈出并訪問之。由此可知，中序遍歷的非遞歸算法，只需在前序遍歷非遞歸程序的基礎(chǔ)上，將訪問結(jié)點語句調(diào)到出棧語句后即可。 template class TElem long TBinTreeTElem:: ClusterIn2(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pNodes) { long t=0。 long nNodes。 long top=0。 TBinTreeNodeTElem** sk。 TBinTreeNodeTElem* p。 nNodes=GetHeight(pNode)。 if (nNodes=0) return 0。 sk =new TBinTreeNodeTElem *[nNodes+1]。 if (sk==NULL) throw TExcepComm(3)。 p =(TBinTreeNodeTElem *) pNode。 while (p!=NULL || top!=0) { if (p!=NULL) { top++。 sk[top]=p。 p = (TBinTreeNodeTElem *)pGetSon(1)。 } else { p = sk[top]。 top。 pNodes[t++]= p。 p = (TBinTreeNodeTElem *) pGetSon(2)。 } } //while delete[] sk。