數(shù)據(jù)結(jié)構(gòu) 第6章 樹和森林

第六章樹和森林主要內(nèi)容樹的概念二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)遍歷二叉樹線索二叉樹二叉樹的應(yīng)用樹的概念某家族的血統(tǒng)關(guān)系如下：張宇有四個(gè)孩子分別是：張山、張川、張星和張?jiān)拢粡埳接卸€(gè)孩子張冰和張雪；張星有三個(gè)孩子張雨、張?jiān)坪蛷堬L(fēng)；張?jiān)朴袃蓚€(gè)孩子張亮和張麗。

樹的定義：樹（tree）T是一個(gè)包含n(n>=0)個(gè)數(shù)據(jù)元素的有限集合。并且有：（1）當(dāng)n=0時(shí)，T稱為空樹；（2）如果n>0，則樹有且僅有一個(gè)特定的被稱為根（root）的結(jié)點(diǎn)，樹的根結(jié)點(diǎn)只有后繼，沒有前驅(qū)；（3）當(dāng)n>1時(shí),除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的非空有限集T1、T2、...、Tm,其中每一個(gè)集合本身又是一棵非空樹,并且稱它們?yōu)楦Y(jié)點(diǎn)的子樹（subtree）。

如右圖（a）表示了一棵空樹，它沒有數(shù)據(jù)元素；如右圖（b）表示了只有一個(gè)數(shù)據(jù)元素的樹，樹中只有一個(gè)沒有子樹的根結(jié)點(diǎn)A；如右圖（c）是有14個(gè)數(shù)據(jù)元素結(jié)點(diǎn)的樹，其中A是樹根，其余結(jié)點(diǎn)分成三個(gè)互不相交的有限集：T1={B,E,F,K,L}、T2={C,G}、T3={D,H,I,J,M,N}，T1、T2、T3又都是樹，且它們是結(jié)點(diǎn)A的子樹。樹的術(shù)語：

1．結(jié)點(diǎn)（node）：在樹中每一個(gè)數(shù)據(jù)元素及指向其子樹根的分支稱為一個(gè)結(jié)點(diǎn)。

2．結(jié)點(diǎn)的度（degreeofnode）：一個(gè)結(jié)點(diǎn)的子樹數(shù)目稱之為該結(jié)點(diǎn)的度。例如在圖（c）所示的樹中,結(jié)點(diǎn)A的度為3，結(jié)點(diǎn)C的度數(shù)為1,結(jié)點(diǎn)E的度數(shù)為0。

3．終端結(jié)點(diǎn)(terminalnode)：在樹中，度為0的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉子(leaf)。如在圖6-2（c）所示的樹中，結(jié)點(diǎn)E，K，L，G，H，M，N，J都是樹的葉子。

4．非終端結(jié)點(diǎn)(nonterminalnode)：在樹中，度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)也稱內(nèi)部結(jié)點(diǎn)。如在圖6-2（c）所示的樹中，結(jié)點(diǎn)A、B、C、D、F、I都是樹的分支結(jié)點(diǎn)，且結(jié)點(diǎn)B、C、D、F、I是樹T的內(nèi)部結(jié)點(diǎn)。5．樹的度（degreeoftree）：樹的結(jié)點(diǎn)中，最大的度稱為該樹的度。如圖6-2（c）所示的樹，其度為3。6．孩子(child)和雙親(parent)：在樹中，結(jié)點(diǎn)p的子樹的根稱為結(jié)點(diǎn)p的孩子；反之,這個(gè)結(jié)點(diǎn)p稱為其孩子的雙親（父親）。如在圖6-2（c）所示的樹中，結(jié)點(diǎn)D為結(jié)點(diǎn)A的子樹的根，因此結(jié)點(diǎn)D是結(jié)點(diǎn)A的孩子，結(jié)點(diǎn)A是結(jié)點(diǎn)D的雙親結(jié)點(diǎn)（父結(jié)點(diǎn)）。7．兄弟(sibling)：在樹中，同一個(gè)雙親的孩子之間互稱為兄弟。例如，在圖6-2（c）所示的樹中，結(jié)點(diǎn)B、C、D互為兄弟。8．祖先(ancestor)：在樹中，從根結(jié)點(diǎn)到結(jié)點(diǎn)x所經(jīng)的分支上的所有結(jié)點(diǎn)稱為結(jié)點(diǎn)x的祖先。如在圖6-2（c）所示的樹中，結(jié)點(diǎn)M的祖先為：A、D、I。9．子孫（descendant）：在樹中，以某結(jié)點(diǎn)p為根的子樹中的所有結(jié)點(diǎn)都稱為結(jié)點(diǎn)p的子孫。例如在圖6-2（c）所示的樹中，D的子孫有H、I、J、M、N。10．結(jié)點(diǎn)的層次（level）：在樹中，從根結(jié)點(diǎn)開始，根為第一層，根的孩子為第二層，依次類推，樹中任一結(jié)點(diǎn)的層次是其雙親結(jié)點(diǎn)層次數(shù)加1。例如在圖6-2（c）所示的樹中，結(jié)點(diǎn)K、L、M、N的層次數(shù)為4。11．樹的深度（depth）：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或樹的高度（height）。例如圖6-2（c）所示的樹的深度為4。12．堂兄弟：雙親在同一層的結(jié)點(diǎn)互稱為堂兄弟。如在圖6-2（c）所示的樹中，結(jié)點(diǎn)F、G、H互稱為堂兄弟。13．有序樹：如果樹中結(jié)點(diǎn)p的各棵子樹是有次序的則稱該樹為有序樹，此時(shí)結(jié)點(diǎn)p從左到右的k子樹分別稱為p的第1棵子樹、第2棵子樹、…、第k棵子樹。14．無序樹：如果樹中結(jié)點(diǎn)的各棵子樹的次序是無關(guān)的則稱該樹為稱無序樹。15．森林(forest)：森林是m(m>0)棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。

樹的表示形式：樹形表示法嵌套集合表示法凹入目錄表示法廣義表形式的表示法。

