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

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

2、m0)個互不相交的有限集合T1, T2, , Tm，其中每一個集合又都是一棵樹。T1, T2, , Tm稱為根的子樹子樹(SubTree)。 另一定義：樹是一個不存在回路的連通圖。為簡便起見，我們以單個字母表示樹中的結(jié)點(diǎn)信息。如：A只有根的樹ABC有兩棵子樹有三棵子樹ABCDGEF(a)(b)(c)：信息項(xiàng)加上與其它項(xiàng)(結(jié)點(diǎn))聯(lián)系的分支 結(jié)點(diǎn)的度：一個結(jié)點(diǎn)的子樹數(shù)目(出支數(shù)目)稱為該結(jié)點(diǎn)的度度(Degree)。 根結(jié)點(diǎn)：一棵樹中入支數(shù)為零的結(jié)點(diǎn)(僅有一個結(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)”。：樹中各結(jié)點(diǎn)度的最大值 。結(jié)點(diǎn)x的子樹的根是結(jié)點(diǎn)x的孩子孩子(Child)(子女)，而x是其孩子的雙親雙親(Parent)。同一雙親的孩子為兄弟兄弟 (Sibling)(同胞、姐妹)。雙親在同一層上的結(jié)點(diǎn)為堂兄弟堂兄弟。祖先祖先(先輩)：一個結(jié)點(diǎn)的祖先是指從根到該結(jié)點(diǎn)的一條路徑上的所有結(jié)點(diǎn)。子孫子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。令根的層次為1，根的諸孩子的層次為2，以此類推，第L層上的結(jié)點(diǎn)的孩子的層次為L+1層。ABCDGEFHIJKLM1層2層3層4層樹中結(jié)點(diǎn)的最大層次數(shù)注意：區(qū)分樹的度與深度的概念注意

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

5、空的，或者是由特殊的稱為根的結(jié)點(diǎn)，以及該根的兩個互不相交的，分別稱為左子樹和右子樹的二叉樹組成。(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)：二叉樹具有如下的特點(diǎn)：二叉樹具有如下的特點(diǎn)： 存在空的二叉樹 二叉樹中結(jié)點(diǎn)的度不大于2 (度為0， 1或2) 二叉樹是有序的，它的子樹分別稱為左子樹和右子樹。其次序

6、不能任意顛倒。(二叉樹中某一結(jié)點(diǎn)的左分支結(jié)點(diǎn)稱為左孩子左孩子，右分支結(jié)點(diǎn)稱為右孩子右孩子) ABABBAB 有關(guān)樹的術(shù)語對二叉樹均適用。二叉樹和樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)。二叉樹和樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)。A3) ADT二叉樹的定義：二叉樹的定義： P121-123：在二叉樹中，第i層上的結(jié)點(diǎn)數(shù)最多為2i1(i1)。(歸納法)： 當(dāng)i=1時，只有一個結(jié)點(diǎn)，2i1=20=1(歸納基礎(chǔ))歸納假設(shè)：設(shè)對所有的j, 1ji 性質(zhì)成立，即第j層上結(jié)點(diǎn)總數(shù)最多為2j1個結(jié)點(diǎn)。則可證明 j=i 時命題成立。歸納步驟：由假設(shè)可知，i1層上的結(jié)點(diǎn)總數(shù)最多為2i2。由于二叉樹每個結(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的二叉樹至多有2k1個結(jié)點(diǎn) (k1)。證證：深度為k的二叉樹結(jié)點(diǎn)最大數(shù)為每一層結(jié)點(diǎn)最大數(shù)之和。由特性一得：122)(111kkiikii層上結(jié)點(diǎn)最大數(shù)第：對任一棵二叉樹，若葉結(jié)點(diǎn)數(shù)為n0, 度為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1 成立。證證：設(shè)度為1的結(jié)點(diǎn)數(shù)為n1，則二叉樹的結(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ù)為B，除根結(jié)點(diǎn)外，每一個結(jié)點(diǎn)都有一個分支進(jìn)入，則B=n1 又因?yàn)槎葹?的結(jié)點(diǎn)發(fā)出一個分支，度為2的結(jié)點(diǎn)發(fā)

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

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

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

11、一種遞歸的結(jié)構(gòu)，我們可以采用遞歸的方法來描述其先序遍歷算法。基本思想為：若二叉樹空則退出，否則作如下操作：訪問根結(jié)點(diǎn)遍歷左子樹(按先序)遍歷右子樹(按先序)遞歸算法如下遞歸算法如下:Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲結(jié)構(gòu)，采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 先序遍歷二叉樹先序遍歷二叉樹T的遞歸算法，對每個元素調(diào)用函數(shù)的遞歸算法，對每個元素調(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; 注：最簡單的Visit函數(shù)是：Status PrintElement(TElemType e) / 輸出元素輸出元素e的值的值 printf(e); / 實(shí)用時加上格式串實(shí)用時加上格式串return OK;調(diào)用先序遍歷算法實(shí)例：PreOrderTraverse(T, PrintElement);2) 中序遍歷中序遍歷(InOrder Traverse)前例圖中

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

