數(shù)據(jù)結(jié)構(gòu)06章_樹(shù)與二叉樹(shù)

1、前述我們所研究的數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)，本章將研究的樹(shù)型結(jié)構(gòu)是一種動(dòng)態(tài)的，非線性的，可描述結(jié)構(gòu)層次特性的數(shù)據(jù)結(jié)構(gòu)。此結(jié)構(gòu)是按分支關(guān)系把信息聯(lián)系起來(lái)的數(shù)據(jù)組織形式，在日常生活中這種結(jié)構(gòu)是不少見(jiàn)的，如：Chang Chang父祖父祖母Chang母外祖父外祖母中央人民政府湖南省湖北省上海市長(zhǎng)沙 全省各地市各市、縣、區(qū)以上兩例的數(shù)據(jù)(信息)組織形式，均稱為樹(shù)型結(jié)構(gòu)。當(dāng)然它與植物樹(shù)有所不同，(它的根在上，支在下)6.1 定義和基本術(shù)語(yǔ)定義和基本術(shù)語(yǔ)樹(shù)樹(shù)(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集合T，并滿足以下兩點(diǎn)： a) 有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn)；b) 當(dāng)n1時(shí)，除根以外的其余結(jié)點(diǎn)分成m(

2、m0)個(gè)互不相交的有限集合T1, T2, , Tm，其中每一個(gè)集合又都是一棵樹(shù)。T1, T2, , Tm稱為根的子樹(shù)子樹(shù)(SubTree)。 另一定義：樹(shù)是一個(gè)不存在回路的連通圖。為簡(jiǎn)便起見(jiàn)，我們以單個(gè)字母表示樹(shù)中的結(jié)點(diǎn)信息。如：A只有根的樹(shù)ABC有兩棵子樹(shù)有三棵子樹(shù)ABCDGEF(a)(b)(c)：信息項(xiàng)加上與其它項(xiàng)(結(jié)點(diǎn))聯(lián)系的分支 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目(出支數(shù)目)稱為該結(jié)點(diǎn)的度度(Degree)。 根結(jié)點(diǎn)：一棵樹(shù)中入支數(shù)為零的結(jié)點(diǎn)(僅有一個(gè)結(jié)點(diǎn)稱為根根(Root) 葉結(jié)點(diǎn)(終端結(jié)點(diǎn))：度為零的結(jié)點(diǎn)稱為葉結(jié)葉結(jié)點(diǎn)點(diǎn)(Leaf) (或“終端結(jié)點(diǎn)”) ；反之，度不為零的結(jié)點(diǎn)稱為“非終端

3、結(jié)點(diǎn)”(或稱為“分支結(jié)點(diǎn)”)，除根以外的分支結(jié)點(diǎn)又稱為“內(nèi)部結(jié)點(diǎn)”。：樹(shù)中各結(jié)點(diǎn)度的最大值 。結(jié)點(diǎn)x的子樹(shù)的根是結(jié)點(diǎn)x的孩子孩子(Child)(子女)，而x是其孩子的雙親雙親(Parent)。同一雙親的孩子為兄弟兄弟 (Sibling)(同胞、姐妹)。雙親在同一層上的結(jié)點(diǎn)為堂兄弟堂兄弟。祖先祖先(先輩)：一個(gè)結(jié)點(diǎn)的祖先是指從根到該結(jié)點(diǎn)的一條路徑上的所有結(jié)點(diǎn)。子孫子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。令根的層次為1，根的諸孩子的層次為2，以此類推，第L層上的結(jié)點(diǎn)的孩子的層次為L(zhǎng)+1層。ABCDGEFHIJKLM1層2層3層4層樹(shù)中結(jié)點(diǎn)的最大層次數(shù)注意：區(qū)分樹(shù)的度與深度的概念注意

4、：區(qū)分樹(shù)的度與深度的概念如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成是從左至右是有次序的(不能互換)，樹(shù)中任意結(jié)點(diǎn)最左邊的子樹(shù)為該結(jié)點(diǎn)的第一棵子樹(shù)，最右邊的子樹(shù)為最后一棵子樹(shù)，則稱該樹(shù)為有序樹(shù)有序樹(shù)，否則為無(wú)序樹(shù)無(wú)序樹(shù)。對(duì)于有序樹(shù)來(lái)說(shuō)，以下幾棵樹(shù)是各不相同的。ABCACB：n(n0)棵互不相交的樹(shù)的集合為森林。 注：除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)是雙重注：除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)是雙重身份，既是孩子，又是雙親。身份，既是孩子，又是雙親。 注：任一棵樹(shù)的子樹(shù)集合即為注：任一棵樹(shù)的子樹(shù)集合即為“森林森林”。6.2 二叉樹(shù)二叉樹(shù) (Binary trees)1) 二叉樹(shù)：二叉樹(shù)：是結(jié)點(diǎn)的有限集合，這個(gè)集合或者是