由于樹形表示法比較直觀，所以在本書中主要采用樹形表示法來表示樹形結(jié)構(gòu)。樹的基本操作：（1）Root()：求樹根結(jié)點(diǎn)的指針，若樹為空，則返回0。（2）CreateRoot(d):建立樹的根結(jié)點(diǎn)，使根結(jié)點(diǎn)的數(shù)據(jù)元素值為d。（3）Parent(x)：求樹中給定結(jié)點(diǎn)x的雙親結(jié)點(diǎn)的指針，若x為根結(jié)點(diǎn)，則返回空。（4）FirstChild(x)：求樹中給定結(jié)點(diǎn)x的第一個(gè)孩子結(jié)點(diǎn)的的指針，若x為葉子結(jié)點(diǎn)，則返回空。（5）NextSibling(x,y)：給定結(jié)點(diǎn)x、y，其中結(jié)點(diǎn)y是結(jié)點(diǎn)x的一個(gè)孩子。該函數(shù)求樹中結(jié)點(diǎn)y的下一個(gè)兄弟結(jié)點(diǎn)的指針，若結(jié)點(diǎn)y是結(jié)點(diǎn)x的最后一個(gè)孩子，則返回空。（6）PreSibling(x,y)給定結(jié)點(diǎn)x、y，其中結(jié)點(diǎn)y是結(jié)點(diǎn)x的一個(gè)孩子。該函數(shù)求樹中結(jié)點(diǎn)y的前一個(gè)兄弟結(jié)點(diǎn)的指針，若結(jié)點(diǎn)y是結(jié)點(diǎn)x的第一個(gè)孩子，則返回空。（7）Retrieve(x)：求給定結(jié)點(diǎn)x中數(shù)據(jù)元素的值。（8）Assign(x，d)：對(duì)二叉樹中給定結(jié)點(diǎn)x賦值為d。（9）InsertChild(x,d)：在結(jié)點(diǎn)x下插入數(shù)據(jù)元素值為d的新孩子結(jié)點(diǎn)，若插入成功，則返回1；否則返回0。（10）DeleteChild(x,i)：刪除以結(jié)點(diǎn)x的第i個(gè)孩子為根的子樹，若刪除成功，則返回1；否則返回0。（11）DeleteSubTree(x)：刪除以結(jié)點(diǎn)x為根的子樹；（12）IsEmpty()：判斷樹是否為空樹。若樹為空樹，則返回1；否則返回0。（13）Travers（）：遍歷樹，按某種次序依次訪問樹中的每一個(gè)結(jié)點(diǎn)，并使每一個(gè)結(jié)點(diǎn)只被訪問一次。二叉樹

二叉樹的定義:

二叉樹BT是有限個(gè)結(jié)點(diǎn)的集合。當(dāng)集合非空時(shí)，其中有一個(gè)結(jié)點(diǎn)稱為二叉樹的根結(jié)點(diǎn)，用BT表示，余下的結(jié)點(diǎn)（如果有的話）最多被組成兩棵分別被稱為BT的左子樹（leftsubtree）和右子樹（rightsubtree）、互不相交的二叉樹。二叉樹的五種形態(tài):二叉樹的性質(zhì):性質(zhì)1：有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹的分支數(shù)為n-1。證明：因?yàn)樵诙鏄渲校Y(jié)點(diǎn)以外的其它每個(gè)結(jié)點(diǎn)有且僅有一個(gè)父結(jié)點(diǎn)。而子結(jié)點(diǎn)與父結(jié)點(diǎn)間有且只有一條分支，因此對(duì)于有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹，其分支的數(shù)目為n-1。性質(zhì)2：若二叉樹的高度為h（h≥0），則該二叉樹最少有h個(gè)結(jié)點(diǎn)，最多有2h-1個(gè)結(jié)點(diǎn)。證明：因?yàn)樵诙鏄渲校恳粚又辽僖?個(gè)結(jié)點(diǎn)，因此對(duì)于高度為h的二叉樹，其結(jié)點(diǎn)數(shù)至少為h個(gè)。在二叉樹中，第一層只有一個(gè)根結(jié)點(diǎn)；又因?yàn)槊總€(gè)結(jié)點(diǎn)最多有2個(gè)孩子結(jié)點(diǎn)，所以第i層的結(jié)點(diǎn)最多為2i-1個(gè)，所以高度為h（h≥0）的二叉樹結(jié)點(diǎn)總數(shù)最多為：20+21+…+2h-1=2h-1性質(zhì)3：含有n個(gè)結(jié)點(diǎn)的二叉樹的高度最大值為n，最小值為log2(n+1)

。證明：因?yàn)樵诙鏄渲?，每層至少有一個(gè)結(jié)點(diǎn)，因此對(duì)于含有n個(gè)結(jié)點(diǎn)的二叉樹，其高度不會(huì)超過n。根據(jù)性質(zhì)2可以得知，高度為h的二叉樹最多有2h-1個(gè)結(jié)點(diǎn)，即n≤2h-1，因此h≥log2(n+1)。由于h是整數(shù)，所以h≥log2(n+1)。滿二叉樹的定義：若高度為h的二叉樹具有最大數(shù)目（2h-1個(gè)）的結(jié)點(diǎn)，則稱其為滿二叉樹（fullbinarytree）。完全二叉樹的定義：若高度為h的二叉樹，除第h層外，其它各層(1h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，并且第h層的結(jié)點(diǎn)是自左向右連續(xù)分布的。則稱它為完全二叉樹（completebinarytree）。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2(n+1)

。證明：設(shè)完全二叉樹的高度為h，則由性質(zhì)2得：2h-1-1＜n≤2h-12h-1＜n+1≤2h

不等式中的各項(xiàng)取對(duì)數(shù)得：h-1＜log2(n+1)≤h。因?yàn)閔為整數(shù)，所以h=log2(n+1)。性質(zhì)5：如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0、1、2、…、n-1。則有以下關(guān)系：（1）若i＝0，則i無雙親，若i＞0，則i的雙親為i/2-1；（2）若2*i+1<n，則i的左孩子為2*i+1；（3）若2*i+2<n，則i的右孩子為2*i+2；（4）若i為偶數(shù)，且i≥1，則i是其雙親的右孩子，且其有編號(hào)為i-1左兄弟；（5）若i為奇數(shù)，且i＜n-1，則i是其雙親的左孩子，且其有編號(hào)為i+1右兄弟。證明：此性質(zhì)可以用歸納法證明，在此先證明其中的(2)和(3)。當(dāng)i＝0時(shí)，由完全二叉樹的定義得知，如果2*i+1＝1<n，說明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以結(jié)點(diǎn)i的左孩子存在且編號(hào)為1；反之，如果2*i+1＝1=n，說明二叉樹中只有一個(gè)結(jié)點(diǎn)i，結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)不存在。同理，如果2i+2＝2<n，說明結(jié)點(diǎn)i的右孩子存在且編號(hào)為2；如果2*i+2＝2=n，說明二叉樹中不存在編號(hào)為2的結(jié)點(diǎn)，即結(jié)點(diǎn)i的右孩子不存在。

