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