【正文】 。 p = (TBinTreeNodeTElem *) pGetSon(2)。 top。 p = (TBinTreeNodeTElem *)pGetSon(1)。 while (p!=NULL || top!=0) { if (p!=NULL) { top++。 if (sk==NULL) throw TExcepComm(3)。 if (nNodes=0) return 0。 TBinTreeNodeTElem* p。 long top=0。 template class TElem long TBinTreeTElem:: ClusterIn2(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pNodes) { long t=0。但在中序遍歷中，搜索到結點時并不能立即訪問，只是將它推進棧，等到左分枝搜索完后再從棧中彈出并訪問之。 } (二 ) 非遞歸算法 中序遍歷非遞歸算法與前序遍歷非遞歸很相似。 } template class TElem ClusterIn(TBinTreeNode0TElem* pNode, TElem ** e) { long t=0。 //訪問根結點 ClusterIn(pNodeGetSon(2), e, t)。 e[t++]=amp。 t) { if (pNode==NULL) return 0。該程序與前面介紹的前序遍歷遞歸程序類似，主要不同是，該程序中，訪問結點的操作出現在遍歷左子樹和遍歷右子樹的兩個操作之間。 表 61 二叉樹非遞歸算法執(zhí)行過程 步驟 P所指 棧中內容 訪問到的結點 說明 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 結束 167。 ? 時空復雜度分析 ：該算法每循環(huán)一次， p指向一個結點或空目標，所指向的空目標是無左兒子或無右兒子的結點的空鏈域，因此所指向的空目標的次數為 (n+1)， n為結點個數，故循環(huán)次數為 n+(n+1)=2n+1，從而算法的時間復雜度為 O(n)。雖然是具體例子，但它們的方法具有普遍意義。表中的步驟 i是指第 i次循環(huán)剛剛執(zhí)行完，而第 (i+1)次尚未開始。 //釋放所分配的?？臻g return t。 //退棧 p = (TBinTreeNodeTElem *)pGetSon(2)。 //令 p指 向 p的左兒子 } else {//已走到左分枝的底，返回到父親或其他祖輩的右兒子（結點）處 //若該結點無右兒子，則 p==NULL，從而在下次循環(huán)時，右進入該分枝，繼續(xù)回退 p = sk[top]。 sk[top]=p。 //令 p開始時指向根 while (p!=NULL || top!=0) { if (p!=NULL) { pNodes[t++]= p。 //分配棧空間，棧元素為結點指針 if (sk==NULL) throw TExcepComm(3)。 //調用成員函數求樹高，以確 定棧的大小 if (nNodes=0) return 0。 TBinTreeNodeTElem* p。 long top=0。前序遍歷以 pNode為根的樹，將遍歷到的結點的指針存于 pNodes //返回遍歷到的結點的數目 long t=0。具體的實現程序如下。 ? 在訪問完某結點后，不能立即放棄它，因為遍歷完它的左子樹后，要從它的右兒子起遍歷，所以在訪問完某結點后，應保存它的指針，以便以后能從它找到它的右兒子。由前序遍歷的定義知，遍歷某樹時，是從根起，順左分枝往下搜索，每搜索到一個結點，就訪問該結點，直到遇到沒有左分枝的結點為止。 a b c d e 圖 一棵二叉數 (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í)行過程 (三 ) 前序遍歷非遞歸算法 ? 一般而言，遞歸算法的效率比非遞歸低。某方框的各個下屬方框表示該方 框對應的子程序的執(zhí)行的各個主要步驟（一次子程序調用）。 這種 “ 包裝 ” 方法很常用，特別是對遞歸程序 (二 ) 遞歸算法的跟蹤 為了便于對遞歸算法的理解，這里用證明樹的形式給出遞歸算法對圖 60所示樹的執(zhí)行過程的示意圖（ 圖 60）。 return ClusterPre(pNode, e, t)。 //返回遍歷到的結點的數目 } 在 ClusterPre中增加的參數 t不屬于函數接口，只是為了函數的實現而引入的，所以參數 t的出現，破壞接口的“ 友好性 ” 。 //前序遍歷根 的左子樹 ClusterPre(pNodeGetSon(2), e, t)。(pNode GetElem())。 if (pNode==NULL) return 0。 t) {//前序遍歷以 pNode為根的二叉樹樹，將遍歷到的結點的指針存放在指針數組 e中 , //將遍歷到的結點的個數存放在 t，并將其作為返回值。 操作的實現 167。將以 rt為根的二出叉樹中各結點的內容的地址，按廣義表形式輸出到 e，返回 g廣義表的元素個數。 PreOrderExToTree(TElem *nodes, int numElem)：類似于前，只是采用遞歸算法。根據二叉樹的前序遍歷結果的擴充，創(chuàng)建二叉樹，返回其根。gListExp中，結點用編號表示，它所對應的結點內容在 es[k]中，這里， k表示某結點在 gListExp中的編號。數組 gListExp中存放二叉樹的廣義表表達式，數組 es存放樹結點的內容。 GListToTree(long InPreToTree(long *gListExp, TElem *es, long numElem)：串行化結果的還原。p1,p2,i1,i2的設置，主要是為了遞歸的實現。根據二叉樹的中序遍歷結果和前序遍歷結果，創(chuàng)建二叉樹結構，返回所創(chuàng)建的樹的根。這里， sn相對于各個值為 e的結點，其可正可負，若值為 e的結點有 m個，則 sn=1表示查找其第 1個出現的（按遍歷次序）值為 e的結點， sn=1表示查找最后一個值為 e的結點，余類推。在以 rt為根的樹中，按指定的遍歷次序，查找元素值為 e的第 sn個出現的結點，返回其指針。 TBinTreeNode0TElem*Locate(TBinTreeNode0 TElem* rt,TElem amp。這里的查找方式是前序，即按前序遍歷的次序查找 e。在以 rt為根的樹中，查找元素值為 e的結點，返回其指針。對具有具體含義的二叉樹（如后面要介紹的二叉排序樹），可單獨刪除一個結點（不是整棵子樹），而將被刪結點的兒子做適當 “ 轉讓 ” 。將 pNode 的兒子號為 sonNo的子樹，連根一同摘取下來，并返回其根。 startLevel和 endLevel取負數時，表示層號從總根（ pNode所在樹的根）算起。 ClusterSeniors(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe, TTraverseMode travMode= PreOrder, int startLevel=1, int endLevel=1)：前輩聚集。將pNode的第 startLevel層到第 endLevel層的后輩結點，按遍歷次序 tm存入pe. 這里，層號 startLevel和 endLevel是相對于 pNode結點（其為第 1層），它們取負數時含義同前解釋。另一個 ClusterAncestors ()類似，不同的是存儲結點的內容的地址。將結點 pNode的各祖先結點的指針，按前序次序存入數組 pe，并返回其數目。 startLevel和 endLevel為正數時，層號相對于 pNode(其層號設為 1)，為負數時，表示 “ 倒數 ” ，即最深一層為 1，其上一層為 2，余類推。 ClusterDescendants(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe, TTraverseMode tm = PreOrder, int startLevel=1, int endLevel=1)：與上面的 Cluster類似，不同的是，這里只遍歷以 pNode為根的樹的 startLevel層到 endLevel層之間的結點（設 pNode為第一層）。 Cluster(TBinTreeNode0TElem* pNode, TBinTreeNode0 TElem **pe,TTraverseMode tm)：與上面的 Cluster類似，不同點是存儲（返回）各結點的指針。 Cluster(TBinTreeNode0TElem* pNode,TElem **e, TTraverseMode tm)：串行聚集：將以 pNode為根的樹中的各結點的內容的地址，按 tm遍歷次序存入 e中，并返回樹 pNode中結點總數。定義根的高度為 1，空樹的高度為(TBinTreeNode0TElem* pNode)：返回以 pNode為根的樹中的結點總數。定義根的層號為 1。 U 以上兩個操作用于隱蔽 root。 GetRoot()：返回樹根指針。 TBinTree()：構造函數，充當初始化操作，其主要任務是置root為空，表示當前包含的樹為空樹。 }。 virtual long TreeToGList(TBinTreeNode0TElem *rt, TElem*e)。 virtual TBinTreeNode0TElem *PreOrderExToTree(TElem *nodes, int numElem)。 virtual TBinTreeNode0TElem *Locate(TBinTreeNode0 TElem* rt,TElem *e)。virtual TBinTreeNode0TElem*Locate (TBinTreeNode0TElem* rt,TElem amp。 virtual long ClusterSeniors(TElemamp。 virtual long Cluste