假設(shè)對(duì)于編號(hào)為j(0＜j＜i）的結(jié)點(diǎn)，(2)和(3)成立。當(dāng)i＝j(luò)+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子結(jié)點(diǎn)存在則其左孩子結(jié)點(diǎn)的編號(hào)等于編號(hào)為j的結(jié)點(diǎn)的右孩子的編號(hào)加1，即其左孩子結(jié)點(diǎn)的編號(hào)等于2*j+2+1＝2*i+1；同樣，當(dāng)i＝j(luò)+1時(shí)，根據(jù)完全二叉樹的定義，若其右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的編號(hào)等于其左孩子結(jié)點(diǎn)的編號(hào)加1，即其右孩子結(jié)點(diǎn)的編號(hào)等于2i+1+1=2*i+2，因此性質(zhì)5的(2)，(3)得證。

由上述(2)和(3)可很容易證明(1)，證明如下：當(dāng)i＝0時(shí)，顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，所以它沒有雙親結(jié)點(diǎn)。當(dāng)i＞0時(shí)，設(shè)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為f。如果i是其雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，根據(jù)性質(zhì)5的(2)有i＝2*f+1（i為奇數(shù)），即f＝(i-1)/2；如果結(jié)點(diǎn)i是其雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，根據(jù)性質(zhì)5的(3)有i＝2*f+2（i為偶數(shù)），即f＝i/2-1。綜合這兩種情況可以得到，當(dāng)i＞0時(shí)，其雙親結(jié)點(diǎn)的編號(hào)等于i/2-1。因此性質(zhì)5的(1)得證。二叉樹的基本操作:（1）IsEmpty()：判斷二叉樹是否為空。若二叉樹為空，則返回1；否則返回0。（2）Root()：求二叉樹根結(jié)點(diǎn)的指針，若二叉樹為空，則返回空指。（3）CreateRoot(d):建立二叉樹的根結(jié)點(diǎn)，使根結(jié)點(diǎn)的數(shù)據(jù)元素值為d。（4）Parent(p)：求二叉樹中給定結(jié)點(diǎn)p的雙親結(jié)點(diǎn)的指針，若p為根結(jié)點(diǎn)，則返回空。（5）LeftChild(p)：求二叉樹中給定結(jié)點(diǎn)p的左孩子結(jié)點(diǎn)的指針；若結(jié)點(diǎn)p沒有左孩子，則返回空。（6）RightChild(p)：求二叉樹中給定結(jié)點(diǎn)p的右孩子結(jié)點(diǎn)的指針；若結(jié)點(diǎn)p沒有右孩子，則返回空。（7）LeftSibling(p)：求二叉樹中給定結(jié)點(diǎn)p的左兄弟結(jié)點(diǎn)的指針；若結(jié)點(diǎn)p是其雙親的左孩子或結(jié)點(diǎn)p是其雙親的右孩子但其雙親沒有左孩子，則返回空。（8）RightSibling(p)：求二叉樹中給定結(jié)點(diǎn)p的右兄弟結(jié)點(diǎn)的指針；若結(jié)點(diǎn)p是其雙親的右孩子或結(jié)點(diǎn)p是其雙親的左孩子但其雙親沒有右孩子，則返回空。（9）Retrieve(p)：求給定結(jié)點(diǎn)p中的數(shù)據(jù)元素的值。（10）Assign(p，d)：對(duì)二叉樹中給定結(jié)點(diǎn)p賦值為d。（11）InsertLeftChild(p,d)：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點(diǎn)作為結(jié)點(diǎn)p的左孩子，若結(jié)點(diǎn)p原來有左子樹PL，則插入完成后PL作為新結(jié)點(diǎn)的左子樹。（12）InsertRightChild(p,d)：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點(diǎn)作為結(jié)點(diǎn)p的右孩子，若結(jié)點(diǎn)p原來有右子樹PR，則插入完成后PR作為新結(jié)點(diǎn)的右子樹。（13）DeleteLeftChild(p)：刪除結(jié)點(diǎn)p的左子樹。（14）DeleteRightChild(p)：刪除結(jié)點(diǎn)p的右子樹。（15）PreOrderTravers（）：先序遍歷二叉樹。（16）InOrderTravers（）：中序遍歷二叉樹。（17）PostOrderTravers（）：后序遍歷二叉樹。（18）LevelOrderTravers（）：按層次順序遍歷二叉樹。二叉樹的存儲(chǔ)結(jié)構(gòu)

數(shù)組表示法:

二叉樹的數(shù)組表示就是采用一組連續(xù)存儲(chǔ)空間存儲(chǔ)二叉樹結(jié)點(diǎn)中的數(shù)據(jù)元素，利用數(shù)組下標(biāo)來反映數(shù)據(jù)元素之間的關(guān)系。對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按從上到下、自左向右的順序連續(xù)給結(jié)點(diǎn)編號(hào)0、1、2、…、n-1。按此結(jié)點(diǎn)編號(hào)將二叉樹中各結(jié)點(diǎn)中的數(shù)據(jù)元素順序地存放于一個(gè)一維數(shù)組中，首先將根結(jié)點(diǎn)中的數(shù)據(jù)元素儲(chǔ)存在數(shù)組的0號(hào)位置；對(duì)于二叉樹中任一個(gè)結(jié)點(diǎn)，如果它的數(shù)據(jù)元素存儲(chǔ)在數(shù)組的第i個(gè)位置，就把它的左、右孩子結(jié)點(diǎn)中的數(shù)據(jù)元素分別存放在數(shù)組的第2*i+1個(gè)位置和第2*i+2個(gè)位置。這樣就得到了二叉樹的一種數(shù)組表示法。

采用這種方法表示一般的二叉樹時(shí)，空間利用效率低是一個(gè)主要的問題。當(dāng)被表示的二叉樹結(jié)構(gòu)很不完整時(shí)，在數(shù)組中就會(huì)出現(xiàn)很多空位置，因此空間浪費(fèi)就變得非常大。

用這種方法表示二叉樹時(shí)，還有一個(gè)問題需要注意的是：必須處理結(jié)點(diǎn)不存在的情況。如果一個(gè)結(jié)點(diǎn)不存在，就必須在數(shù)組中相應(yīng)位置設(shè)置一個(gè)特殊標(biāo)志，指明在這個(gè)位置沒有結(jié)點(diǎn)。鏈表表示法:

在二叉樹的鏈表表示中，樹中的每一個(gè)元素用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)一般包括三個(gè)域，其結(jié)構(gòu)如圖(a)所示。其中，Data域用于存放數(shù)據(jù)元素的信息；leftChild域用于存放指向其左孩子結(jié)點(diǎn)的指針；rightChild域用于存放指向其右孩子結(jié)點(diǎn)的指針。二叉樹的這種鏈表表示稱為二叉鏈表。

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