5、空的，或者是由特殊的稱為根的結(jié)點(diǎn)，以及該根的兩個(gè)互不相交的，分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。(A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.)2) 特點(diǎn)：特點(diǎn)：二叉樹(shù)具有如下的特點(diǎn)：二叉樹(shù)具有如下的特點(diǎn)： 存在空的二叉樹(shù) 二叉樹(shù)中結(jié)點(diǎn)的度不大于2 (度為0， 1或2) 二叉樹(shù)是有序的，它的子樹(shù)分別稱為左子樹(shù)和右子樹(shù)。其次序

6、不能任意顛倒。(二叉樹(shù)中某一結(jié)點(diǎn)的左分支結(jié)點(diǎn)稱為左孩子左孩子，右分支結(jié)點(diǎn)稱為右孩子右孩子) ABABBAB 有關(guān)樹(shù)的術(shù)語(yǔ)對(duì)二叉樹(shù)均適用。二叉樹(shù)和樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)。二叉樹(shù)和樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)。A3) ADT二叉樹(shù)的定義：二叉樹(shù)的定義： P121-123：在二叉樹(shù)中，第i層上的結(jié)點(diǎn)數(shù)最多為2i1(i1)。(歸納法)： 當(dāng)i=1時(shí)，只有一個(gè)結(jié)點(diǎn)，2i1=20=1(歸納基礎(chǔ))歸納假設(shè)：設(shè)對(duì)所有的j, 1ji 性質(zhì)成立，即第j層上結(jié)點(diǎn)總數(shù)最多為2j1個(gè)結(jié)點(diǎn)。則可證明 j=i 時(shí)命題成立。歸納步驟：由假設(shè)可知，i1層上的結(jié)點(diǎn)總數(shù)最多為2i2。由于二叉樹(shù)每個(gè)結(jié)點(diǎn)的度最大為2，所以第i層上的結(jié)點(diǎn)最大

7、數(shù)為第i1層上結(jié)點(diǎn)最大數(shù)的2倍，即2 2i1，從而得證，i層上最大結(jié)點(diǎn)數(shù)為2i1.：深度為k的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn) (k1)。證證：深度為k的二叉樹(shù)結(jié)點(diǎn)最大數(shù)為每一層結(jié)點(diǎn)最大數(shù)之和。由特性一得：122)(111kkiikii層上結(jié)點(diǎn)最大數(shù)第：對(duì)任一棵二叉樹(shù)，若葉結(jié)點(diǎn)數(shù)為n0, 度為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1 成立。證證：設(shè)度為1的結(jié)點(diǎn)數(shù)為n1，則二叉樹(shù)的結(jié)點(diǎn)總數(shù)為：n=n0+n1+ n2 (1)即：終端結(jié)點(diǎn)數(shù)比度為即：終端結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多的結(jié)點(diǎn)數(shù)多1。設(shè)二叉樹(shù)的分支總數(shù)為B，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，則B=n1 又因?yàn)槎葹?的結(jié)點(diǎn)發(fā)出一個(gè)分支，度為2的結(jié)點(diǎn)發(fā)

8、出2個(gè)分支所以： B=n1+2n2從而得 n=n1+2n2+1 (2)由(1), (2)式得 n0=n2+1 成立.(1) 滿二叉樹(shù)：滿二叉樹(shù)：深度為k，且具有2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為深度為k的滿二叉樹(shù)。例：BDEACFG在滿二叉樹(shù)中只有度為0或?yàn)?的結(jié)點(diǎn)。(只是滿二叉樹(shù)的必要條件，而不是充分條件)(2) 完全二叉樹(shù)：完全二叉樹(shù)：若對(duì)滿二叉樹(shù)，從根結(jié)點(diǎn)起自上而下，從左至右進(jìn)行連續(xù)編號(hào)，則可得到滿二叉樹(shù)的一種順序表示。并由此可引出完全二叉樹(shù)定義為：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱該二叉樹(shù)為完全二叉樹(shù)完全二叉樹(shù)。滿二叉樹(shù)如

