50數(shù)據(jù)結(jié)構(gòu)-樹和森林

1、數(shù)據(jù)結(jié)構(gòu)-樹和森林數(shù) 據(jù) 結(jié) 構(gòu)主要內(nèi)容樹的概念二叉樹二叉樹的存儲結(jié)構(gòu)遍歷二叉樹線索二叉樹二叉樹的應(yīng)用樹的概念某家族的血統(tǒng)關(guān)系如下：張宇有四個孩子分別是：張山、張川、張星和張月；張山有二個孩子張冰和張雪；張星有三個孩子張雨、張云和張風；張云有兩個孩子張亮和張麗。 樹的定義： 樹（tree）T是一個包含n(n=0)個數(shù)據(jù)元素的有限集合。并且有：（1）當n=0時，T稱為空樹；（2）如果n0，則樹有且僅有一個特定的被稱為根（root）的結(jié)點，樹的根結(jié)點只有后繼，沒有前驅(qū)；（3）當n1時,除根結(jié)點以外的其余結(jié)點可分為m(m0)個互不相交的非空有限集T1、T2、.、Tm,其中每一個集合本身又是一棵非空樹

2、,并且稱它們?yōu)楦Y(jié)點的子樹（subtree）。 如右圖（a）表示了一棵空樹，它沒有數(shù)據(jù)元素； 如右圖（b）表示了只有一個數(shù)據(jù)元素的樹，樹中只有一個沒有子樹的根結(jié)點A； 如右圖（c）是有14個數(shù)據(jù)元素結(jié)點的樹，其中A是樹根，其余結(jié)點分成三個互不相交的有限集：T1=B,E,F,K,L、T2=C,G、T3=D,H,I,J,M,N，T1、T2、T3又都是樹，且它們是結(jié)點A的子樹。樹的術(shù)語： 1結(jié)點（node）：在樹中每一個數(shù)據(jù)元素及指向其子樹根的分支稱為一個結(jié)點。 2結(jié)點的度（degree of node）：一個結(jié)點的子樹數(shù)目稱之為該結(jié)點的度。例如在圖（c）所示的樹中, 結(jié)點A的度為3，結(jié)點C的度數(shù)為

3、1, 結(jié)點E的度數(shù)為0。 3終端結(jié)點(terminal node)：在樹中，度為0的結(jié)點稱為終端結(jié)點或葉子(leaf)。如在圖（c）所示的樹中，結(jié)點E，K，L，G，H，M，N，J都是樹的葉子。 4非終端結(jié)點(nonterminal node)：在樹中，度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。除根結(jié)點之外的分支結(jié)點也稱內(nèi)部結(jié)點。如在圖（c）所示的樹中，結(jié)點A、B、C、D、F、I都是樹的分支結(jié)點，且結(jié)點B、C、D、F、I是樹T的內(nèi)部結(jié)點。5樹的度（degree of tree）：樹的結(jié)點中，最大的度稱為該樹的度。如圖（c）所示的樹，其度為3。6孩子(child)和雙親(parent)：在樹中，結(jié)點

4、p的子樹的根稱為結(jié)點p的孩子；反之,這個結(jié)點p稱為其孩子的雙親（父親）。如在圖（c）所示的樹中，結(jié)點D為結(jié)點A的子樹的根，因此結(jié)點D是結(jié)點A的孩子，結(jié)點A是結(jié)點D的雙親結(jié)點（父結(jié)點）。7兄弟(sibling)：在樹中，同一個雙親的孩子之間互稱為兄弟。例如，在圖（c）所示的樹中，結(jié)點B、C、D互為兄弟。8祖先(ancestor)：在樹中，從根結(jié)點到結(jié)點x所經(jīng)的分支上的所有結(jié)點稱為結(jié)點x的祖先。如在圖（c）所示的樹中，結(jié)點M的祖先為：A、D、I。9子孫（descendant）：在樹中，以某結(jié)點p為根的子樹中的所有結(jié)點都稱為結(jié)點p的子孫。例如在圖（c）所示的樹中，D的子孫有H、I、J、M、N。10結(jié)

5、點的層次（level）：在樹中，從根結(jié)點開始，根為第一層，根的孩子為第二層，依次類推，樹中任一結(jié)點的層次是其雙親結(jié)點層次數(shù)加1。例如在圖（c）所示的樹中，結(jié)點K、L、M、N的層次數(shù)為4。11樹的深度（depth）：樹中結(jié)點的最大層次稱為樹的深度或樹的高度（height）。例如圖（c）所示的樹的深度為4。12堂兄弟：雙親在同一層的結(jié)點互稱為堂兄弟。如在圖（c）所示的樹中，結(jié)點F、G、H互稱為堂兄弟。13有序樹：如果樹中結(jié)點p的各棵子樹是有次序的則稱該樹為有序樹，此時結(jié)點p從左到右的k子樹分別稱為p的第1棵子樹、第2棵子樹、第k棵子樹。14無序樹：如果樹中結(jié)點的各棵子樹的次序是無關(guān)的則稱該樹為稱無