Typedata;//結(jié)點(diǎn)的數(shù)據(jù)域public:BinTreeNode():leftChild(NULL),rightChild(NULL){}//構(gòu)造函數(shù)，構(gòu)造一個(gè)空結(jié)點(diǎn)

BinTreeNode(Typed,BinTreeNode<Type>*lp=NULL,BinTreeNode<Type>*rp=NULL):data(d),leftChild(lp),rightChild(rp){}//構(gòu)造函數(shù)，構(gòu)造一個(gè)數(shù)據(jù)域的值為d的結(jié)點(diǎn)

Type&GetData()const{returndata;}BinTreeNode<Type>*GetLeftChild()const{returnleftChild;}BinTreeNode<Type>*GetRightChild()const{returnrightChild;}voidSetData(constType&d){data=d;}voidSetLeftChild(BinTreeNode<Type>*p){leftChild=p;}voidSetRightChild(BinTreeNode<Type>*p){rightChild=p;}};二叉鏈表類定義如下：template<classType>classBinaryTree{private:BinTreeNode<Type>*root;//二叉樹根結(jié)點(diǎn)指針

BinTreeNode<Type>*Parent(BinTreeNode<Type>*start,BinTreeNode<Type>*p);

voiddestroy(BinTreeNode<Type>*p);//刪除以p為根的二叉樹

voidPreOrder(BinTreeNode<Type>*r);//前序遍歷以r為根的二叉樹

voidInOrderTravers(BinTreeNode<Type>*r);//中序遍歷以r為根的二叉樹

voidPostOrderTravers(BinTreeNode<Type>*r);//后序遍歷以r為根的二叉樹public:BinaryTree():root(NULL){}//構(gòu)造函數(shù)

BinaryTree(Typed):root(d){}//構(gòu)造函數(shù)

virtual~BinaryTree(){destroy(root);}//析構(gòu)函數(shù)

virtualintIsEmpty(){returnroot==NULL?1:0;}//判斷二叉樹是否為空

BinTreeNode<Type>*Root(){returnroot;}CreateRoot(Typedata){root=newBinTreeNode<Type>(d);}virtualBinTreeNode<Type>*Parent(BinTreeNode<Type>*p){returnParent(root,p);}//找p的雙親virtualBinTreeNode<Type>*LeftChild(BinTreeNode<Type>*p){returnp==NULL?NULL:p→GetLeftChild();}virtualBinTreeNode<Type>*RightChild(BinTreeNode<Type>*p){returnp==NULL?NULL:p→GetRightChild();}BinTreeNode<Type>*LeftSibling(BinTreeNode<Type>*p);BinTreeNode<Type>*RightSibling(BinTreeNode<Type>*p);TypeRetrieve(BinTreeNode<Type>*p){returnp→GetData();}Assign(BinTreeNode<Type>*p,Typed);{p→SetData(d);}InsertLeftChild(BinTreeNode<Type>*p,Typed);InsertRightChild(BinTreeNode<Type>*p,Typed);DeleteLeftChild(BinTreeNode<Type>*p);{destroy(p→GetLeftChild());}DeleteRightChild(BinTreeNode<Type>*p);{destroy(p→GetRightChild());}PreOrder(){PreOrder(root);}InOrderTravers(){InOrderTravers(root)};PostOrderTravers(){PostOrderTravers(root)};LevelOrderTravers();}部分成員函數(shù)的實(shí)現(xiàn):template<classType>voidBinaryTree<Type>::destroy(BinTreeNode<Type>*p){

if(p!=NULL){destroy(p→GetLeftChild());destroy(p→GetRightChild());deletep;}}template<classType>BinTreeNode<Type>*BinaryTree<Type>::Parent(BinTreeNode<Type>*r,BinTreeNode<Type>*p){BinTreeNode<Type>*q;

if(r==NULL)return

NULL;

if(r→GetLeftChild()==p||r→GetRightChild()==p)returnr;

if((q=Parent(r→GetLeftChild(),p))!=NULL)returnq;

else

returnParent(r→GetRightChild(),p);}template<classType>BinTreeNode<Type>*BinaryTree<Type>::LeftSibling(BinTreeNode<Type>*p){BinTreeNode<Type>*q;q=Parent(root,p);

if((q==NULL)||(p==q→GetLeftChild()))

return

NULL;

else

returnq→GetLeftChild();}template<classType>BinTreeNode<Type>*BinaryTree<Type>::RightSibling(BinTreeNode<Type>*p){BinTreeNode<Type>*q;q=Parent(root,p);

if((q==NULL)||(p==q→GetRightChild()))

return

NULL;

else

returnq→GetRightChild();}template<classType>BinTreeNode<Type>::InsertLeftChild(BinTreeNode<Type>*p,Typed){BinTreeNode<Type>*q=newBinTreeNode<Type>(d);q→SetLeftChild(p→GetRightChild());p→SetLefttChild(q);}template<classType>BinTreeNode<Type>::InsertRightChild(BinTreeNode<Type>*p,Typed){BinTreeNode<Type>*q=newBinTreeNode<Type>(d);q→SetRightChild(p→GetRightChild());p→SetRightChild(q);}遍歷二叉樹:

二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)被訪問一次且只被訪問一次。在遍歷過程中，對(duì)結(jié)點(diǎn)的訪問具有普遍的含義，可以是輸出各結(jié)點(diǎn)的數(shù)據(jù)元素信息，也可以是對(duì)結(jié)點(diǎn)作其他處理。另外，通過一次完整的遍歷，可使二叉樹中結(jié)點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性排列。也就是說，遍歷操作使非線性結(jié)構(gòu)線性化。前序遍歷:前序遍歷(PreorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）訪問根結(jié)點(diǎn)；（2）前序遍歷根結(jié)點(diǎn)的左子樹；（3）前序遍歷根結(jié)點(diǎn)的右子樹。

對(duì)上圖所示的二叉樹，進(jìn)行前序遍歷，按訪問結(jié)點(diǎn)的先后順序?qū)⒔Y(jié)點(diǎn)的數(shù)據(jù)元素排列起來，得到二叉樹的前序序列為：A、B、D、E、G、H、C、F、I。前序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*r){

if(r!=NULL){

cout<<r→GetData()<<endl;PreOrder(r→GetLeftChild());PreOrder(r→GetRightChild());}}中序遍歷:中序遍歷(InorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。對(duì)上圖所示的二叉樹，進(jìn)行中序遍歷，按訪問結(jié)點(diǎn)的先后順序?qū)⒔Y(jié)點(diǎn)的數(shù)據(jù)元素排列起來，可得到二叉樹的中序序列為：D、B、G、E、H、A、C、F、I。中序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::InOrder(BinTreeNode<Type>*r){

if(r!=NULL){InOrder(r→GetLeftChild());

cout<<r→GetData()<<endl;InOrder(r→GetRightChild());}}后序遍歷:后序遍歷(PostorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹；（3）訪問根結(jié)點(diǎn)。對(duì)上圖所示的二叉樹，進(jìn)行后序遍歷，按訪問結(jié)點(diǎn)的先后順序?qū)⒔Y(jié)點(diǎn)的數(shù)據(jù)元素排列起來，可得到二叉樹的后序序列為：D、G、H、E、B、I、F、C、A。后序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::PostOrder(BinTreeNode<Type>*r){

if(bt!=NULL){PostOrder(r→GetLeftChild());PostOrder(r→GetRightChild());}

cout<<r→GetData()<<endl;}層序遍歷:所謂層序遍歷(LevelorderTraversal)二叉樹，是指從二叉樹的第一層(根結(jié)點(diǎn))開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。對(duì)于右圖所示的二叉樹，按層序遍歷方式進(jìn)行遍歷所得到的結(jié)點(diǎn)序列為：A、B、C、D、E、F、G、H、I。在進(jìn)行層序遍歷時(shí)，需要設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，并按下述步驟層序遍歷二叉樹：(1)初始化隊(duì)列，并將根結(jié)點(diǎn)入隊(duì)。(2)當(dāng)隊(duì)列非空時(shí)，取出隊(duì)頭結(jié)點(diǎn)p，轉(zhuǎn)步驟3；如果隊(duì)列為空，則結(jié)束遍歷。(3)訪問結(jié)點(diǎn)p；如果該結(jié)點(diǎn)有左孩子，則將其左孩子入隊(duì)列；如果該結(jié)點(diǎn)有右孩子，則將其右孩子入隊(duì)列。(4)重復(fù)步驟(2)、(3)，直到隊(duì)列為空。下面給出層序遍歷算法的C++描述，其中二叉樹的存儲(chǔ)結(jié)構(gòu)仍為二叉鏈表。在此還用到了前面定義的隊(duì)列Queue。template<classType>voidBinaryTree<Type>::LevelOrder(){linkqueue<BinTreeNode*>q;BinTreeNode*p=root;

if(p)q.EnQueue(p);

While(!q.IsEmpty()){p=*q.DeQueue();

cout<<p.GetData()<<endl;

if(p→GetLeftChild())q.EnQueue(p→GetLeftChild());

if(p→GetRightChild())q.EnQueue(p→GetRightChild());}}

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

線索二叉樹的定義:

一棵具有n個(gè)結(jié)點(diǎn)的二叉樹就會(huì)發(fā)現(xiàn)，當(dāng)它采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，二叉鏈表中的所有結(jié)點(diǎn)共有n+1個(gè)空指針域。因此，可以設(shè)法利用這些空指針域來存放結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針信息。在此，可以作這樣的規(guī)定：當(dāng)某結(jié)點(diǎn)的左指針域?yàn)榭諘r(shí)，令其指向依某種方式遍歷時(shí)所得到的該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，否則指向它的左孩子；當(dāng)某結(jié)點(diǎn)的右指針域?yàn)榭諘r(shí)，令其指向依某種方式遍歷時(shí)所得到的該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，否則指向它的右孩子。在每個(gè)結(jié)點(diǎn)中增設(shè)兩個(gè)標(biāo)志位leftTag和rightTag，令：當(dāng)leftTag=0時(shí),

leftChild為左孩子指針當(dāng)leftTag=1時(shí), leftChild為前驅(qū)線索當(dāng)rightTag=0時(shí), rightChild為右孩子指針當(dāng)rightTag=1時(shí), rightChild為后繼指針