9、：4892510116121337141514892510116371完全二叉樹(shù) 完全二叉樹(shù)的特點(diǎn)：完全二叉樹(shù)的特點(diǎn)： 葉子結(jié)點(diǎn)只可能在層次葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；最大的兩層上出現(xiàn)； 對(duì)任一結(jié)點(diǎn)，若其右分支下對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為的子孫的最大層次為k ，則其左分支下的子孫的最大，則其左分支下的子孫的最大層次必為層次必為k或或k +1 。由以上所述的特殊的二叉樹(shù)，則導(dǎo)出二叉樹(shù)的另兩個(gè)特性：具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)(或完全二叉樹(shù))，其深度為： k=log2n+1證證：根據(jù)性質(zhì)2和完全二叉樹(shù)的定義，設(shè)完全二叉樹(shù)的深度為k，則 2k1 1 n 2k1深度為k1的完全二叉

10、樹(shù)的最大結(jié)點(diǎn)數(shù)深度為k的完全二叉樹(shù)的最大結(jié)點(diǎn)數(shù)即2k1 n 2k 于是有k1 log2ndata) return ERROR; / 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)return OK; Push(S, p); p = plchild; / 根指針進(jìn)棧遍歷左子樹(shù)根指針進(jìn)棧遍歷左子樹(shù) Pop(S, p); p = prchild; / else InitStack(S); p = T;while (p | ! StackEmpty(S) if (p) / while / PreOrderTraverse算法執(zhí)行情況：堆棧s的內(nèi)容指針p 的指向訪問(wèn)序列ABCDEAABABCABAADAAEAABCDE二叉樹(shù)作為

11、一種遞歸的結(jié)構(gòu)，我們可以采用遞歸的方法來(lái)描述其先序遍歷算法。基本思想為：若二叉樹(shù)空則退出，否則作如下操作：訪問(wèn)根結(jié)點(diǎn)遍歷左子樹(shù)(按先序)遍歷右子樹(shù)(按先序)遞歸算法如下遞歸算法如下:Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 先序遍歷二叉樹(shù)先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)Visit。if (Visit(Tdata)if (T) else return OK

12、; / PreOrderTraverseif (PreOrderTraverse (Tlchild, Visit)if (PreOrderTraverse (Trchild, Visit)return OK; return ERROR; 注：最簡(jiǎn)單的Visit函數(shù)是：Status PrintElement(TElemType e) / 輸出元素輸出元素e的值的值 printf(e); / 實(shí)用時(shí)加上格式串實(shí)用時(shí)加上格式串return OK;調(diào)用先序遍歷算法實(shí)例：PreOrderTraverse(T, PrintElement);2) 中序遍歷中序遍歷(InOrder Traverse)前例圖中

13、的二叉樹(shù)的中序序列為：C B D E A 和 a+b*cde/f (中綴式)遞歸算法：遞歸算法：若二叉樹(shù)空則退出，否則：遍歷左子樹(shù)(按中序)訪問(wèn)根結(jié)點(diǎn)遍歷右子樹(shù)(按中序)遞歸算法如下遞歸算法如下:Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)Visit。if (Visit(Tdata)if (T) else ret

14、urn OK; / InOrderTraverseif (InOrderTraverse (Tlchild, Visit)if (InOrderTraverse (Trchild, Visit)return OK; return ERROR; 非遞歸算法一如下非遞歸算法一如下:Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)的非遞歸算法，對(duì)每個(gè)

15、元素調(diào)用函數(shù)Visit。else / 根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù) if ( ! Visit(pdata) return ERROR; return OK; Pop(S, p); InitStack(S); p = T;while (p | ! StackEmpty(S) if (p) Push(S, p); p = plchild; / 根指針進(jìn)棧遍歷左子樹(shù)根指針進(jìn)棧遍歷左子樹(shù) / while / InOrderTraversep = prchild; / else 非遞歸算法二如下非遞歸算法二如下:Status InOrderTraverse(BiT

16、ree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)的非遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)Visit。Pop(S, p); if ( ! Visit(pdata) return ERROR; if ( ! StackEmpty(S) / 訪問(wèn)結(jié)點(diǎn)，向右一步訪問(wèn)結(jié)點(diǎn)，向右一步return OK; Pop(S, p); / 空指針退棧空指針退棧InitStack(S); Push(S, T); / 根指針進(jìn)棧

17、根指針進(jìn)棧while ( ! StackEmpty(S) while (GetTop(S, p) & p) Push(S,plchild); / 向左走到頭向左走到頭 / while / InOrderTraversePush(S, prchild); / if 算法分析：分析先序、中序遍歷的運(yùn)行效率;假定二叉樹(shù)有n個(gè)結(jié)點(diǎn),對(duì)每個(gè)結(jié)點(diǎn)都要入棧一次,也要出棧一次。此外，當(dāng)p = NULL時(shí)，才對(duì)當(dāng)前棧頂結(jié)點(diǎn)信息處理(訪問(wèn)棧頂結(jié)點(diǎn))，而p = NULL的情況發(fā)生在遇到空鏈域的情況，二叉樹(shù)的空鏈域?yàn)椋?n0+n1=n0+n1+n2+1=n+1所以算法的時(shí)間量可記為O(n).空間量：(除二叉樹(shù)

18、存儲(chǔ)結(jié)構(gòu)占用單元外), 其額外空間，即為堆棧s的空間。設(shè)二叉樹(shù)的深度為k，則堆棧s所需的空間為一個(gè)k個(gè)單元，所以其空間量記為O(k)3) 后序遍歷后序遍歷(PostOrder Traverse)仍以前例中的二叉樹(shù)為例，則其后序序列為CEDBA 和 abcd+ef/ 逆波蘭式遞歸算法：若二叉樹(shù)空退出，否則遍歷左子樹(shù)；(后序法)遍歷右子樹(shù)；(后序法)訪問(wèn)根結(jié)點(diǎn)。遞歸算法如下遞歸算法如下:Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對(duì)

19、數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 后序遍歷二叉樹(shù)后序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)的遞歸算法，對(duì)每個(gè)元素調(diào)用函數(shù)Visit。if (Visit(Tdata)if (T) else return OK; / PostOrderTraverseif (PostOrderTraverse (Tlchild, Visit)if (PostOrderTraverse (Trchild, Visit)return OK; return ERROR; 4) 三種遍歷算法的統(tǒng)一三種遍歷算法的統(tǒng)一 三種遍歷算法的不同之處不同之處：僅在于訪問(wèn)根結(jié)點(diǎn)與左、右子樹(shù)之間的先后次序不同而已，如果用遞歸法來(lái)描述，則

20、可由P130頁(yè)圖6.10可得出三種遍歷序列。 其中：向下表示更深一層遞歸調(diào)用，向上表示從遞歸返回。5) 層序遍歷層序遍歷(LevelOrder Traverse) (略略)6) 先序建立二叉鏈表算法先序建立二叉鏈表算法 P131Status CreateBiTree(BiTree &T) / 按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符一個(gè)字符)， / 空格字符表示空樹(shù)，構(gòu)造二叉鏈表表示的二叉樹(shù)空格字符表示空樹(shù)，構(gòu)造二叉鏈表表示的二叉樹(shù)T。else Tdata = ch; / 生成根結(jié)點(diǎn)生成根結(jié)點(diǎn)return OK; exit(OVERFLOW); scanf

21、(&ch);if (ch = = ) T = NULL;if ( ! (T = (BiTNode *)malloc(sizeof(BiTNode) / else / CreateBiTreeCreateBiTree (Tlchild); / 構(gòu)造左子樹(shù)構(gòu)造左子樹(shù)CreateBiTree (Trchild); / 構(gòu)造右子樹(shù)構(gòu)造右子樹(shù)由遍歷二叉樹(shù)可得到二叉樹(shù)中結(jié)點(diǎn)的一個(gè)線性序列，從而使得非線性的二叉樹(shù)結(jié)構(gòu)成為一種線性序列結(jié)構(gòu)，二叉樹(shù)的每一個(gè)結(jié)點(diǎn)在這種序列中有且僅有一個(gè)直接前驅(qū)和直接后繼(序列中第一個(gè)和最后一個(gè)結(jié)點(diǎn)例外)。例：BCDAE先序：ABCDEB的前驅(qū)A，后繼C中序：CBDEAB的

22、前驅(qū)C，后繼D后序：CEDBAB的前驅(qū)D，后繼A那么，如何確定二叉樹(shù)中某個(gè)結(jié)點(diǎn)在相應(yīng)序列中的前驅(qū)和后繼呢？即，能否定義一個(gè)求某一結(jié)點(diǎn)x在相應(yīng)序列中的前驅(qū)和后繼的運(yùn)算。如Prior(x)或Next(x).若二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，則結(jié)點(diǎn)結(jié)構(gòu)為：lchilddatarchild這只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)的前驅(qū)和后繼信息。這種前驅(qū)和后繼信息只能在遍歷的動(dòng)態(tài)過(guò)程中獲得。如何能保存這些信息，這就是我們下面所要研究的問(wèn)題。 一個(gè)簡(jiǎn)單的辦法是把每個(gè)結(jié)點(diǎn)增加兩個(gè)鏈域，fwd和bkwd分別指示結(jié)點(diǎn)的前驅(qū)和后繼。按某種序列遍歷二叉樹(shù)一次后，就可將各結(jié)點(diǎn)的前驅(qū)和后繼保存。lchildda

23、tarchildfwdbkwd如上例中的二叉樹(shù)，按中序序列遍歷一次后可得各結(jié)點(diǎn)信息如下表：lchildrchildfwddatabkwdCBDEBEABEEDABCDCD以這種結(jié)構(gòu)存儲(chǔ)二叉樹(shù)，顯然可以直接訪問(wèn)任一結(jié)點(diǎn)的前驅(qū)和后繼，但使得結(jié)構(gòu)的存儲(chǔ)密度大大降低，浪費(fèi)不少空間(特別是結(jié)點(diǎn)數(shù)多時(shí)) 仍以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，僅對(duì)每一結(jié)點(diǎn)增加兩個(gè)標(biāo)志域(布爾量)，即結(jié)點(diǎn)結(jié)構(gòu)為：lchildltagdatartagrchild前面我們已討論過(guò)，以二叉鏈表存儲(chǔ)n個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，有n+1個(gè)空鏈域，為充分的利用這些空鏈域，我們約定：ltag=0 有左孩子， lchild指向其左孩子1 無(wú)左孩子， lchil

24、d指向其前驅(qū)rtag=0 有右孩子，rchild指向其右孩子1 無(wú)右孩子，rchild指向其后繼以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表，稱為二叉線索二叉線索鏈表鏈表；其中指向結(jié)點(diǎn)的前驅(qū)和后繼的鏈域，稱為線索線索；具有線索的二叉樹(shù)，就是線索二叉樹(shù)線索二叉樹(shù)(Threaded Binary Tree)。按某種序列對(duì)二叉樹(shù)遍歷并加上線索使其成為線索二叉樹(shù)的過(guò)程稱為線索化線索化。一般在畫一棵線索二叉樹(shù)時(shí)，以實(shí)線表示指向左、右孩子的鏈，以虛線表示線索。例：BCDAEBCDAENil Nil 該二叉樹(shù)的中序線索樹(shù)中各結(jié)點(diǎn)的信息用表可列出為：ltaglchildrtagdatarchildC11BD1B0EA0B1E

25、1D1AB0C0D 二叉樹(shù)的二叉線索存儲(chǔ)表示二叉樹(shù)的二叉線索存儲(chǔ)表示/-二叉樹(shù)的二叉線索存儲(chǔ)表示二叉樹(shù)的二叉線索存儲(chǔ)表示-TElemType data ；struct BiThrNode *lchild, *rchild / 左右孩子指針左右孩子指針typedef struct BiThrNode BiThrNode , *BiThrTree ；typedef enum Link, Thread PointerTag; / Link = = 0：指針；：指針；Thread= = 1：線索：線索PointerTag Ltag, Rtag; / 左右標(biāo)志左右標(biāo)志注：此結(jié)構(gòu)可以用注：此結(jié)構(gòu)可以用bo

26、ol類型替換類型替換enum Link, Thread 類型。類型。以下我們以中序線索二叉樹(shù)為例來(lái)討論P(yáng)rior、Next和Insert運(yùn)算。 a) Prior運(yùn)算運(yùn)算(求某一結(jié)點(diǎn)的前驅(qū)求某一結(jié)點(diǎn)的前驅(qū)) 算法思想：設(shè)某一結(jié)點(diǎn)由指針P指向，則當(dāng)pltag=1時(shí)，plchild就是p所指結(jié)點(diǎn)的前驅(qū)當(dāng)pltag=0時(shí)，沿p的左孩子的右鏈找到一個(gè)結(jié)點(diǎn)的rtag=1時(shí)，則該結(jié)點(diǎn)就是p所指結(jié)點(diǎn)的前驅(qū)。 即：即：p所指示結(jié)點(diǎn)的左子樹(shù)中最后訪問(wèn)到的所指示結(jié)點(diǎn)的左子樹(shù)中最后訪問(wèn)到的結(jié)點(diǎn)則為結(jié)點(diǎn)則為p的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)Status Prior (BiThrTree p, ElemType &e) /

27、在中序線索樹(shù)中找出指針在中序線索樹(shù)中找出指針P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) t = plchild; if ( ! pltag ) while ( ! trtag ) t = trchild; e = tdata; / Prior return OK;例：BCDAE中序線索樹(shù)0A11D00B01C11E1root中序序列：CBDEA b) Next運(yùn)算運(yùn)算(求求p指針?biāo)附Y(jié)點(diǎn)的后繼指針?biāo)附Y(jié)點(diǎn)的后繼) 如果prtag=1，則prchild就是p所指結(jié)點(diǎn)的后繼 否則，沿p所指結(jié)點(diǎn)的右孩子的左鏈找到一個(gè)結(jié)點(diǎn)的ltag=1時(shí)，則該結(jié)點(diǎn)就是p指針?biāo)附Y(jié)點(diǎn)的后繼結(jié)點(diǎn)。(即：p的右子樹(shù)中最先訪問(wèn)到

28、的結(jié)點(diǎn))Status Next (BiThrTree p, ElemType &e) / 求求p指針?biāo)附Y(jié)點(diǎn)的后繼，求得的后繼由指針?biāo)附Y(jié)點(diǎn)的后繼，求得的后繼由e返回返回 t = prchild; if ( ! prtag ) while ( ! tltag )t = tlchild;e = tdata;return OK; / Next例：中序序列DBEAGFC以A結(jié)點(diǎn)為例：沿右孩子C結(jié)點(diǎn)的左鏈直到結(jié)點(diǎn)G的ltag=1BDCAEFG0A01E10B01D11G1root0C10F0 A的后繼為結(jié)點(diǎn)G對(duì)于在后序線索二叉樹(shù)中如何確定結(jié)點(diǎn)的后繼，(因與雙親有關(guān)，所以必須以三叉線索鏈作為存儲(chǔ)

29、結(jié)構(gòu))以上所介紹的是在已建立線索的二叉樹(shù)中確定任意結(jié)點(diǎn)前驅(qū)和后繼，下面我們來(lái)討論如何建立線索的問(wèn)題，在以二叉線索鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)建立線索主要是將那些空的鏈域加上線索，以及各結(jié)點(diǎn)加上標(biāo)志。而這些線索的保存只有通過(guò)某種遍歷方式動(dòng)態(tài)的形成。即：線索化的實(shí)現(xiàn)。 由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，因而，線索化的過(guò)程即為在遍歷過(guò)程中修改空指針修改空指針的過(guò)程。我們可以附設(shè)一個(gè)pre指針始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)，若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向p的前驅(qū)。Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 中