15、元素調(diào)用函數(shù)Visit。else / 根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹 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)棧遍歷左子樹根指針進(jìn)棧遍歷左子樹 / while / InOrderTraversep = prchild; / else 非遞歸算法二如下非遞歸算法二如下:Status InOrderTraverse(BiT

16、ree T, Status(*Visit)(TElemType e) /采用二叉鏈表存儲結(jié)構(gòu)，采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 中序遍歷二叉樹中序遍歷二叉樹T的非遞歸算法，對每個元素調(diào)用函數(shù)的非遞歸算法，對每個元素調(diào)用函數(shù)Visit。Pop(S, p); if ( ! Visit(pdata) return ERROR; if ( ! StackEmpty(S) / 訪問結(jié)點(diǎn)，向右一步訪問結(jié)點(diǎn)，向右一步return OK; Pop(S, p); / 空指針退?？罩羔樛藯nitStack(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)行效率;假定二叉樹有n個結(jié)點(diǎn),對每個結(jié)點(diǎn)都要入棧一次,也要出棧一次。此外，當(dāng)p = NULL時，才對當(dāng)前棧頂結(jié)點(diǎn)信息處理(訪問棧頂結(jié)點(diǎn))，而p = NULL的情況發(fā)生在遇到空鏈域的情況，二叉樹的空鏈域?yàn)椋?n0+n1=n0+n1+n2+1=n+1所以算法的時間量可記為O(n).空間量：(除二叉樹

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

19、數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 / 后序遍歷二叉樹后序遍歷二叉樹T的遞歸算法，對每個元素調(diào)用函數(shù)的遞歸算法，對每個元素調(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)一 三種遍歷算法的不同之處不同之處：僅在于訪問根結(jié)點(diǎn)與左、右子樹之間的先后次序不同而已，如果用遞歸法來描述，則

20、可由P130頁圖6.10可得出三種遍歷序列。 其中：向下表示更深一層遞歸調(diào)用，向上表示從遞歸返回。5) 層序遍歷層序遍歷(LevelOrder Traverse) (略略)6) 先序建立二叉鏈表算法先序建立二叉鏈表算法 P131Status CreateBiTree(BiTree &T) / 按先序次序輸入二叉樹中結(jié)點(diǎn)的值按先序次序輸入二叉樹中結(jié)點(diǎn)的值(一個字符一個字符)， / 空格字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹空格字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹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)造左子樹構(gòu)造左子樹CreateBiTree (Trchild); / 構(gòu)造右子樹構(gòu)造右子樹由遍歷二叉樹可得到二叉樹中結(jié)點(diǎn)的一個線性序列，從而使得非線性的二叉樹結(jié)構(gòu)成為一種線性序列結(jié)構(gòu)，二叉樹的每一個結(jié)點(diǎn)在這種序列中有且僅有一個直接前驅(qū)和直接后繼(序列中第一個和最后一個結(jié)點(diǎn)例外)。例：BCDAE先序：ABCDEB的前驅(qū)A，后繼C中序：CBDEAB的

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

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

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

25、1D1AB0C0D 二叉樹的二叉線索存儲表示二叉樹的二叉線索存儲表示/-二叉樹的二叉線索存儲表示二叉樹的二叉線索存儲表示-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 類型。類型。以下我們以中序線索二叉樹為例來討論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時，plchild就是p所指結(jié)點(diǎn)的前驅(qū)當(dāng)pltag=0時，沿p的左孩子的右鏈找到一個結(jié)點(diǎn)的rtag=1時，則該結(jié)點(diǎn)就是p所指結(jié)點(diǎn)的前驅(qū)。 即：即：p所指示結(jié)點(diǎn)的左子樹中最后訪問到的所指示結(jié)點(diǎn)的左子樹中最后訪問到的結(jié)點(diǎn)則為結(jié)點(diǎn)則為p的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)Status Prior (BiThrTree p, ElemType &e) /

27、在中序線索樹中找出指針在中序線索樹中找出指針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中序線索樹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)的右孩子的左鏈找到一個結(jié)點(diǎn)的ltag=1時，則該結(jié)點(diǎn)就是p指針?biāo)附Y(jié)點(diǎn)的后繼結(jié)點(diǎn)。(即：p的右子樹中最先訪問到

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對于在后序線索二叉樹中如何確定結(jié)點(diǎn)的后繼，(因與雙親有關(guān)，所以必須以三叉線索鏈作為存儲

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

30、序中序遍歷二叉樹遍歷二叉樹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;/ 最后一個結(jié)點(diǎn)最后一個結(jié)點(diǎn)線索化線索化if ( !T ) Thrtlchild = Thrt; / 若二叉樹空，左指針回指若二叉樹空，左指針回指 / InOrderThreadingInT

31、hreading(T); / 中序中序遍歷進(jìn)行遍歷進(jìn)行中序線索化中序線索化 Thrtrchild = Thrt; / 右指針回指右指針回指prerchild = Thrt; preRTag = Thread; Thrtrchild = pre; / else void InThreading(BiThrTree p) InThreading(plchild); / 左子樹線索化左子樹線索化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); / 右子樹線索化右子樹線索化例：BCDAEFGHA0E1B1C1H 1bt D0F0G1 C B A E D G F H 以上算法僅對二叉樹中結(jié)點(diǎn)的右子樹線索化，因此前面所述的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 樹和森林樹和森林：n(n0)棵樹的集合 關(guān)于樹的存儲結(jié)構(gòu)，除前述的二叉鏈表結(jié)構(gòu)和多重鏈表結(jié)構(gòu)表示之外，請參見教材P135136中所介紹的三種表示。二叉樹表示一般樹的步驟：二叉樹表示一般樹的步驟：(1) 在各兄弟之間加一連線(2) 對任何結(jié)點(diǎn)，除最左的孩子以外，抹去該結(jié)點(diǎn)與其它孩子的各分支(3) 以樹的根為軸心，將整棵樹順時針方向大致旋轉(zhuǎn)45。即：即： 最左孩子不變，右兄弟變成右孩子；最左孩子不變，右兄弟變成右孩子； 單個單個孩子看成左孩子。孩子看成左孩子。1.

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

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

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

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

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

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