為算法設(shè)計(jì)方便起見，通常在線索鏈表中添加一個(gè)與二叉樹中結(jié)點(diǎn)的類型相同的頭結(jié)點(diǎn)，令頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?；其leftChild指向二叉樹的根結(jié)點(diǎn)，但當(dāng)二叉樹為空時(shí)，leftChild指向頭結(jié)點(diǎn)本身；其rightChild域指向以某種方式遍歷二叉樹時(shí)第一個(gè)訪問的結(jié)點(diǎn)，而當(dāng)二叉樹為空時(shí)，rightChild域指向該結(jié)點(diǎn)本身。并令原來指向二叉樹根結(jié)點(diǎn)的頭指針指向該頭結(jié)點(diǎn)。以某種方式遍歷二叉樹時(shí)第一個(gè)被訪問結(jié)點(diǎn)的左指針和最后一個(gè)被訪問結(jié)點(diǎn)的右指針如果是線索，也指向頭結(jié)點(diǎn)。這樣一來，就相當(dāng)于為二叉樹建立了帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表。線索二叉樹的類定義:線索二叉樹的結(jié)點(diǎn)類template<classType>classThreadBinTreeNode{friend

classThreadBinTree;//線索二叉樹的類friend

classThreadPreorderTree;//前序線索二叉樹的類friend

classThreadInorderTree;//中序線索二叉樹的類friend

classThreadPostorderTree;//后序線索二叉樹的類Public:ThreadBinTreeNode(constTyped)://構(gòu)造函數(shù)

data(d),leftChild(NULL),rightChild(NULL),leftTag(0),rightTag(0){}Type&GetData()const{returndata;}ThreadBinTreeNode<Type>*GetLeftChild()const{returnleftChild;}ThreadBinTreeNode<Type>*GetRightChild()const{returnrightChild;}

voidSetData(constType&d){data=d;}

voidSetLeftChild(ThreadBinTreeNode<Type>*p){leftChild=p;}

voidSetRightChild(ThreadBinTreeNode<Type>*p){rightChild=p;}private:

intleftTag,rightTag;//左右標(biāo)志位

ThreadBinTreeNode<Type>*leftChild,*rightChild;//線索或孩子指針

Typedata;//結(jié)點(diǎn)數(shù)據(jù)};線索二叉樹的類template<classType>classThreadBinTreeBinTree{friend

classThreadPreorderTree;//前序線索二叉樹的類friend

classThreadInorderTree;//中序線索二叉樹的類friend

classThreadPostorderTree;//后序線索二叉樹的類public:ThreadBinTree():root(NULL){}private:ThreadBinTreeNode<Type>*root;};3．前序線索二叉樹的類template<classType>classThreadPreorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點(diǎn)指針

voidpreThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//前序線索化以r為根的二叉樹，pre為前序序歷中第一個(gè)結(jié)點(diǎn)的前驅(qū)public:ThreadPreorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadPreOrderFirst();//當(dāng)前結(jié)點(diǎn)指針指向前序遍歷的第一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPreOrderLast();//當(dāng)前結(jié)點(diǎn)指針指向前序遍歷的最后一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPreOrderNext();//當(dāng)前結(jié)點(diǎn)指針指向其后繼結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPreOrderPrior();//當(dāng)前結(jié)點(diǎn)指針指向其前驅(qū)結(jié)點(diǎn)

voidPreorder();//前序遍歷

voidCreatePreThread();//建立前序線索二叉樹};4．中序線索二叉樹的類template<classType>classThreadInorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點(diǎn)指針

voidinThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//中序線索化以r為根的二叉樹，pre為中序序歷中第一個(gè)結(jié)點(diǎn)的前驅(qū)public:ThreadInorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadInOrderFirst();//當(dāng)前結(jié)點(diǎn)指針指向中序遍歷的第一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadInOrderLast();//當(dāng)前結(jié)點(diǎn)指針指向中序遍歷的最后一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadInOrderNext();//當(dāng)前結(jié)點(diǎn)指針指向其后繼結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadInOrderPrior();//當(dāng)前結(jié)點(diǎn)指針指向其前驅(qū)結(jié)點(diǎn)

voidInorder();//中序遍歷

voidCreateInThread();//建立中序線索二叉樹};5．后序線索二叉樹的類template<classType>classThreadPostorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點(diǎn)指針

voidpostThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//后序線索化以r為根的二叉樹，pre為后序序歷中第一個(gè)結(jié)點(diǎn)的前驅(qū)public:ThreadPostorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadPostOrderFirst();//當(dāng)前結(jié)點(diǎn)指針指向后序遍歷的第一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPostOrderLast();//當(dāng)前結(jié)點(diǎn)指針指向后序遍歷的最后一個(gè)結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPostOrderNext();//當(dāng)前結(jié)點(diǎn)指針指向其后繼結(jié)點(diǎn)

ThreadBinTreeNode<Type>*ThreadPostOrderPrior();//當(dāng)前結(jié)點(diǎn)指針指向其前驅(qū)結(jié)點(diǎn)

voidPostorder();//后序遍歷

voidCreatePostThread();//建立后序線索二叉樹};中序線索二叉樹:

下面以中序線索二義樹為例，討論線索二叉樹的建立、線索二叉樹的遍歷以及在線索二叉樹中查找前驅(qū)結(jié)點(diǎn)、查找后繼結(jié)點(diǎn)、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)等操作的實(shí)現(xiàn)算法。1．建立中序線索二叉樹

建立線索二叉樹，或者說對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷的過程中檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空。如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。另外，在對(duì)一棵二叉樹加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，并使頭結(jié)點(diǎn)的leftchild指向二叉樹的根結(jié)點(diǎn)。對(duì)二叉樹線索化后，還須建立最后一個(gè)結(jié)點(diǎn)到頭結(jié)點(diǎn)的線索；并使頭結(jié)點(diǎn)的rightchild指向第一個(gè)結(jié)點(diǎn)。

template<classType>voidThreadBinTree<Type>::InThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre){//利用中序遍歷線索化以r為根的二叉樹，pre為中序序歷中第一個(gè)結(jié)點(diǎn)的前驅(qū)

if(r!=NULL){InThread(r→GetLeftChild(),pre);//中序線索化r的左子樹

if(r→GetLeftChild()==NULL){r→SetLeftChild(pre);r→leftTag=1;}//建立前驅(qū)線索

if(pre→GetRightChild()==NULL){pre→SetRightChild(r);pre→rightTag=1;}//建立后繼線索

pre=r;InThread(r→GetRightChild(),pre);//中序線索化r的右子樹

}}template<classType>voidThreadBinTree<Type>::CreateInThread(){//建立中序線索二叉樹

ThreadBinTreeNode<Type>*pre;root=newThreadBinTreeNode<Type>;//建立頭結(jié)點(diǎn)

root→leftTag=1;root→rightTag=1;

if(this==NULL){root→SetLeftChild(root);root→SetRightChild(root);}//二叉樹為空樹

else{current==this;root→SetLeftChild(this);root→leftThread=0;pre=root;InThread(current,pre);//中序線索化

pre→SetRightChild(root);//最后一個(gè)結(jié)點(diǎn)的后續(xù)線索指向頭結(jié)點(diǎn)

pre→rightTag=1;root→SetRightChild(ThreadInOrderFirst());//頭結(jié)點(diǎn)的rightChild指向中序序列的第一個(gè)結(jié)點(diǎn)

}}2．中序線索化二叉樹中的部分成員函數(shù)的實(shí)現(xiàn)在中序線索樹中尋找中序序列中的最后一個(gè)結(jié)點(diǎn)的算法如下：template<classType>ThreadBinTreeNode<Type>*ThreadInorderTree<Type>::ThreadInOrderLast(){if(T.root→leftTag==0){current=T.root→GetLeftChild();while(current→rightTag==0)current=current→GetRightChild();returncurrent;}elsereturnNULL;}中序線索樹中尋找當(dāng)前結(jié)點(diǎn)CURRENT的中序后繼結(jié)點(diǎn)的算法如下：template<classType>ThreadBinTreeNode<Type>*ThreadInorderTree<Type>::ThreadInOrderNext(){//在線索樹中尋找CURRENT的中序后繼

ThreadBinTreeNode<Type>*p=current→GetRightChild();

if(current→rightTag==0)//CURRENT有右孩子

while(p→leftTag==0)p=p→GetLeftChild();current=p;

if(current==T.root)return

NULL;

else

returncurrent;}