30、序中序遍歷二叉樹(shù)遍歷二叉樹(shù)T，并將其中序線索化，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)。 if (! (Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW); ThrtLTag = Link; ThrtRTag = Thread; / 建頭結(jié)點(diǎn)建頭結(jié)點(diǎn)else return OK; Thrtlchild = T; pre = Thrt;/ 最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)線索化線索化if ( !T ) Thrtlchild = Thrt; / 若二叉樹(shù)空，左指針回指若二叉樹(shù)空，左指針回指 / InOrderThreadingInT

31、hreading(T); / 中序中序遍歷進(jìn)行遍歷進(jìn)行中序線索化中序線索化 Thrtrchild = Thrt; / 右指針回指右指針回指prerchild = Thrt; preRTag = Thread; Thrtrchild = pre; / else void InThreading(BiThrTree p) InThreading(plchild); / 左子樹(shù)線索化左子樹(shù)線索化if (! plchild) pLTag = Thread; plchild = pre; / ifif ( p ) / InThreading pre = p; / 保持保持pre指向指向p的前驅(qū)的前驅(qū)/

32、前驅(qū)線索前驅(qū)線索if (! prerchild) preRTag = Thread; prerchild = p; / 后繼線索后繼線索 InThreading(prchild); / 右子樹(shù)線索化右子樹(shù)線索化例：BCDAEFGHA0E1B1C1H 1bt D0F0G1 C B A E D G F H 以上算法僅對(duì)二叉樹(shù)中結(jié)點(diǎn)的右子樹(shù)線索化，因此前面所述的Next運(yùn)算的算法應(yīng)改為：Status Next (BiThrTree p, ElemType &e) t = prchild; if ( ! prtag ) while ( tlchild ) t = tlchild; e = td

