【文章內(nèi)容簡介】 但不能區(qū)分是左兒還是右兒。為了解決該問題，可在結(jié)點上設(shè)立左右兒標志位。因此，一指針式存儲在存儲了左右兒標志的情況下，是關(guān)系完備的（即存儲了全部關(guān)系信息）。 ? 顯然，對一指針結(jié)構(gòu)，只有知道每個葉子的地址，才能訪問到一棵樹中的每個結(jié)點。因此，需要將一棵樹中各個葉子的地址記錄下來。為此，對每棵樹，設(shè)立一個數(shù)組，將各葉子地址分別保存在數(shù)組的各個元素中。一指針式的結(jié)點結(jié)構(gòu)如圖 60(a)，示例如圖 60(b)。 內(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è)立指向其后繼的指針。由于二叉樹每個結(jié)點的后繼最多有兩個，故每個結(jié)點需設(shè)二個后繼指針，分別稱為左兒指針和右兒指針。 顯然，在這種儲存方式下，從根出發(fā)可以訪問到所有結(jié)點，所以，記錄下根的地址后，就可以訪問到各個元素。因此，二指針式在已知根的情況下，是關(guān)系完備的。 雖然已知某結(jié)點的指針，很容易找到它的兒子，但要找到它的父親，一般需從根起搜索，很耗時。二指針式的結(jié)點結(jié)構(gòu)如圖 60 (b) ，示例如圖 60 (c)。 (三 )三指針式 三指針式是一指針和二指針的結(jié)合，即每個結(jié)點分別設(shè)立三個指針，分別指向其前驅(qū)和兩個后繼。三指針式同時具有一指針和二指針的的優(yōu)點，當然是通過存儲空間換來的。三指針式的結(jié)點結(jié)構(gòu)如圖 60 (c)，示例如圖 60 (d)。 顯然，三指針式在關(guān)系存儲方面有冗余（我們前面已指出，二指針是關(guān)系完備的）。與普通鏈式存儲一樣，二叉樹的鏈式存儲也既可以是“靜態(tài)”的，也可以是“動態(tài)”的。不過，由于動態(tài)鏈式更多地隱蔽了存儲管理細節(jié)，使我們能用更多的精力考慮其他問題，所以，我們下面一般以動態(tài)為主。當然，也將適當介紹靜態(tài)方法。 (四 ) 存儲結(jié)構(gòu)的高級語言描述 下面給出二叉樹結(jié)點（三指針）的數(shù)據(jù)部分的C++描述。關(guān)于它的完整對象描述，將在后面給出。 template class TElem //對樹結(jié)點內(nèi)容使用可變類型 struct TBinTreeNode { TElem info。 //樹結(jié)點內(nèi)容，類型為可變類型（類模板） TBinTreeNode *father。 //父指針 TBinTreeNode *lc, *rc。 //左兒指針、右兒指針 }。 167。 二叉樹對象模型 下面將二叉樹看作一個獨立的對象，給出它的屬性和方法（基本操作）接口描述。二叉樹對象主要涉及兩個類：樹結(jié)點類TBinTreeNode0和樹類 TBinTree. 下面分別介紹。 167。 二叉樹結(jié)點對象 (一 ) 抽象結(jié)點 結(jié)點類 TBinTreeNode0是對二叉樹的元素結(jié)點的抽象，它規(guī)定了針對結(jié)點本身的基本操作接口，使各種具體的結(jié)點結(jié)構(gòu)，都可從它派生。在C++中，用純虛類表示。 從邏輯關(guān)系上講，每個二叉樹元素除應(yīng)包含相應(yīng)的內(nèi)容外，還應(yīng)包含表示關(guān)系的信息：兒子和父親指示器。由于元素內(nèi)容可通過類屬（參數(shù)化類型）表示，所以，在純虛類中可直接定義元素內(nèi)容，但對關(guān)系，就不易這樣處理，我們這里只給出它們的訪問接口，具體的結(jié)構(gòu)要根據(jù)具體的存儲方式確定。 這里的關(guān)于元素結(jié)點的抽象操作的設(shè)置，我們采用最小化的原則，即只設(shè)置針對結(jié)點本身的內(nèi)容和關(guān)系的操作，對涉及全局的操作，放到“樹類”中 下面是二叉樹元素結(jié)點的抽象結(jié)構(gòu)的定義。其中各成分從其名稱可自明。 template class TElem class TBinTreeNode0 { public: TElem info。 //樹結(jié)點內(nèi)容，使用可變類型 virtual TElemamp。 GetElem(){return info。}。 //讀元素內(nèi)容 virtual TBinTreeNode0* SetElem(TElem *e){info=*e。 return this。}。 //置元素值 virtual TBinTreeNode0* GetSon(char sonNo)=0。 //讀元素的兒子指針 virtual TBinTreeNode0* SetSon(char sonNo, TBinTreeNode0* pSon)=0。//置兒子指針 virtual TBinTreeNode0* GetFather()=0。 //讀父指針 virtual TBinTreeNode0* SetFather(char sonNo, TBinTreeNode0* f)=0。 //置父指針 char IsLeaf() {return GetSon(1)==NULL amp。amp。 GetSon(2)==NULL。}。 //判斷是否為葉子 }。 (二 ) 動態(tài)三指針結(jié)點 從上面給出的抽象類 TBinTreeNode0，可派生出各種具體存儲結(jié)構(gòu)的二叉樹結(jié)點。這里，我們給出一種存儲結(jié)構(gòu)：動態(tài)三指針鏈結(jié)構(gòu) TBinTreeNode，它適合于使用堆空間（通過 C++的 new、 malloc等建立）。 template class TElem class TBinTreeNode :public TBinTreeNode0TElem { public: TBinTreeNodeTElem *lc, *rc, *father。 //左兒指針、右兒指針、父指針 TBinTreeNode(){lc=rc=father=NULL。}。 //初始時，將各指針置為空 virtual TBinTreeNode0TElem* GetSon(char sonNo) {if (sonNo==1) return lc。 else return rc。}。 //讀出指定的兒子指針。 sonNo為 1時表示左兒，為 2時表示右兒，下同 virtual TBinTreeNode0TElem* SetSon(char sonNo, TBinTreeNode0TElem* pSon) {sonNo==1? lc= (TBinTreeNodeTElem* )pSon: rc=(TBinTreeNode TElem* )pSon。 return pSon。 }。//將 pSon設(shè)置為本對象的兒子（ sonNo=1時置為左兒，否則置為右兒） virtual TBinTreeNode0TElem* GetFather(){return father。}。//讀父指針 virtual TBinTreeNode0TElem*SetFather (TBinTreeNode0TElem* f)。 {father=(TBinTreeNodeTElem* )f。}。 //把 f置為本對象的父親 }。 該類是從 TBinTreeNode0派生而來，實現(xiàn)了TBinTreeNode0中規(guī)定的操作。 167。 二叉樹對象 ? 為了方便對整棵樹進行操作，設(shè)立二叉樹類 TBinTree。該類用于封裝具體的二叉樹實體及其相關(guān)操作。 ? TBinTree中包含的樹實體是由一個類型為 TBinTreeNode0的根指針 root所指出。由于在 C++中，指向基類的指針，可以直接指向該基類的派生類，而且，我們已在樹結(jié)點類中通過基本操作抽象隱蔽了結(jié)點的結(jié)構(gòu)，所以，該樹類對各種具體的樹結(jié)點都是兼容的。下面是該類的 C++描述。 enum TTraverseMode {PreOrder, InOrder, PostOrder, LevelOrder}。 //定義一個枚舉類型，表示樹的幾種遍歷方式 template class TElemclass TBinTree //樹類 { public: TBinTreeNode0TElem *root。 //指向所代表的樹的根 long numNodes。 //樹結(jié)點總數(shù) TBinTree()。 ~TBinTree()。 virtual TBinTreeNode0TElem* GetRoot(){return root。}。 virtual void SetRoot(TBinTreeNode0TElem* rt){root=rt。}。 virtual long GetLevel(TBinTreeNode0TElem* pNode)。 virtual long GetHeight(TBinTreeNode0TElem*pNode)。 virtual long GetNumSubNodes(TBinTreeNode0TElem* pNode)。 virtual long GetNumSubNodes(void)。 virtual long GetNumLeaves(TBinTreeNode0TElem* pNode)。 virtual long Cluster(TBinTreeNode0TElem* pNode,TElem **e,TTraverseMode tm)。 virtual long Cluster(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe,TTraverseMode tm)。 virtual long Cluster2(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe,TTraverseMode tm)。 virtual long ClusterDescendants(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe, TTraverseMode tm =PreOrder, int startLevel=1, int endLevel=1)。 virtual long ClusterAncestors(TBinTreeNode0TElem* pNode,TBinTreeNode0TElem **pe)。 virtual long ClusterAncestors(TBinTreeNode0TElem* pNode,TElem **e)。 virtual long ClusterAncestors(TElem amp。e, TBinTreeNode0 TElem**pNodes)。 virtual long ClusterJuniors(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe,TTraverseMode travMode=PreOrder, int startLevel=1, int endLevel=1)。 virtual long ClusterSeniors(TBinTreeNode0TElem* pNode, TBinTreeNode0TElem **pe, TTraverseMode