在中序線索樹中進(jìn)行中序遍歷，可以通過從第一個(gè)結(jié)點(diǎn)開始依次找當(dāng)前結(jié)點(diǎn)的后繼來完成。算法的描述如下：template<classType>void

ThreadInorderTree<Type>::Inorder(){ThreadBinTreeNode<Type>*p;

for(p=T.root→GetLeftChild();p!=NULL;p=ThreadInOrderNext())

cout<<p.GetData<<endl;}3.在中序線索二叉樹上插入結(jié)點(diǎn)在中序線索二叉樹上插入結(jié)點(diǎn)有兩種方法：一種是將新結(jié)點(diǎn)插入到二叉樹中作為某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；另一種方法是將新結(jié)點(diǎn)插入到二叉樹中作為某結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。在此討論后一種情況。假設(shè)指針p指向線索二叉樹中的某一結(jié)點(diǎn)，指針x指向要插入的新結(jié)點(diǎn)，新結(jié)點(diǎn)x將插入到二叉樹中作為結(jié)點(diǎn)p的右孩子。此時(shí)，將有兩種情況第一種情況：結(jié)點(diǎn)p沒有右孩子，則插入過程很簡(jiǎn)單，下圖(a)、(b)給出了這種情況下插入前后二叉樹的兩種形態(tài)。這時(shí)結(jié)點(diǎn)P原來的后繼結(jié)點(diǎn)變?yōu)榻Y(jié)點(diǎn)x的后繼結(jié)點(diǎn)，結(jié)點(diǎn)p為結(jié)點(diǎn)x的前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)x成為結(jié)點(diǎn)p的右孩子。第二種情況：若結(jié)點(diǎn)P有右子樹，結(jié)點(diǎn)x插入后，令結(jié)點(diǎn)p原來的右子樹成為結(jié)點(diǎn)x的右子樹，x為P的右孩子。此時(shí)，結(jié)點(diǎn)p成為結(jié)點(diǎn)x的前驅(qū)結(jié)點(diǎn)，根據(jù)中序線索二叉樹的定義，這時(shí)還需修改結(jié)點(diǎn)p原來右子樹中最左下結(jié)點(diǎn)的左指針，使它由原來指向結(jié)點(diǎn)p改為指向結(jié)點(diǎn)x。下圖(c)、(d)給出了這種情況下插入前后二叉樹的兩種形態(tài)。插入結(jié)點(diǎn)的算法如下：template<classtype>voidThreadBinTree<type>::insertRight(ThreadBinTreeNode<type>*p,ThreadBinTreeNode<type>*x){ThreadBinTreeNode<type>*qx→SetRightChild(p.GetRightChild());x→rightTag=p→rightTag;x→SetLeftChild(p);x→leftTag=1;p→SetRightChild(x);p→rightTag=0;

if(x→rightTag==0){q=x→GetRightChild();q=ThreadInOrderFirst(q);q→SetLeftChild(x);}}二叉樹的應(yīng)用

二叉樹結(jié)構(gòu)在實(shí)際問題中有著廣泛的應(yīng)用。二叉排序樹、堆排序、哈夫曼樹等是最典型的二叉樹應(yīng)用。作為二叉樹的應(yīng)用例子，本節(jié)介紹堆和哈夫曼樹(或稱最優(yōu)二叉樹)以及哈夫曼樹在編碼問題中的應(yīng)用。1．堆的定義設(shè)有n個(gè)數(shù)據(jù)元素的關(guān)鍵字為（k0、k1、…、kn-1），如果它們滿足以下的關(guān)系：ki<=k2i+1且ki<=k2i+2（或ki>=k2i+1且ki>=k2i+2）（i=0、1、…、(n-2)/2）則稱之為堆(Heap)。如果將此數(shù)據(jù)元素序列用一維數(shù)組存儲(chǔ)，并將此數(shù)組對(duì)應(yīng)一棵完全二叉樹，則堆的含義可以理解為：在完全二叉樹中任何非終端結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的關(guān)鍵字。堆