33、ata; / Next/ 求求p指針?biāo)附Y(jié)點(diǎn)的后繼，求得的后繼由指針?biāo)附Y(jié)點(diǎn)的后繼，求得的后繼由e返回返回 return OK;6.4 樹(shù)和森林樹(shù)和森林：n(n0)棵樹(shù)的集合 關(guān)于樹(shù)的存儲(chǔ)結(jié)構(gòu)，除前述的二叉鏈表結(jié)構(gòu)和多重鏈表結(jié)構(gòu)表示之外，請(qǐng)參見(jiàn)教材P135136中所介紹的三種表示。二叉樹(shù)表示一般樹(shù)的步驟：二叉樹(shù)表示一般樹(shù)的步驟：(1) 在各兄弟之間加一連線(2) 對(duì)任何結(jié)點(diǎn)，除最左的孩子以外，抹去該結(jié)點(diǎn)與其它孩子的各分支(3) 以樹(shù)的根為軸心，將整棵樹(shù)順時(shí)針?lè)较虼笾滦D(zhuǎn)45。即：即： 最左孩子不變，右兄弟變成右孩子；最左孩子不變，右兄弟變成右孩子； 單個(gè)單個(gè)孩子看成左孩子。孩子看成左孩子。1.

34、 一般樹(shù)的二叉樹(shù)表示一般樹(shù)的二叉樹(shù)表示例例：JABCDEFG HIABCDEFG HIJABECFGDHIJ轉(zhuǎn)換方法：轉(zhuǎn)換方法：(1)將森林中各棵樹(shù)轉(zhuǎn)換成二叉樹(shù)(2)將每棵樹(shù)的根結(jié)點(diǎn)相連(3)以第一棵樹(shù)的根為軸心，將連接各棵樹(shù)的根的連線順時(shí)針?lè)较虼笾滦D(zhuǎn)45。即：即： 每棵樹(shù)分別先變成二叉樹(shù)；每棵樹(shù)分別先變成二叉樹(shù)； 將各樹(shù)的根將各樹(shù)的根結(jié)點(diǎn)看成兄弟；結(jié)點(diǎn)看成兄弟； 右兄弟變成右孩子即可；右兄弟變成右孩子即可； 所所得新的二叉樹(shù)的根為森林中第一棵樹(shù)的根。得新的二叉樹(shù)的根為森林中第一棵樹(shù)的根。例：例：ABCDEFGHIABCDEFGHIABCEFDGHI轉(zhuǎn)換方法：轉(zhuǎn)換方法： 左孩子不變即可。則得