6、序樹。15森林(forest)：森林是m(m0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。 樹的表示形式：樹形表示法嵌套集合表示法凹入目錄表示法廣義表形式的表示法。 由于樹形表示法比較直觀，所以在本書中主要采用樹形表示法來表示樹形結(jié)構(gòu)。樹的基本操作：（1）Root ( )：求樹根結(jié)點的指針，若樹為空，則返回0。（2）CreateRoot ( d ):建立樹的根結(jié)點，使根結(jié)點的數(shù)據(jù)元素值為d。（3）Parent( x )：求樹中給定結(jié)點x的雙親結(jié)點的指針，若x為根結(jié)點，則返回空。（4）FirstChild ( x )：求樹中給定結(jié)點x的第一個孩子結(jié)點的的指針，若x為葉子結(jié)點

7、，則返回空。（5）NextSibling ( x, y )：給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的下一個兄弟結(jié)點的指針，若結(jié)點y是結(jié)點x的最后一個孩子，則返回空。（6）PreSibling ( x, y ) 給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的前一個兄弟結(jié)點的指針，若結(jié)點y是結(jié)點x的第一個孩子，則返回空。（7）Retrieve ( x )：求給定結(jié)點x中數(shù)據(jù)元素的值。（8）Assign (x，d)：對二叉樹中給定結(jié)點x賦值為d。（9）InsertChild ( x,d )：在結(jié)點x下插入數(shù)據(jù)元素值為d的新孩子結(jié)點，若插入成功，則返回1；

8、否則返回0。（10）DeleteChild ( x,i )：刪除以結(jié)點x的第i個孩子為根的子樹，若刪除成功，則返回1；否則返回0。（11）DeleteSubTree ( x )：刪除以結(jié)點x為根的子樹；（12）IsEmpty ( )：判斷樹是否為空樹。若樹為空樹，則返回1；否則返回0。（13）Travers（ ）：遍歷樹，按某種次序依次訪問樹中的每一個結(jié)點，并使每一個結(jié)點只被訪問一次。樹的抽象數(shù)據(jù)類型：ADT tree is Data 樹的根結(jié)點Operation Root 輸入：無 前置條件：無 動作：求樹根結(jié)點的指針，若樹為空，則返回空指針。 輸出：樹的結(jié)點的指針 后置條件：無Create

9、Root 輸入：數(shù)據(jù)元素d 前置條件：無 動作：建立樹的根結(jié)點，使根結(jié)點的數(shù)據(jù)元素值為d。 輸出：樹的結(jié)點指針 后置條件：無Parent 輸入：樹中的結(jié)點x 前置條件：無 動作：求樹中給定結(jié)點x的雙親結(jié)點的指針，若x為根結(jié)點，則返回空。 輸出：樹中結(jié)點的指針 后置條件：無FirstChild 輸入：樹中的結(jié)點x 前置條件：無 動作：求樹中給定結(jié)點x的第一個孩子結(jié)點的的指針，若x為葉子結(jié)點，則返回空。 輸出：樹中結(jié)點的指針 后置條件：無NextSibling 輸入：樹中的結(jié)點x、y 前置條件：無 動作：給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的下一個兄弟結(jié)點的指針，若結(jié)點

10、y是結(jié)點x的最后一個孩子，則返回空。 輸出：樹中結(jié)點的指針 后置條件：無PreSibling 輸入：樹中的結(jié)點x、y 前置條件：無 動作：給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的前一個兄弟結(jié)點的指針，若結(jié)點y是結(jié)點x的第一個孩子，則返回空。 輸出：樹中結(jié)點的指針 后置條件：無Retrieve 輸入：樹中的結(jié)點x 前置條件：結(jié)點x必須存在 動作：求給定結(jié)點x中數(shù)據(jù)元素的值 輸出：樹結(jié)點中數(shù)據(jù)元素 后置條件：無Assign 輸入：樹中的結(jié)點x和數(shù)據(jù)元素d 前置條件：結(jié)點必須存在 動作：對樹中給定結(jié)點x賦值為d 輸出：無 后置條件：無InsertChild 輸入：結(jié)點x和數(shù)

11、據(jù)元素d 前置條件：結(jié)點x必須存在 動作：在結(jié)點x下插入數(shù)據(jù)元素值為d的新孩子結(jié)點，若插入成功，則 返回1；否則返回0。 輸出：無 后置條件：無DeleteChild 輸入：結(jié)點x和序號i 前置條件：結(jié)點x必須存在且結(jié)點x孩子個數(shù)超過i 動作：刪除以結(jié)點x的第i個孩子為根的子樹，若刪除成功，則返回1；否則返回0。 輸出：1或0 后置條件：無DeleteSubTree 輸入：樹中結(jié)點x 前置條件：樹中結(jié)點x 動作：刪除以結(jié)點x為根的子樹 輸出：無 后置條件：無IsEmpty 輸入：無 前置條件：無 動作：判斷樹是否為空。若樹為空，則返回1；否則返回0。 輸出：1或0后置條件：無Travers 輸

12、入：無 前置條件：無 動作：遍歷樹，按某種次序依次訪問樹中的每一個結(jié)點，并使每一個結(jié)點只被訪問一次。 輸出：一般為數(shù)據(jù)元素序列 后置條件：無end ADT tree二叉樹 二叉樹的定義 : 二叉樹BT是有限個結(jié)點的集合。當集合非空時，其中有一個結(jié)點稱為二叉樹的根結(jié)點，用BT表示，余下的結(jié)點（如果有的話）最多被組成兩棵分別被稱為BT的左子樹（left subtree）和右子樹（right subtree）、互不相交的二叉樹。 二叉樹的五種形態(tài) :二叉樹的性質(zhì) :性質(zhì)1：有n(n0)個結(jié)點的二叉樹的分支數(shù)為n-1。證明：因為在二叉樹中，除根結(jié)點以外的其它每個結(jié)點有且僅有一個父結(jié)點。而子結(jié)點與父結(jié)點

13、間有且只有一條分支，因此對于有n(n0)個結(jié)點的二叉樹，其分支的數(shù)目為n-1。性質(zhì)2：若二叉樹的高度為h（h0），則該二叉樹最少有h個結(jié)點，最多有2h-1個結(jié)點。證明：因為在二叉樹中，每一層至少要有1個結(jié)點，因此對于高度為h的二叉樹，其結(jié)點數(shù)至少為h個。 在二叉樹中，第一層只有一個根結(jié)點；又因為每個結(jié)點最多有2個孩子結(jié)點，所以第i層的結(jié)點最多為2i-1個，所以高度為h（h0）的二叉樹結(jié)點總數(shù)最多為：20 + 21 + + 2h-1 = 2h - 1性質(zhì)3：含有n個結(jié)點的二叉樹的高度最大值為n，最小值為log2(n+1) 。證明：因為在二叉樹中，每層至少有一個結(jié)點，因此對于含有n個結(jié)點的二叉樹，

14、其高度不會超過n。 根據(jù)性質(zhì)2可以得知，高度為h的二叉樹最多有2h-1個結(jié)點，即n2h-1，因此hlog2(n+1)。 由于h是整數(shù)，所以hlog2(n+1)。滿二叉樹的定義：若高度為h的二叉樹具有最大數(shù)目（2h-1個）的結(jié)點，則稱其為滿二叉樹（full binary tree ）。完全二叉樹的定義：若高度為h的二叉樹，除第 h 層外，其它各層 (1 h-1) 的結(jié)點數(shù)都達到最大個數(shù)，并且第 h 層的結(jié)點是自左向右連續(xù)分布的。則稱它為完全二叉樹（complete binary tree ）。性質(zhì)4：具有 n 個結(jié)點的完全二叉樹的高度為log2(n+1) 。證明：設(shè)完全二叉樹的高度為h，則由性質(zhì)

15、2得：2h-1-1n2h -1 2h-1n+12h 不等式中的各項取對數(shù)得：h-1log2(n+1)h。因為h為整數(shù)，所以h=log2(n+1)。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號0、1、2、n-1。則有以下關(guān)系：（1）若i0，則 i 無雙親，若i0，則 i 的雙親為i/2-1；（2）若2*i+1n，則 i 的左孩子為2*i+1；（3）若2*i+2n，則 i 的右孩子為2*i+2；（4）若i為偶數(shù)，且i1，則 i 是其雙親的右孩子，且其有編號為i-1左兄弟；（5）若i為奇數(shù)，且in-1，則 i 是其雙親的左孩子，且其有編號為i+1右兄弟。證明：此性質(zhì)

16、可以用歸納法證明，在此先證明其中的(2)和(3)。 當i0時，由完全二叉樹的定義得知， 如果2*i+11n，說明二叉樹中存在兩個或兩個以上的結(jié)點，所以結(jié)點i的左孩子存在且編號為1； 反之，如果2*i+11n，說明二叉樹中只有一個結(jié)點i，結(jié)點i的左孩子結(jié)點不存在。 同理，如果2i+22n，說明結(jié)點i的右孩子存在且編號為2； 如果2*i+22n，說明二叉樹中不存在編號為2的結(jié)點，即結(jié)點i的右孩子不存在。 假設(shè)對于編號為j(0ji）的結(jié)點，(2)和(3)成立。 當ij+1時，根據(jù)完全二叉樹的定義，若其左孩子結(jié)點存在則其左孩子結(jié)點的編號等于編號為j的結(jié)點的右孩子的編號加1，即其左孩子結(jié)點的編號等于2*

17、j+2+12*i+1； 同樣，當ij+1時，根據(jù)完全二叉樹的定義，若其右孩子結(jié)點存在，則其右孩子結(jié)點的編號等于其左孩子結(jié)點的編號加1，即其右孩子結(jié)點的編號等于2i+1+1=2*i+2， 因此性質(zhì)5的(2)，(3)得證。 由上述(2)和(3)可很容易證明(1)，證明如下： 當i0時，顯然該結(jié)點為根結(jié)點，所以它沒有雙親結(jié)點。 當i0時，設(shè)編號為i的結(jié)點的雙親結(jié)點的編號為f。如果i是其雙親結(jié)點的左孩子結(jié)點，根據(jù)性質(zhì)5的(2)有i2*f+1（i為奇數(shù)），即f(i-1)/2； 如果結(jié)點i是其雙親結(jié)點的右孩子結(jié)點，根據(jù)性質(zhì)5的(3)有i2*f+2（i為偶數(shù)），即fi/2-1。 綜合這兩種情況可以得到，當i

18、0時，其雙親結(jié)點的編號等于i/2-1。因此性質(zhì)5的(1)得證。二叉樹的基本操作 :（1）IsEmpty ( )：判斷二叉樹是否為空。若二叉樹為空，則返回1；否則返回0。（2）Root ( )：求二叉樹根結(jié)點的指針，若二叉樹為空，則返回空指。（3）CreateRoot ( d ):建立二叉樹的根結(jié)點，使根結(jié)點的數(shù)據(jù)元素值為d。（4）Parent( p )：求二叉樹中給定結(jié)點p的雙親結(jié)點的指針，若p為根結(jié)點，則返回空。（5）LeftChild ( p )：求二叉樹中給定結(jié)點p的左孩子結(jié)點的指針；若結(jié)點p沒有左孩子，則返回空。（6）RightChild ( p )：求二叉樹中給定結(jié)點p的右孩子結(jié)點的

19、指針；若結(jié)點p沒有右孩子，則返回空。（7）LeftSibling ( p )：求二叉樹中給定結(jié)點p的左兄弟結(jié)點的指針；若結(jié)點p是其雙親的左孩子或結(jié)點p是其雙親的右孩子但其雙親沒有左孩子，則返回空。（8）RightSibling ( p )：求二叉樹中給定結(jié)點p的右兄弟結(jié)點的指針；若結(jié)點p是其雙親的右孩子或結(jié)點p是其雙親的左孩子但其雙親沒有右孩子，則返回空。（9）Retrieve ( p )：求給定結(jié)點p中的數(shù)據(jù)元素的值。（10）Assign (p，d)：對二叉樹中給定結(jié)點p賦值為d。（11）InsertLeftChild ( p,d )：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點作為結(jié)點p的左孩子，若

20、結(jié)點p原來有左子樹PL，則插入完成后PL作為新結(jié)點的左子樹。（12）InsertRightChild ( p,d )：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點作為結(jié)點p的右孩子，若結(jié)點p原來有右子樹PR，則插入完成后PR作為新結(jié)點的右子樹。（13）DeleteLeftChild ( p )：刪除結(jié)點p的左子樹。（14）DeleteRightChild ( p )：刪除結(jié)點p的右子樹。（15）PreOrderTravers（ ）：先序遍歷二叉樹。（16）InOrderTravers（ ）：中序遍歷二叉樹。（17）PostOrderTravers（ ）：后序遍歷二叉樹。（18）LevelOrderTra

21、vers（ ）：按層次順序遍歷二叉樹。二叉樹的存儲結(jié)構(gòu) 數(shù)組表示法 : 二叉樹的數(shù)組表示就是采用一組連續(xù)存儲空間存儲二叉樹結(jié)點中的數(shù)據(jù)元素，利用數(shù)組下標來反映數(shù)據(jù)元素之間的關(guān)系。 對具有n個結(jié)點的完全二叉樹按從上到下、自左向右的順序連續(xù)給結(jié)點編號0、1、2、n-1。 按此結(jié)點編號將二叉樹中各結(jié)點中的數(shù)據(jù)元素順序地存放于一個一維數(shù)組中， 首先將根結(jié)點中的數(shù)據(jù)元素儲存在數(shù)組的0號位置； 對于二叉樹中任一個結(jié)點，如果它的數(shù)據(jù)元素存儲在數(shù)組的第i個位置，就把它的左、右孩子結(jié)點中的數(shù)據(jù)元素分別存放在數(shù)組的第2*i+1個位置和第2*i+2個位置。 這樣就得到了二叉樹的一種數(shù)組表示法。 采用這種方法表示一般

22、的二叉樹時，空間利用效率低是一個主要的問題。當被表示的二叉樹結(jié)構(gòu)很不完整時，在數(shù)組中就會出現(xiàn)很多空位置，因此空間浪費就變得非常大。 用這種方法表示二叉樹時，還有一個問題需要注意的是：必須處理結(jié)點不存在的情況。如果一個結(jié)點不存在，就必須在數(shù)組中相應(yīng)位置設(shè)置一個特殊標志，指明在這個位置沒有結(jié)點。 鏈表表示法 : 在二叉樹的鏈表表示中，樹中的每一個元素用一個結(jié)點表示，結(jié)點一般包括三個域，其結(jié)構(gòu)如圖(a)所示。其中，Data域用于存放數(shù)據(jù)元素的信息；leftChild域用于存放指向其左孩子結(jié)點的指針；rightChild域用于存放指向其右孩子結(jié)點的指針。二叉樹的這種鏈表表示稱為二叉鏈表。 二叉樹的二叉

23、鏈表表示，對于大多數(shù)的應(yīng)用來說是適合的。 但是，在二叉鏈表中要想找出一個結(jié)點的雙親是比較困難的，必須通過二叉樹的遍歷才能實現(xiàn)。 如果在應(yīng)用中需要方便地找到任何一個結(jié)點的雙親，可以在結(jié)點中增加一個Parent域來指向該結(jié)點的雙親， 二叉樹的這種表示方法稱為三叉鏈表。 二叉樹的二叉鏈表類聲明 :二叉鏈表中結(jié)點的類定義如下：template class BinaryTree;template Class BinTreeNode friend class BinaryTree;private: BinTreeNode *leftChild, *rightChild; /結(jié)點的左、右孩子指針域 Type

24、 data; /結(jié)點的數(shù)據(jù)域public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) /構(gòu)造函數(shù)，構(gòu)造一個空結(jié)點 BinTreeNode ( Type d, BinTreeNode *lp = NULL, BinTreeNode *rp = NULL ) : data (d), leftChild (lp), rightChild (rp) /構(gòu)造函數(shù)，構(gòu)造一個數(shù)據(jù)域的值為d的結(jié)點 Type &GetData ( ) const return data; BinTreeNode *GetLeftChild ( ) const r

25、eturn leftChild; BinTreeNode *GetRightChild ( ) const return rightChild; void SetData ( const Type & d ) data = d; void SetLeftChild ( BinTreeNode *p ) leftChild = p; void SetRightChild ( BinTreeNode *p ) rightChild = p; ;二叉鏈表類定義如下：template class BinaryTree private: BinTreeNode *root; /二叉樹根結(jié)點指針 BinT

26、reeNode *Parent ( BinTreeNode *start, BinTreeNode *p ); void destroy(BinTreeNode *p);/刪除以p為根的二叉樹 void PreOrder( BinTreeNode *r ) ; /前序遍歷以r為根的二叉樹 void InOrderTravers( BinTreeNode *r ); /中序遍歷以r為根的二叉樹 void PostOrderTravers( BinTreeNode *r ); /后序遍歷以r為根的二叉樹public: BinaryTree ( ) : root (NULL) /構(gòu)造函數(shù) Binar

27、yTree ( Type d ) : root (d) /構(gòu)造函數(shù) virtual BinaryTree ( ) destroy ( root ); /析構(gòu)函數(shù) virtual int IsEmpty ( ) return root = NULL ? 1 : 0; /判斷二叉樹是否為空 BinTreeNode * Root ( ) return root ; CreateRoot ( Type data ) root= new BinTreeNode (d) ; virtual BinTreeNode *Parent ( BinTreeNode * p ) return Parent( roo

28、t , p ) ; /找p的雙親 virtual BinTreeNode *LeftChild ( BinTreeNode * p ) return p = NULL ? NULL : pGetLeftChild( ); virtual BinTreeNode *RightChild ( BinTreeNode * p ) return p = NULL ? NULL : pGetRightChild( ); BinTreeNode * LeftSibling (BinTreeNode * p ) ; BinTreeNode * RightSibling (BinTreeNode * p );

29、 Type Retrieve (BinTreeNode * p ) return pGetData( ) ; Assign (BinTreeNode *p, Type d ); pSetData(d) ; InsertLeftChild (BinTreeNode * p, Type d ); InsertRightChild (BinTreeNode * p, Type d ); DeleteLeftChild (BinTreeNode * p ); destroy ( pGetLeftChild( ); DeleteRightChild (BinTreeNode * p ); destroy

30、 ( pGetRightChild( ); PreOrder ( ) PreOrder ( root ); InOrderTravers ( ) InOrderTravers ( root ) ; PostOrderTravers ( )PostOrderTravers ( root ) ; LevelOrderTravers ( ); 部分成員函數(shù)的實現(xiàn) :template void BinaryTree: destroy ( BinTreeNode*p ) if ( p != NULL ) destroy ( pGetLeftChild( ); destroy ( pGetRightChi

31、ld( ); delete p; template BinTreeNode * BinaryTree :Parent ( BinTreeNode * r, BinTreeNode *p ) BinTreeNode *q; if ( r= NULL ) return NULL; if ( rGetLeftChild( ) = p | rGetRightChild( ) = p ) return r; if ( ( q = Parent ( rGetLeftChild( ), p ) ) != NULL ) return q; else return Parent ( rGetRightChild

32、( ), p);template BinTreeNode * BinaryTree :LeftSibling (BinTreeNode * p ) BinTreeNode *q; q=Parent ( root, p ); if ( q=NULL ) | ( p = qGetLeftChild( ) ) return NULL ; else return qGetLeftChild( ) ;template BinTreeNode * BinaryTree :RightSibling (BinTreeNode * p ) BinTreeNode *q; q=Parent ( root, p )

33、; if ( q=NULL ) | ( p = qGetRightChild( ) ) return NULL ; else return qGetRightChild( ) ;template BinTreeNode :InsertLeftChild (BinTreeNode * p, Type d ) BinTreeNode *q = new BinTreeNode (d); qSetLeftChild(pGetRightChild( ); pSetLefttChild( q );template BinTreeNode :InsertRightChild (BinTreeNode * p

34、, Type d ) BinTreeNode *q = new BinTreeNode (d); qSetRightChild(pGetRightChild( ); pSetRightChild( q );遍歷二叉樹 : 二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，并使每個結(jié)點被訪問一次且只被訪問一次。 在遍歷過程中，對結(jié)點的訪問具有普遍的含義，可以是輸出各結(jié)點的數(shù)據(jù)元素信息，也可以是對結(jié)點作其他處理。另外，通過一次完整的遍歷，可使二叉樹中結(jié)點信息由非線性排列變?yōu)槟撤N意義上的線性排列。也就是說，遍歷操作使非線性結(jié)構(gòu)線性化。 前序遍歷:前序遍歷(Preorder Traversal)的遞

35、歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）訪問根結(jié)點；（2）前序遍歷根結(jié)點的左子樹；（3）前序遍歷根結(jié)點的右子樹。 對上圖所示的二叉樹，進行前序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，得到二叉樹的前序序列為：A、B、D、E、G、H、C、F、I。 前序遍歷二叉樹的遞歸算法如下：template void BinaryTree:PreOrder ( BinTreeNode *r ) if ( r != NULL ) cout rGetData( ) endl; PreOrder ( rGetLeftChild( ) ); PreOrder ( rGetRightChild( ) )

36、; 中序遍歷:中序遍歷(Inorder Traversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點的左子樹；（2）訪問根結(jié)點；（3）中序遍歷根結(jié)點的右子樹。對上圖所示的二叉樹，進行中序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，可得到二叉樹的中序序列為：D、B、G、E、H、A、C、F、I。中序遍歷二叉樹的遞歸算法如下：template void BinaryTree:InOrder ( BinTreeNode *r ) if ( r != NULL ) InOrder ( rGetLeftChild( ) ); cout rGetData( ) endl; I

37、nOrder ( rGetRightChild( ) ); 后序遍歷:后序遍歷(Postorder Traversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）后序遍歷根結(jié)點的左子樹；（2）后序遍歷根結(jié)點的右子樹；（3）訪問根結(jié)點。對上圖所示的二叉樹，進行后序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，可得到二叉樹的后序序列為：D、G、H、E、B、I、F、C、A。后序遍歷二叉樹的遞歸算法如下：template void BinaryTree:PostOrder ( BinTreeNode *r ) if ( bt != NULL ) PostOrder ( rGetLeftC

38、hild( ) ); PostOrder ( rGetRightChild( ) ); cout rGetData( ) endl;層序遍歷:所謂層序遍歷(Levelorder Traversal)二叉樹，是指從二叉樹的第一層(根結(jié)點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。對于右圖所示的二叉樹，按層序遍歷方式進行遍歷所得到的結(jié)點序列為：A、B、C、D、E、F、G、H、I。在進行層序遍歷時，需要設(shè)置一個隊列結(jié)構(gòu)，并按下述步驟層序遍歷二叉樹：(1)初始化隊列，并將根結(jié)點入隊。(2)當隊列非空時，取出隊頭結(jié)點p，轉(zhuǎn)步驟3；如果隊列為空，則結(jié)束遍歷。(3)訪問結(jié)點p；如

39、果該結(jié)點有左孩子，則將其左孩子入隊列；如果該結(jié)點有右孩子，則將其右孩子入隊列。(4)重復(fù)步驟(2)、(3)，直到隊列為空。下面給出層序遍歷算法的C+描述，其中二叉樹的存儲結(jié)構(gòu)仍為二叉鏈表。在此還用到了前面定義的隊列Queue。template void BinaryTree:LevelOrder ( ) linkqueue q;BinTreeNode * p=root; if (p ) q.add(p); While (!q.IsEmpty( ) p = *q.delete (); cout p.GetData() endl; if (pGetLeftChild( ) ) q. add (pG

40、etLeftChild( ) ); if (pGetRightChild( ) ) q. add (pGetRightChild( ) ); 在遍歷二叉樹時，無論采用前面所講的哪一種方式進行遍歷，其基本操作都是訪問結(jié)點。所以，對具有n個結(jié)點的二叉樹，遍歷操作的時間復(fù)雜度均為O(n)。 在前序、中序和后序遍歷的過程中，遞歸時棧所需要的空間最多等于樹的深度h乘以每個棧元素所需空間，在最壞的情況下，二叉樹的深度等于結(jié)點數(shù)目，所以空間復(fù)雜度為O(n)。在層序遍歷時，所設(shè)置隊列的大小顯然小于二叉樹中結(jié)點的個數(shù)，所以空間復(fù)雜度也為O(n)。 利用二叉樹的遍歷可以實現(xiàn)許多關(guān)于二叉樹的運算，例如計算二叉樹的結(jié)

41、點數(shù)目、計算二叉樹的高度、二叉樹的復(fù)制等。 線索二叉樹 線索二叉樹的定義 : 一棵具有n個結(jié)點的二叉樹就會發(fā)現(xiàn)，當它采用二叉鏈表作存儲結(jié)構(gòu)時，二叉鏈表中的所有結(jié)點共有n+1個空指針域。 因此，可以設(shè)法利用這些空指針域來存放結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的指針信息。 在此，可以作這樣的規(guī)定： 當某結(jié)點的左指針域為空時，令其指向依某種方式遍歷時所得到的該結(jié)點的前驅(qū)結(jié)點，否則指向它的左孩子； 當某結(jié)點的右指針域為空時，令其指向依某種方式遍歷時所得到的該結(jié)點的后繼結(jié)點，否則指向它的右孩子。線索二叉樹示例在每個結(jié)點中增設(shè)兩個標志位leftTag和rightTag，令：當leftTag = 0 時,leftCh

42、ild為左孩子指針當leftTag = 1 時,leftChild為前驅(qū)線索當rightTag = 0 時,rightChild為右孩子指針當rightTag = 1 時,rightChild為后繼指針 為算法設(shè)計方便起見，通常在線索鏈表中添加一個與二叉樹中結(jié)點的類型相同的頭結(jié)點， 令頭結(jié)點的數(shù)據(jù)域為空； 其leftChild指向二叉樹的根結(jié)點，但當二叉樹為空時，leftChild指向頭結(jié)點本身； 其rightChild域指向以某種方式遍歷二叉樹時第一個訪問的結(jié)點，而當二叉樹為空時，rightChild域指向該結(jié)點本身。 并令原來指向二叉樹根結(jié)點的頭指針指向該頭結(jié)點。 以某種方式遍歷二叉樹時第

43、一個被訪問結(jié)點的左指針和最后一個被訪問結(jié)點的右指針如果是線索，也指向頭結(jié)點。 這樣一來，就相當于為二叉樹建立了帶頭結(jié)點的雙向循環(huán)鏈表。 帶頭結(jié)點的二叉鏈表線索二叉樹的類定義 :線索二叉樹的結(jié)點類template class ThreadBinTreeNode friend class ThreadBinTree; /線索二叉樹的類friend class ThreadPreorderTree; /前序線索二叉樹的類friend class ThreadInorderTree; /中序線索二叉樹的類friend class ThreadPostorderTree; /后序線索二叉樹的類Publi

44、c: ThreadBinTreeNode ( const Type d ) : /構(gòu)造函數(shù) data (d),leftChild (NULL),rightChild (NULL), leftTag(0), rightTag (0) Type &GetData ( ) const return data; ThreadBinTreeNode *GetLeftChild ( ) const return leftChild; ThreadBinTreeNode*GetRightChild ( ) const return rightChild; void SetData ( const Type

45、& d ) data = d; void SetLeftChild (ThreadBinTreeNode *p ) leftChild = p; void SetRightChild (ThreadBinTreeNode *p ) rightChild = p; private: int leftTag, rightTag; /左右標志位 ThreadBinTreeNode *leftChild, *rightChild; Type data; /結(jié)點數(shù)據(jù);線索二叉樹的類template class ThreadBinTreeBinTree friend class ThreadPreorde

46、rTree; /前序線索二叉樹的類friend class ThreadInorderTree; /中序線索二叉樹的類friend class ThreadPostorderTree; /后序線索二叉樹的類public: ThreadBinTree ( ) : root(NULL) private: ThreadBinTreeNode *root;3前序線索二叉樹的類template class ThreadPreorderTree private: ThreadBinTree & T ; /線索二叉樹 ThreadBinTreeNode *current; /當前結(jié)點指針 void preT

47、hread ( ThreadBinTreeNode *r, ThreadBinTreeNode *pre ) ; /前序線索化以r為根的二叉樹，pre為前序序歷中第一個結(jié)點的前驅(qū)public: ThreadPreorderTree (ThreadBinTree & Tree ) : T(Tree) current=T.root ThreadBinTreeNode * ThreadPreOrderFirst ( ); /當前結(jié)點指針指向前序遍歷的第一個結(jié)點 ThreadBinTreeNode * ThreadPreOrderLast ( ); /當前結(jié)點指針指向前序遍歷的最后一個結(jié)點 Threa

48、dBinTreeNode * ThreadPreOrderNext ( ); /當前結(jié)點指針指向其后繼結(jié)點 ThreadBinTreeNode * ThreadPreOrderPrior ( ); /當前結(jié)點指針指向其前驅(qū)結(jié)點 void Preorder ( ) ; /前序遍歷 void CreatePreThread ( ); /建立前序線索二叉樹;4中序線索二叉樹的類template class ThreadInorderTree private: ThreadBinTree & T ; /線索二叉樹 ThreadBinTreeNode *current; /當前結(jié)點指針 void inT

49、hread ( ThreadBinTreeNode *r, ThreadBinTreeNode *pre ) ; /中序線索化以r為根的二叉樹，pre為中序序歷中第一個結(jié)點的前驅(qū)public: ThreadInorderTree (ThreadBinTree & Tree ) : T(Tree) current=T.root ThreadBinTreeNode * ThreadInOrderFirst ( ); /當前結(jié)點指針指向中序遍歷的第一個結(jié)點 ThreadBinTreeNode * ThreadInOrderLast ( ); /當前結(jié)點指針指向中序遍歷的最后一個結(jié)點 ThreadBi

50、nTreeNode * ThreadInOrderNext ( ); /當前結(jié)點指針指向其后繼結(jié)點 ThreadBinTreeNode * ThreadInOrderPrior ( ); /當前結(jié)點指針指向其前驅(qū)結(jié)點 void Inorder ( ) ; /中序遍歷 void CreateInThread ( ); /建立中序線索二叉樹;5后序線索二叉樹的類template class ThreadPostorderTree private: ThreadBinTree & T ; /線索二叉樹 ThreadBinTreeNode *current; /當前結(jié)點指針 void postThre

51、ad ( ThreadBinTreeNode *r, ThreadBinTreeNode *pre ) ; /后序線索化以r為根的二叉樹，pre為后序序歷中第一個結(jié)點的前驅(qū)public: ThreadPostorderTree (ThreadBinTree & Tree ) : T(Tree) current=T.root ThreadBinTreeNode * ThreadPostOrderFirst ( ); /當前結(jié)點指針指向后序遍歷的第一個結(jié)點 ThreadBinTreeNode * ThreadPostOrderLast ( ); /當前結(jié)點指針指向后序遍歷的最后一個結(jié)點 Threa

52、dBinTreeNode * ThreadPostOrderNext ( ); /當前結(jié)點指針指向其后繼結(jié)點 ThreadBinTreeNode * ThreadPostOrderPrior ( ); /當前結(jié)點指針指向其前驅(qū)結(jié)點 void Postorder ( ) ; /后序遍歷 void CreatePostThread ( ); /建立后序線索二叉樹;中序線索二叉樹 : 下面以中序線索二義樹為例，討論線索二叉樹的建立、線索二叉樹的遍歷以及在線索二叉樹中查找前驅(qū)結(jié)點、查找后繼結(jié)點、插入結(jié)點和刪除結(jié)點等操作的實現(xiàn)算法。1建立中序線索二叉樹 建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上就是遍

53、歷一棵二叉樹。在遍歷的過程中檢查當前結(jié)點的左、右指針域是否為空。如果為空，將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索。另外，在對一棵二叉樹加線索時，必須首先申請一個頭結(jié)點，并使頭結(jié)點的leftchild指向二叉樹的根結(jié)點。對二叉樹線索化后，還須建立最后一個結(jié)點到頭結(jié)點的線索；并使頭結(jié)點的rightchild指向第一個結(jié)點。 template void ThreadBinTree :InThread ( ThreadBinTreeNode *r, ThreadBinTreeNode *pre ) /利用中序遍歷線索化以r為根的二叉樹，pre為中序序歷中第一個結(jié)點的前驅(qū) if ( r != NULL

54、) InThread ( rGetLeftChild( ), pre ); /中序線索化current的左子樹 if ( rGetLeftChild( ) = NULL ) rSetLeftChild( pre ); rleftTag = 1; /建立前驅(qū)線索 if ( preGetRightChild( ) = NULL ) preSetRightChild( r ); prerightTag = 1; /建立后繼線索 pre = r; InThread ( rGetRightChild( ), pre ); /中序線索化r的右子樹 template void ThreadBinTree:C

55、reateInThread ( ) /建立中序線索二叉樹 ThreadBinTreeNode *pre; root = new ThreadBinTreeNode; /建立頭結(jié)點 rootleftTag= 1; rootrightTag = 1; if ( this = NULL ) rootSetLeftChild( root ); rootSetRightChild( root ); /二叉樹為空樹 else current = = this; rootSetLeftChild( this ); rootleftThread = 0; pre = root; InThread ( curr

56、ent, pre ); /中序線索化 preSetRightChild( root ); /最后一個結(jié)點的后續(xù)線索指向頭結(jié)點 prerightTag = 1; rootSetRightChild( ThreadInOrderFirst ( ) ; /頭結(jié)點的rightChild指向中序序列的第一個結(jié)點 2中序線索化二叉樹中的部分成員函數(shù)的實現(xiàn)在中序線索樹中尋找中序序列中的最后一個結(jié)點的算法如下：template ThreadBinTreeNode*ThreadInorderTree:ThreadInOrderLast( ) if (T.rootleftTag = 0) current = T.

57、rootGetLeftChild( ); while ( currentrightTag = 0 ) current = currentGetRightChild( ); return current; else return NULL;中序線索樹中尋找當前結(jié)點CURRENT的中序后繼結(jié)點的算法如下：template ThreadBinTreeNode*ThreadInorderTree:ThreadInOrderNext()/在線索樹中尋找CURRENT的中序后繼 ThreadBinTreeNode *p = currentGetRightChild( ); if ( currentrigh

58、tTag = 0 ) /CURRENT有右孩子 while ( pleftTag = 0 ) p = pGetLeftChild( ); current = p; if ( current = T.root ) return NULL; else return current; 在中序線索樹中進行中序遍歷，可以通過從第一個結(jié)點開始依次找當前結(jié)點的后繼來完成。算法的描述如下： template void ThreadInorderTree :Inorder ( ) ThreadBinTreeNode * p; for( p = T.rootGetLeftChild( ); p != NULL;

59、p = ThreadInOrderNext ( ) ) cout p.GetData endl;3. 在中序線索二叉樹上插入結(jié)點 在中序線索二叉樹上插入結(jié)點有兩種方法：一種是將新結(jié)點插入到二叉樹中作為某結(jié)點的左孩子結(jié)點；另一種方法是將新結(jié)點插入到二叉樹中作為某結(jié)點的右孩子結(jié)點。在此討論后一種情況。 假設(shè)指針p指向線索二叉樹中的某一結(jié)點，指針x指向要插入的新結(jié)點，新結(jié)點x將插入到二叉樹中作為結(jié)點p的右孩子。此時，將有兩種情況第一種情況：結(jié)點p沒有右孩子，則插入過程很簡單，下圖 (a)、(b)給出了這種情況下插入前后二叉樹的兩種形態(tài)。這時結(jié)點P原來的后繼結(jié)點變?yōu)榻Y(jié)點x的后繼結(jié)點，結(jié)點p為結(jié)點x的前

60、驅(qū)結(jié)點，結(jié)點 x成為結(jié)點p的右孩子。第二種情況：若結(jié)點P有右子樹，結(jié)點x插入后，令結(jié)點p原來的右子樹成為結(jié)點x的右子樹，x為P的右孩子。此時，結(jié)點p成為結(jié)點x的前驅(qū)結(jié)點，根據(jù)中序線索二叉樹的定義，這時還需修改結(jié)點p原來右子樹中最左下結(jié)點的左指針，使它由原來指向結(jié)點p改為指向結(jié)點x。下圖 (c)、(d)給出了這種情況下插入前后二叉樹的兩種形態(tài)。插入結(jié)點的算法如下：template void ThreadBinTree: insertRight(ThreadBinTreeNode *p, ThreadBinTreeNode* x) ThreadBinTreeNode*q xSetRightChil