右圖(b)、(c)分別給出了最小堆和最大堆的例子，前者任一非終端結(jié)點(diǎn)的關(guān)鍵字均小于或等于它的左、右孩子的關(guān)鍵字，此時(shí)位于堆頂(即完全二叉樹的根結(jié)點(diǎn)位置)的結(jié)點(diǎn)的關(guān)鍵字是整個(gè)序列中最小的，所以稱它為最小堆；后者任一非終端結(jié)點(diǎn)的關(guān)鍵字均大于或等于它的左、右孩子的關(guān)鍵字，此時(shí)位于堆頂?shù)慕Y(jié)點(diǎn)的關(guān)鍵字是整個(gè)序列中最大的，所以稱它為最大堆。最小堆的類定義:template<classType>classMinHeap{public:MinHeap(intmaxSize);//構(gòu)造函數(shù)，建立空堆

MinHeap(Typea[],intn);//構(gòu)造函數(shù)，以數(shù)組a[]的值建立堆

~MinHeap(){delete[]heapArr;}//析構(gòu)函數(shù)

intInsert(constType&d);//在堆中插入元素dTypeDeleteTop();//刪除堆頂元素

TypeGetTop()const//取堆頂元素值

{returnheapArr[0];}

intIsEmpty()const//判斷堆是否為空?？斩逊祷?，否則返回0{returnheapCurrentSize==0;}intIsFull()const//判斷堆是否為滿。滿堆返回1，否則返回0{returnheapCurrentSize==heapMaxSize;}

intSizeofHeap()const//取堆的當(dāng)前元素?cái)?shù)目

{returnheapCurrentSize;}

voidSetEmpty(){heapCurrentSize=0;}//置堆為一個(gè)空堆private:Type*heapArr;//存放堆中數(shù)據(jù)元素的數(shù)組

intheapCurrentSize;//堆中當(dāng)前數(shù)據(jù)元素?cái)?shù)目

intheapMaxSize;//堆中數(shù)據(jù)元素的最大數(shù)目

voidFilterDown(intp);//向下調(diào)整使以結(jié)點(diǎn)p為根的子樹成為堆

voidFilterUp(intp);//向上調(diào)整使結(jié)點(diǎn)p所在的子樹成為堆}2．堆的構(gòu)造在最小堆的類定義中，有兩個(gè)構(gòu)造函數(shù)用于建立堆，第一個(gè)構(gòu)造函數(shù)建立一個(gè)空間大小maxSize的空堆；另一個(gè)構(gòu)造函數(shù)是通過復(fù)制一個(gè)記錄數(shù)組并對(duì)其進(jìn)行調(diào)整形成一個(gè)堆。下面分別給出這兩個(gè)構(gòu)造函數(shù)的定義。template<classType>MinHeap<Type>::MinHeap(intmaxSize){//根據(jù)給定大小maxSize,建立空堆

if(maxSize<=0){cerr<<”堆的大小不能小于1”<<endl;exit(1);}heapMaxSize=maxSize;//確定堆的最大空間

heapArr=newType[heapMaxSize];//創(chuàng)建堆空間

heapCurrentSize=0;//初始化}template<classType>MinHeap<Type>::MinHeap(Typea[],intn){//根據(jù)數(shù)組a[]中的數(shù)據(jù),建立堆,n為數(shù)組的大小

if(n<=0){cerr<<”堆的大小不能小于1”<<endl;exit(1);}heapMaxSize=n;//確定堆的最大空間

heapArr=newType[heapMaxSize];//創(chuàng)建堆空間

heapArr=a;//數(shù)組傳送

heapCurrentSize=n;//當(dāng)前堆大小

inti=(heapCurrentSize-2)/2;//找最后一個(gè)分支結(jié)點(diǎn)的序號(hào)

while(i>=0){//自下而上逐步調(diào)整形成堆

FilterDown(i);//從i開始到heapCurrentSize為止進(jìn)行調(diào)整

i--;}}

調(diào)整算法FilterDown要求將以分支結(jié)點(diǎn)i為根的子樹調(diào)整為最小堆，其基本思想是：從結(jié)點(diǎn)i開始向下調(diào)整，先比較結(jié)點(diǎn)i左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)的關(guān)鍵字大小，如果結(jié)點(diǎn)i左孩子結(jié)點(diǎn)的關(guān)鍵字小于右孩子結(jié)點(diǎn)的關(guān)鍵字，則沿結(jié)點(diǎn)i的左分支進(jìn)行調(diào)整；否則沿結(jié)點(diǎn)i的右分支進(jìn)行調(diào)整，在算法中用j指示關(guān)鍵字值較小的孩子結(jié)點(diǎn)。然后結(jié)點(diǎn)i和結(jié)點(diǎn)j進(jìn)行關(guān)鍵字比較，若結(jié)點(diǎn)i的關(guān)鍵字大于結(jié)點(diǎn)j的關(guān)鍵字，則兩結(jié)點(diǎn)對(duì)調(diào)位置，相當(dāng)于把關(guān)鍵字小的結(jié)點(diǎn)上浮。再令i＝j(luò)，j＝2*j十l，繼續(xù)向下一層進(jìn)行比較；若結(jié)點(diǎn)i的關(guān)鍵字不大于結(jié)點(diǎn)j的關(guān)鍵字或結(jié)點(diǎn)i沒有孩子時(shí)調(diào)整結(jié)束。向下調(diào)整算法的定義。template<classType>voidMinHeap<Type>::FilterDown(const

intstart){inti=start,j;Typetemp=heapArr[i];j=2*i+1;//j為i的左孩子

while(j<heapCurrentSize){

if(j<heapCurrentSize-1&&heapArr[j].key>heapArr[j+1].key)j++;//在左右孩子中選關(guān)鍵字較小者

if(temp.key<=heapArr[j].key)break;

else{heapArr[i]=heapArr[j];i=j;j=2*j+1;}}heapArr[i]=temp;}3．在堆中插入元素在堆的類定義中成員函數(shù)Insert()用于在堆中插入一個(gè)數(shù)據(jù)元素，在此規(guī)定數(shù)據(jù)元素總是插在已經(jīng)建成的最小堆后面，如下圖所示在堆中插入關(guān)鍵字為14的數(shù)據(jù)元素。顯然在堆中插入元素后可能破壞堆的性質(zhì)，所以還需要調(diào)用FilterUp()函數(shù)，進(jìn)行自下而上調(diào)整使之所在的子樹成為堆。成員函數(shù)Insert()的C++描述:template<classType>intMinHeap<Type>::Insert(constType&d){//在堆中插入新元素d

if(IsFull())//堆滿

{cout<<"堆已滿"<<endl;return0;}heapArr[heapCurrentSize]=d;//在堆尾插入數(shù)據(jù)元素dFilterUp(heapCurrentSize);//向上調(diào)整為堆

heapCurrentSize++;//堆元素?cái)?shù)目加1

return1;}下面給出函數(shù)FilterUp()的C++描述template<classType>voidMinHeap<Type>::FilterUp(intp){//從p開始向上調(diào)整。使序列成為堆

intj=p,i;Typetemp=heapArr[j];i=(j-1)/2;//i是

j的雙親

while(j>0){

if(heapArr[i].key<=temp.key)break;

else{heapArr[j]=heapArr[i];j=i;i=(j-1)/2;}}heapArr[j]=temp;}4．在堆中刪除元素在堆的類定義中成員函數(shù)DeleteTop()用于刪除堆頂數(shù)據(jù)元素。在從堆中刪除堆頂元素后，一般把堆的最后一個(gè)元素移到堆頂，并將堆的當(dāng)前元素個(gè)數(shù)heapCurrentSize減1，最后需要調(diào)用FilterDown()函數(shù)從堆頂向下進(jìn)行調(diào)整。如圖6-20所示給出了在堆中刪除堆頂元素的過程。成員函數(shù)DeleteTop()的C++描述:template<classType>TypeMinHeap<Type>::DeleteTop(){

if(IsEmpty()){cout<<“堆已空

"<<endl;return

NULL;}Typetemp=heapArr[0];//取堆頂元素

heapA