35、森林，即若干棵樹(shù)。 從左至右，右孩子變成右兄弟；樹(shù)的遍歷有兩種方法：樹(shù)的遍歷有兩種方法：1) 先根遍歷法：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后從左至右依次遍歷根的每棵子樹(shù)。例：例：ABCEDABCDEABECFGHI DABCDGEFIH2)后根遍歷法：先依次遍歷根的每棵子樹(shù)，然后訪問(wèn)根。如上圖中的樹(shù)：后序：BDCEAEBGHIFCDAABCEDABCDGEFIH1)先序遍歷：若森林非空，則訪問(wèn)森林中第一棵樹(shù)(從左數(shù)起)的根，再遍歷第一棵樹(shù)的子樹(shù)森林；然后遍歷除第一棵樹(shù)之外的其它樹(shù)構(gòu)成的森林。2)中序遍歷：若森林非空，則遍歷第一棵樹(shù)的子樹(shù)構(gòu)成的森林，再訪問(wèn)第一棵樹(shù)的根，然后遍歷除第一棵之外的其它樹(shù)構(gòu)成的森林

36、。例：例：ABCDEFGHIJ先序：ABCDEFGHIJ中序：BCDAFEHJIG若樹(shù)以二叉樹(shù)表示，由樹(shù)和二叉樹(shù)的對(duì)應(yīng)關(guān)系，則可對(duì)其對(duì)應(yīng)的二叉樹(shù)進(jìn)行先序遍歷和中序遍歷，則可得到樹(shù)和森林的兩種序列。例：例：ABCDEABCED相應(yīng)二叉樹(shù)的先序序列：ABCDE相應(yīng)二叉樹(shù)的中序序列：BDCEA上例森林轉(zhuǎn)換成的二叉樹(shù)為：ABCEDFGHIJ先序：ABCDEFGHIJ 中序：BCDAFEHJIG因此，樹(shù)和森林的遍歷算法可借用二叉樹(shù)的先序遍歷和中序遍歷算法實(shí)現(xiàn)。即先將樹(shù)或森林轉(zhuǎn)換成與其對(duì)應(yīng)的二叉樹(shù)，然后進(jìn)行遍歷。即：樹(shù)的先序遍歷相應(yīng)二叉樹(shù)的先序遍歷樹(shù)的后序遍歷相應(yīng)二叉樹(shù)的中序遍歷森林的先序遍歷相應(yīng)二叉樹(shù)的

