【正文】 rSeniors(TElemamp。 e,TElem **es,TTraverseModetravMode=PreOrder, Int startLevel=1, int endLevel=1)。 e,TBinTreeNode0TElem **pe,TTraverseMode travMode=PreOrder, int startLevel=1, intendLevel=1)。 virtual long ClusterJuniors(TBinTreeNode0TElem* pNode, TElem**es,TTraverseMode travMode=PreOrder, int startLevel=1,intendLevel=1)。 virtual long ClusterDescendants(TElem amp。 virtual long ClusterDescendants(TElem amp。 virtual TBinTreeNode0TElem *DeleteSubTree (TBinTreeNode0TElem* pNode,char sonNo)。 virtual long ClusterJuniors(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe,TTraverseMode travMode=PreOrder, int startLevel=1, int endLevel=1)。 virtual long ClusterAncestors(TElem amp。 virtual long ClusterAncestors(TBinTreeNode0TElem* pNode,TBinTreeNode0TElem **pe)。 virtual long Cluster2(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe,TTraverseMode tm)。 virtual long Cluster(TBinTreeNode0TElem* pNode,TElem **e,TTraverseMode tm)。 virtual long GetNumSubNodes(void)。 virtual long GetHeight(TBinTreeNode0TElem*pNode)。}。}。 ~TBinTree()。 //指向所代表的樹的根 long numNodes。 enum TTraverseMode {PreOrder, InOrder, PostOrder, LevelOrder}。由于在 C++中，指向基類的指針，可以直接指向該基類的派生類，而且，我們已在樹結(jié)點類中通過基本操作抽象隱蔽了結(jié)點的結(jié)構(gòu)，所以，該樹類對各種具體的樹結(jié)點都是兼容的。該類用于封裝具體的二叉樹實體及其相關(guān)操作。 167。 //把 f置為本對象的父親 }。 {father=(TBinTreeNodeTElem* )f。}。 }。 sonNo為 1時表示左兒，為 2時表示右兒，下同 virtual TBinTreeNode0TElem* SetSon(char sonNo, TBinTreeNode0TElem* pSon) {sonNo==1? lc= (TBinTreeNodeTElem* )pSon: rc=(TBinTreeNode TElem* )pSon。}。 //初始時，將各指針置為空 virtual TBinTreeNode0TElem* GetSon(char sonNo) {if (sonNo==1) return lc。 //左兒指針、右兒指針、父指針 TBinTreeNode(){lc=rc=father=NULL。這里，我們給出一種存儲結(jié)構(gòu)：動態(tài)三指針鏈結(jié)構(gòu) TBinTreeNode，它適合于使用堆空間（通過 C++的 new、 malloc等建立）。 //判斷是否為葉子 }。 GetSon(2)==NULL。 //置父指針 char IsLeaf() {return GetSon(1)==NULL amp。//置兒子指針 virtual TBinTreeNode0* GetFather()=0。 //置元素值 virtual TBinTreeNode0* GetSon(char sonNo)=0。 return this。}。 //樹結(jié)點內(nèi)容，使用可變類型 virtual TElemamp。其中各成分從其名稱可自明。由于元素內(nèi)容可通過類屬（參數(shù)化類型）表示，所以，在純虛類中可直接定義元素內(nèi)容，但對關(guān)系，就不易這樣處理，我們這里只給出它們的訪問接口，具體的結(jié)構(gòu)要根據(jù)具體的存儲方式確定。在C++中，用純虛類表示。 167。 二叉樹對象模型 下面將二叉樹看作一個獨立的對象，給出它的屬性和方法（基本操作）接口描述。 //左兒指針、右兒指針 }。 //樹結(jié)點內(nèi)容，類型為可變類型（類模板） TBinTreeNode *father。關(guān)于它的完整對象描述，將在后面給出。當(dāng)然，也將適當(dāng)介紹靜態(tài)方法。與普通鏈式存儲一樣，二叉樹的鏈式存儲也既可以是“靜態(tài)”的，也可以是“動態(tài)”的。三指針式的結(jié)點結(jié)構(gòu)如圖 60 (c)，示例如圖 60 (d)。 (三 )三指針式 三指針式是一指針和二指針的結(jié)合，即每個結(jié)點分別設(shè)立三個指針，分別指向其前驅(qū)和兩個后繼。 雖然已知某結(jié)點的指針，很容易找到它的兒子，但要找到它的父親，一般需從根起搜索，很耗時。 顯然，在這種儲存方式下，從根出發(fā)可以訪問到所有結(jié)點，所以，記錄下根的地址后，就可以訪問到各個元素。 內(nèi)容 父指針 (a) 一指針結(jié)點 內(nèi)容 左兒指針 右兒指針 (b) 二指針結(jié)點 內(nèi)容 父指針 右兒指針 右兒指針 (c) 三指針結(jié)點 圖 二叉樹鏈式存儲方式的結(jié)點結(jié)構(gòu) 1 2 3 4 5 (a) 二叉樹 1 ^ 2 3 4 5 (b) (a)樹的一指針存儲 1 2 ^ 3 ^ ^ 4 ^ 5 ^ ^ (c) (a)樹的二指針存儲 1 ^ 2 ^ ^ ^ 4 ^ 5 ^ ^ (d) (a)樹的三指針存儲 圖 二叉樹鏈式存儲結(jié)構(gòu)示例 (二 )二指針式 這種方法是，為每個結(jié)點只設(shè)立指向其后繼的指針。為此，對每棵樹，設(shè)立一個數(shù)組，將各葉子地址分別保存在數(shù)組的各個元素中。 ? 顯然，對一指針結(jié)構(gòu)，只有知道每個葉子的地址，才能訪問到一棵樹中的每個結(jié)點。為了解決該問題，可在結(jié)點上設(shè)立左右兒標志位。顯然，這種存儲方式下，已知某結(jié)點的指針，很容易找到它的父親，但要找到它的兒子，需從葉子起搜索，很耗時。由于每個結(jié)點的前驅(qū)是唯一的，故每個結(jié)點只需設(shè)一個前驅(qū)指針。根據(jù)指針設(shè)置情況，存儲方式分為一指針式、二指針式和三指針式。 鏈式存儲 二叉樹一般多采用鏈式存儲。 這種存儲方式中，實結(jié)點是不連續(xù)出現(xiàn)的，所以，若虛結(jié)點對應(yīng)的存儲位置不能被利用，則是一種很大的浪費（虛結(jié)點數(shù)目可能很大），圖 60給出了這種存儲結(jié)構(gòu)的示例。這樣處理后，再按順序二叉樹的順序存儲方式存儲。這種存儲方式，邏輯結(jié)構(gòu)用存儲次序體現(xiàn)，故若不進行插入與刪除操作，是一種很經(jīng)濟的存儲方式。由定理 67知，對順序二叉樹，若已知結(jié)點的層序編號，則可推算出它的父親和兒子的編號，所以，在這種存儲結(jié)構(gòu)中，很容易根據(jù)結(jié)點的相對地址計算出它的父親和兒子的相對地址，方法是： ? x的相對地址 ?x的編號 ?x的父親 /兒子的編號 (性質(zhì) 7)? x的父親 /兒子的相對地址。 167。在具體的應(yīng)用中，可能要求從任一結(jié)點能直接訪問到它的后繼（即兒子），或直接訪問到它的前驅(qū)（父親），或同時直接訪問父親和兒子。 167。實例見圖 60. 遍歷是樹結(jié)構(gòu)的一種重要的操作（我們在后面還要給出一般樹的遍歷的概念），許多對樹的操作，都是基于遍歷的。在上面的定義中，始基就是“若樹為空，則不做任何動作”，若無此句，所定義的遍歷將是個無限動作。其實例見圖 60. 在上列三種方式的定義中，采用了遞歸描述方式，這種描述方式簡潔而準確。其實例見圖 60. (四 ) 后序遍歷 二叉樹后序遍歷定義為： 若樹為空，則不作任何動作，返回，否則，先分別按后序遍歷方式遍歷根的左子樹與右子樹，然后訪問根。前序遍歷實例見圖 60. 1 2 3 4 5 6 7 前序遍歷結(jié)果： 1 2 4 5 3 6 7 中序遍歷結(jié)果： 2 5 4 1 3 7 6 后序遍歷結(jié)果： 5 4 2 7 6 3 1 層序遍歷結(jié)果： 1 2 3 4 6 5 7 圖 6 0 二叉樹遍歷示例 (三 ) 中序遍歷 二叉樹中序遍歷定義為： 若樹為空，則不作任何動作，返回，否則，先按中序方式遍歷根的左子樹，然后訪問根，最后再按中序方式遍歷根的右子樹。 簡言之，前序遍歷是按“根 ─左子樹 ─右子樹”的次序遍歷二叉樹。 ? ? 二叉樹的遍歷方式有前序遍歷、中序遍歷、后序遍歷與層序遍歷四種，現(xiàn)分述如下。我們假定執(zhí)行訪問的機構(gòu)是單處理機的，任何時刻只能對一個目標進行訪問，所以，訪問的軌跡是被訪問結(jié)點的線性序列，即遍歷的結(jié)果是樹中各結(jié)點按某種次序的一個線性序列。不失一般性，我們在此將訪問看作是輸出。對于樹的遍歷，是指按一定方式訪問樹中的結(jié)點，使得每個結(jié)點恰好被訪問一次。 167。再考慮 k與 k+1不在同一層的情況，此時， k必在它所在層的最右，而 k+1必在下一層的最左，由于順序二叉樹編號是編完上層最右結(jié)點時從下層最左結(jié)點起編號，所以若 k+1有兒子，則編號必然為 (2i+1)+1與 (2i+1)+2，這與 k與 k+1位于同層的情況相同。若 k結(jié)點無左兒子或無右兒子，則 (k+1)亦必為葉子（否則就不是順序二叉樹了），故證明 (b)時無需考慮此情況，而只需考慮 k有兩個兒子的情況。當(dāng) i=1時，結(jié)論是顯然的。 (c)若 2i+1n，則結(jié)點 i無右孩子，否則它的右孩子結(jié)點的編號為 2i+1。由于 n與 2k1均為整數(shù)，為 2k11加一后，有可能與 n相等，但不會變得大于 n，故 n≥ 2k1，即 k≤ log2n+1 ………… ..(b ) 現(xiàn)在，我們已得到 (a)與（ b）兩式，即 log2n k≤ log2n+1 由于 k為整數(shù)，故必有 k=[log2n]+1（見圖 60） 1單位 1單位， k所在區(qū)間 log2n log2n+1 [log2n] 圖 6 0 log2nk≤log2n+1示意圖 [log2n]+1 定理 67：若對一棵順序二叉樹的結(jié)點按層序編號（即從根所在層起，依次從層號較小的層到層號較大的層、同層從左到右，給各結(jié)點依次編以連續(xù)的號碼），則對任一結(jié)點 i（ 1≤ i≤ n， n為結(jié)點數(shù)目， 1為根的編號），有 (a)若 i=1，則結(jié)點 i是根，無父親，若 i1，則其父親的編號為 [i/2]。又分枝是由度為 1和 2的結(jié)點射出的，故有 B=n1+2n2 結(jié)合上面三式，即可導(dǎo)出 n0=n2+1與 n=2n0+n11 定理 66：具有 n個結(jié)點的順序二叉樹的深度為 [log2n]+1（這里，