37、先序遍歷森林的中序遍歷相應(yīng)二叉樹(shù)的中序遍歷6.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用(Huffman tree)為介紹哈夫曼樹(shù)，我們先介紹路徑和路徑長(zhǎng)度的概念。樹(shù)中一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑；路徑上的分支數(shù)為路徑路徑長(zhǎng)度長(zhǎng)度。由此可定義：樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度為：從樹(shù)的根結(jié)點(diǎn)到樹(shù)中每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。例：例： a)b)樹(shù)的路徑長(zhǎng)度： pl=0+1+1+2+3+4=11 pl=0+1+1+2+2+2+2+3=13將路徑長(zhǎng)度的概念推廣到一般情況，考慮帶權(quán)的結(jié)點(diǎn)，則結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)值之乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的

38、帶權(quán)路徑長(zhǎng)度：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。即：若樹(shù)中有n個(gè)葉子結(jié)點(diǎn)，有n個(gè)實(shí)數(shù)w1, w2, , wn分別作為各葉子結(jié)點(diǎn)的權(quán)值，則樹(shù)的帶權(quán)路徑長(zhǎng)度記為：nkkkWLWPL1Lk: 從根到權(quán)值為Wk的葉結(jié)點(diǎn)的路徑長(zhǎng)度(即分支數(shù))Wk: 第K個(gè)葉子結(jié)點(diǎn)的權(quán)值。假設(shè)有n個(gè)權(quán)值，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)的帶權(quán)為Wi，則其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)。哈夫曼提出了構(gòu)造最優(yōu)二叉樹(shù)的方法，所以又稱最優(yōu)二叉樹(shù)為哈夫曼樹(shù)哈夫曼樹(shù)。例：例：如下圖的三棵二叉樹(shù)都具有4個(gè)葉結(jié)點(diǎn)，給定的權(quán)值為： WG =7, 5, 2, 4a)5427b)5427c)5427它們的帶權(quán)路

39、徑長(zhǎng)度分別為：a) WPL=22+42+52+72=36b) WPL=42+21+53+73=46c) WPL=71+52+43+23=35 由此例可見(jiàn)帶權(quán)路徑長(zhǎng)度最小的并不一定是完全二叉樹(shù)，(如果Wk=1(k=1,2,n)，那么WPL最小的才為完全二叉樹(shù))上圖c)的樹(shù)的WPL最小，實(shí)際上就是哈夫曼樹(shù)，該樹(shù)有一個(gè)明顯的特征，即權(quán)值最大的葉子離根最近，權(quán)小的離根遠(yuǎn)。究竟如何構(gòu)造具有此特征的二叉樹(shù)？哈夫曼提出了一個(gè)帶有一般規(guī)律的算法。即哈夫曼算法哈夫曼算法，可敘述如下： 給定n個(gè)權(quán)值w1, w2, w3, , wn構(gòu)成含有n棵二叉樹(shù)的森林：F=T1, T2, , Tn，其中每一棵樹(shù)Ti只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn) 在F中選取兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。 在F中刪除這兩棵二叉樹(shù)，并將新的二叉樹(shù)加入F中。 重復(fù)、直到F中只剩一棵二叉樹(shù)為止，該二叉樹(shù)就是哈夫曼樹(shù)。例：例：WG=7, 5, 2, 41) 5427排序2)