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

1、第六章第六章樹和二叉樹樹和二叉樹6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 第六章第六章 樹和二叉樹樹和二叉樹6.1 樹的類型定義樹的類型定義第六章 樹6.1 樹的定義樹的定義定義定義v定義：樹定義：樹(tree)是是n(n=0)個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的有限集有限集T，其，其中：中：ln=0 則稱為則稱為空樹空樹。l當(dāng)當(dāng)n0時(shí)，時(shí)，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的的根根(root)l當(dāng)當(dāng)n1時(shí)，時(shí)

2、，其余結(jié)點(diǎn)可分為其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交個(gè)互不相交的的有限集有限集T1,T2,Tm，其中每一個(gè)集合本，其中每一個(gè)集合本身又是一棵身又是一棵樹樹，稱為根的，稱為根的子樹子樹(subtree)A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為為空集，則稱為空樹空樹 。否則。否則: (1) 在在D中存在唯一的稱為中存在唯一的稱為根根的數(shù)據(jù)元素的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互個(gè)互 不相交的

3、有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的的子樹子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：ADT Tree 基本操作：基本操作：查找類查找類；插入類插入類; 刪除類刪除類； ADT Tree基本術(shù)語(yǔ)基本術(shù)語(yǔ)v結(jié)點(diǎn)結(jié)點(diǎn)(node)表示樹中的表示樹中的元素元素，包括，包括數(shù)據(jù)數(shù)據(jù)元素及若干元素及若干指向其子樹的指向其子樹的分支分支v結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的結(jié)點(diǎn)擁有的子樹數(shù)子樹數(shù)v葉子葉子(leaf)度為度為0的結(jié)點(diǎn)的結(jié)點(diǎn)v孩子孩子(child)結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的結(jié)點(diǎn)子樹的

4、根稱為該結(jié)點(diǎn)的孩子孩子v雙親雙親(parents)孩子結(jié)點(diǎn)的孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的叫該結(jié)點(diǎn)的v兄弟兄弟(sibling)同一雙親同一雙親的孩子的孩子v樹的度樹的度一棵樹中一棵樹中最大最大的結(jié)點(diǎn)度數(shù)的結(jié)點(diǎn)度數(shù)v結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，從根結(jié)點(diǎn)算起，根為第一層根為第一層，它，它的孩子為第二層的孩子為第二層v深度深度(depth)樹中結(jié)點(diǎn)的樹中結(jié)點(diǎn)的最大層次最大層次數(shù)數(shù)v森林森林(forest)m(m 0)棵棵互不相交互不相交的樹的集合的樹的集合ABCDEFGHIJKLM結(jié)點(diǎn)結(jié)點(diǎn)A的的度度：3結(jié)點(diǎn)結(jié)點(diǎn)B的的度度：2結(jié)點(diǎn)結(jié)點(diǎn)M的的度度：0葉子葉子：K，L，F(xiàn)，G，

5、M，I，J結(jié)點(diǎn)結(jié)點(diǎn)A的的孩子孩子：B，C，D結(jié)點(diǎn)結(jié)點(diǎn)B的的孩子孩子：E，F(xiàn)結(jié)點(diǎn)結(jié)點(diǎn)I的的雙親雙親：D結(jié)點(diǎn)結(jié)點(diǎn)L的的雙親雙親：E結(jié)點(diǎn)結(jié)點(diǎn)B，C，D為為兄弟兄弟結(jié)點(diǎn)結(jié)點(diǎn)K，L為為兄弟兄弟樹的度：樹的度：3結(jié)點(diǎn)結(jié)點(diǎn)A的層次：的層次：1結(jié)點(diǎn)結(jié)點(diǎn)M的層次：的層次：4樹的深度：樹的深度：4結(jié)點(diǎn)結(jié)點(diǎn)F，G為為堂兄弟堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)A是結(jié)點(diǎn)是結(jié)點(diǎn)F，G的的祖先祖先結(jié)點(diǎn)結(jié)點(diǎn)F,G是結(jié)點(diǎn)是結(jié)點(diǎn)A的子孫結(jié)點(diǎn)的子孫結(jié)點(diǎn)任何一棵非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組 Tree = (root，F(xiàn))其中：其中：root 被稱為根結(jié)點(diǎn)被稱為根結(jié)點(diǎn) F 被稱為子樹森林被稱為子樹森林森林：森林：是是m(m0)棵互棵互不相交

6、的樹的集合不相交的樹的集合ArootBCDEFGHIJMKLF趙老根趙老根趙躍進(jìn)趙躍進(jìn)趙小康趙小康趙改革趙改革趙開放趙開放趙解放趙解放趙抗美趙抗美趙衛(wèi)兵趙衛(wèi)兵趙永紅趙永紅 Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹是否為

7、空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹為根的樹插入為結(jié)點(diǎn)插入為結(jié)點(diǎn)p的第的第i棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪

8、除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹棵子樹ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根樹的廣義表表示法樹的廣義表表示法1、圖示法、圖示法2、廣義表法、廣義表法樹的幾種表示法樹的幾種表示法: :ABDCJIHMEFGKL有向樹有向樹：有序樹：有序樹：無(wú)序樹：無(wú)序樹：樹的基本分類：樹的基本分類：樹型結(jié)構(gòu)樹型結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu) 線性結(jié)構(gòu)線性結(jié)構(gòu) 樹型結(jié)構(gòu)樹型結(jié)構(gòu) ( (非線性結(jié)構(gòu)非線性結(jié)構(gòu))

9、 )第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無(wú)前驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 第六章第六章 樹和二叉樹樹和二叉

10、樹6.2 6.2 二叉樹二叉樹6.2.1 二叉樹的定義二叉樹的定義6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.2 6.2 二叉樹二叉樹6.2.1 二叉樹的定義二叉樹的定義v定義：二叉樹是定義：二叉樹是n(n 0)個(gè)結(jié)點(diǎn)的有限集，它或個(gè)結(jié)點(diǎn)的有限集，它或?yàn)闉榭諛淇諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹左子樹和和右子樹右子樹的的互不相交的互不相交的二叉樹構(gòu)成二叉樹構(gòu)成。v特點(diǎn)特點(diǎn)l每個(gè)結(jié)點(diǎn)至多有二棵子樹每個(gè)結(jié)點(diǎn)至多有二棵子樹l二叉樹的子樹有左、右之分，且其次序不能二叉樹的子樹有左、右之分，且其次序不能任意顛倒任意顛倒v基

11、本形態(tài)基本形態(tài)A只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)的二叉樹的二叉樹 空二叉樹空二叉樹AB右子樹為空右子樹為空AB左子樹為空左子樹為空ABC左、右子樹左、右子樹均非空均非空查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit()

12、; PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();查找類：查找類：InitBiTree(&T);Assign(T, &e, value);CreateBiTree(&T, definition);InsertChild(T, p, LR, c); 插入類：插入類：ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);刪除類：刪除類：6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)v性質(zhì)性質(zhì)1：在二叉樹的第：在二叉樹的第i層上至多有層上

13、至多有2i-1個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)(i1)證明：用歸納法證明之證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，時(shí)，只有一個(gè)根結(jié)點(diǎn)， 是對(duì)的是對(duì)的。 假設(shè)對(duì)所有假設(shè)對(duì)所有j(1 ji)命題成立，即第命題成立，即第j層上至層上至多有多有 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), 那么，第那么，第i-1層至多有層至多有 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 又二叉樹每個(gè)結(jié)點(diǎn)的度至多為又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2 第第i層上最大結(jié)點(diǎn)數(shù)是第層上最大結(jié)點(diǎn)數(shù)是第i-1層的層的2倍，即倍，即 故命題得證故命題得證12201i12j22i12222ii6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)v性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k 1)

14、12 k證明：由性質(zhì)證明：由性質(zhì)1，可得深度為，可得深度為k 的二叉樹最大結(jié)點(diǎn)的二叉樹最大結(jié)點(diǎn)數(shù)是數(shù)是122)(111kkikiii層的最大結(jié)點(diǎn)數(shù)第v性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為，如果其終端結(jié)點(diǎn)數(shù)為n0，度為，度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則，則n0=n2+1證明：證明：n1為二叉樹為二叉樹T中度為中度為1的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè) 分支進(jìn)入分支

15、進(jìn)入 設(shè)設(shè)B為分支總數(shù)，則為分支總數(shù)，則n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結(jié)點(diǎn)射出，的結(jié)點(diǎn)射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1幾種特殊形式的二叉樹幾種特殊形式的二叉樹v滿二叉樹滿二叉樹l定義：定義：12個(gè)結(jié)點(diǎn)的二叉樹稱為且有一棵深度為kkl特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)v完全二叉樹完全二叉樹l定義：深度為定義：深度為k，有，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中的滿二叉樹中編號(hào)從編號(hào)從1至至n的結(jié)點(diǎn)

16、一一對(duì)應(yīng)的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為時(shí)，稱為l特點(diǎn)特點(diǎn)u葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)u對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為為l，則其左分支下子孫的最大層次必為，則其左分支下子孫的最大層次必為l 或或l+11231145891213671014151231145891267101234567123456性質(zhì)性質(zhì)4：證明：假設(shè)深度為證明：假設(shè)深度為k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2和完全二和完全二叉樹的定義有叉樹的定義有 2 k-1-1n=2k-1或或2 k-1=n2k 于是于是k-1=log2n1，則其，則其雙親雙親是是

17、i/2 (2) 如果如果2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無(wú)左孩子；如果無(wú)左孩子；如果2i n，則其，則其左左孩子是孩子是2i (3) 如果如果2i+1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無(wú)右孩子；如果無(wú)右孩子；如果2i+1 n，則，則其其右孩子是右孩子是2i+1 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1圖圖6.11 6.11 完全二叉樹中結(jié)點(diǎn)完全二叉樹中結(jié)點(diǎn)i i和和i+1i+1(a)i(a)i和和i+1i+1結(jié)點(diǎn)在同一層結(jié)點(diǎn)在同一層 (b)i(b)i和和i+1i+1結(jié)點(diǎn)不在同一層結(jié)點(diǎn)不在同一層如圖如圖6.116.11所示為完全二叉樹上結(jié)點(diǎn)及其所示為完全二叉樹上結(jié)點(diǎn)及其左

18、右好在結(jié)點(diǎn)之間的關(guān)系。左右好在結(jié)點(diǎn)之間的關(guān)系。證明：證明： 可以從可以從(2)(2)和和(3)(3)推出推出(1)(1)，先證明，先證明(2)(2)和和(3)(3)。 科學(xué)歸納法：科學(xué)歸納法： 對(duì)于對(duì)于i i1 1，其左孩子是結(jié)點(diǎn)，其左孩子是結(jié)點(diǎn)2 2，若，若2n2n，即不存在，即不存在結(jié)點(diǎn)結(jié)點(diǎn)2 2，此時(shí)，結(jié)點(diǎn)，此時(shí)，結(jié)點(diǎn)i i無(wú)孩子。結(jié)點(diǎn)無(wú)孩子。結(jié)點(diǎn)i i的右孩子是結(jié)點(diǎn)的右孩子是結(jié)點(diǎn)3 3，若結(jié)點(diǎn)若結(jié)點(diǎn)3 3不存在，即不存在，即3n3n，此時(shí)結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)i i無(wú)右孩子。無(wú)右孩子。即即i=1,i=1,結(jié)論成立。結(jié)論成立。 對(duì)于對(duì)于i1i1，可分為兩種情況：，可分為兩種情況： (1)(1)設(shè)

19、第設(shè)第j j層的層的第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的編號(hào)為的編號(hào)為i i，由二叉樹的，由二叉樹的性質(zhì)性質(zhì)2 2和定義知和定義知i i2 2j-1j-1 結(jié)點(diǎn)結(jié)點(diǎn)i i的左孩子的左孩子必定為的必定為的j j1 1層的第一個(gè)結(jié)點(diǎn)，其層的第一個(gè)結(jié)點(diǎn)，其編號(hào)為編號(hào)為2 2j j2 22 2j-1j-12i2i。如果。如果2 2i inn，則無(wú)左孩子。，則無(wú)左孩子。 結(jié)點(diǎn)結(jié)點(diǎn)i i右孩子右孩子必定為第必定為第j j1 1層的第二個(gè)結(jié)點(diǎn)，編號(hào)層的第二個(gè)結(jié)點(diǎn)，編號(hào)為為2i2i1 1。若。若2i+1n2i+1n，則無(wú)右孩子。，則無(wú)右孩子。 (2)(2)假設(shè)第假設(shè)第j j層上的某個(gè)結(jié)點(diǎn)編號(hào)為層上的某個(gè)結(jié)點(diǎn)編號(hào)為i i(2

20、(2j-1j-1=i=2=i=2j j- -1),1),且且2i2i1n11時(shí)，如果時(shí)，如果i為左孩子，即為左孩子，即2(i/2)=i，則，則i/2是是i的雙親；如果的雙親；如果i為右孩子，為右孩子，i2p+1，i的雙親應(yīng)為的雙親應(yīng)為p， p(i1)/2=i/2. 證畢證畢。6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、一、 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)

21、單元存儲(chǔ)根結(jié)點(diǎn)號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;一、一、 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)v順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)l實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素二叉樹中的數(shù)據(jù)元素l特點(diǎn)：特點(diǎn)：u結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中u浪費(fèi)空間，適于存滿二叉樹和完全二叉樹浪費(fèi)空間，適于存滿二叉樹和完全二叉樹 (比如深度為比如深度為k的右單支樹，需要的右單支樹，需要2k-1個(gè)結(jié)點(diǎn)，有效結(jié)點(diǎn)為個(gè)結(jié)點(diǎn)，有效結(jié)點(diǎn)為k)abcdefga b c d e 0 0 0 0 f g 1 2 3

22、 4 5 6 7 8 9 10 11二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):1. 1. 二叉鏈表二叉鏈表v鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)l二叉鏈表二叉鏈表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode , *BiTree;lchild data rchild ABCDEFG性質(zhì)性質(zhì)6：在在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二

23、叉鏈表中，有n+1個(gè)空指針域個(gè)空指針域 AB C D E F GADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):l三叉鏈表三叉鏈表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild, *parent; BiTNode , *BiTree;lchild data parent rchildABCDEFG A B C D E F G0123456B2C0A -1D2E3F4 data parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):3 3雙親鏈表雙親鏈表LRTagL

24、RRRLABCDFE typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BPTree6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線

25、索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 第六章第六章 樹和二叉樹樹和二叉樹6.3.1 遍歷二叉樹遍歷二叉樹問(wèn)題的提出問(wèn)題的提出先序遍歷先序遍歷中序遍歷中序遍歷后序遍歷后序遍歷中序遍歷的非遞歸算法中序遍歷的非遞歸算法遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例6.3.2 線索二叉樹線索二叉樹何謂線索二叉樹？何謂線索二叉樹？線索鏈表的遍歷算法線索鏈表的遍歷算法如何建立線索鏈表如何建立線索鏈表6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷二叉樹是指按遍歷二叉樹是指按一定的規(guī)律一定的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)點(diǎn)均

26、被訪問(wèn)一次均被訪問(wèn)一次，而且，而且僅被訪問(wèn)一次僅被訪問(wèn)一次。 “訪問(wèn)訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息或的含義可以很廣，如：輸出結(jié)點(diǎn)的信息或判定節(jié)點(diǎn)滿足某些條件等。判定節(jié)點(diǎn)滿足某些條件等。“遍歷遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑，只有一條搜索路徑( (因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼) )，故不需要另加討論。而二叉樹是樹型結(jié)構(gòu)，故不需要另加討論。而二叉樹是樹型結(jié)構(gòu)，每個(gè)結(jié)每個(gè)結(jié)點(diǎn)有兩個(gè)后繼點(diǎn)有兩個(gè)后繼，則，則存在如何遍歷存在如何遍歷，即按什么樣的，即按什么樣的搜索搜索路徑路徑遍歷的問(wèn)題。遍歷的問(wèn)題。一、問(wèn)題

27、的提出（一、問(wèn)題的提出（尋找某個(gè)結(jié)點(diǎn)尋找某個(gè)結(jié)點(diǎn)）6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 對(duì)對(duì)“二叉樹二叉樹”而言，可以有三條搜索路徑：而言，可以有三條搜索路徑：1 1先上后下先上后下的按層次遍歷；的按層次遍歷；2 2先左先左（子樹）（子樹）后右后右（子樹）的遍歷；（子樹）的遍歷；3 3先右先右（子樹）（子樹）后左后左（子樹）的遍歷。（子樹）的遍歷。先左后右的遍歷算法先左后右的遍歷算法(左子樹總是先于右子樹左子樹總是先于右子樹)DLRLDR、LRD、DLRRDL、RLD、DRLv方法方法l先序先序(根根)遍歷：遍歷：(1)訪問(wèn)訪問(wèn)根結(jié)點(diǎn)根結(jié)點(diǎn)；(2)先序遍歷左子樹；先序遍歷左子樹

28、；(3)先序遍歷右子樹；先序遍歷右子樹；l中序中序(根根)遍歷：遍歷：(1)中序遍歷左子樹；中序遍歷左子樹；(2)訪問(wèn)訪問(wèn)根結(jié)點(diǎn)根結(jié)點(diǎn)；(3)中序遍歷右子樹；中序遍歷右子樹；l后序后序(根根)遍歷：遍歷：(1)后序遍歷左子樹后序遍歷左子樹; (2)后序遍歷右子樹；后序遍歷右子樹；(3)訪問(wèn)訪問(wèn)根結(jié)點(diǎn)根結(jié)點(diǎn);l按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)ADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷先序遍歷:ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A

29、 C中序遍歷中序遍歷: :ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C A后序遍歷后序遍歷:B-+/a*b-efcd先序遍歷：先序遍歷：中序遍歷：中序遍歷：后序遍歷：后序遍歷：層次遍歷：層次遍歷：- - + + a a * * b b - - c c d d / / e e f f- -+ +a a* *b b- -c cd d/ /e ef f- -+ + a a* *b b- -c cd d/ /e ef f- -+ +a a* *b b- -c c d d/ /e e f f主程序主程序Pre( T )返回返回返回返回返回返回返回返回A

30、CBDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCvisit(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cstatus PreOrderTraversal(BiTree T ) if(T) visit(T-data); PreOrderTraversal(T-lchild); PreOrderTraversal(T-rchild); retu

31、rn OK; v算法：遞歸算法算法：遞歸算法先序遍歷先序遍歷:pre(T R);pre(T R);status InOrderTraversal(BiTree T ) if(T) InOrderTraversal(T-lchild); visit(T-data); InOrderTraversal(T-rchild); return OK; status PostOrderTraversal(BiTree T ) if(T) PostOrderTraversal(T-lchild); PostOrderTraversal(T-rchild); visit(T-data); return OK;

32、 中序遍歷中序遍歷:后序遍歷后序遍歷:l非遞歸算法非遞歸算法(中序中序)ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問(wèn)：訪問(wèn)：C(4)pABCDEFGiP-A訪問(wèn)：訪問(wèn)：C B(5)ABCDEFGiP-AP-D訪問(wèn)：訪問(wèn)：C Bp(6)ABCDEFGiP-AP-DP-E訪問(wèn)：訪問(wèn)：C Bp(7)ABCDEFGiP-AP-D訪問(wèn)：訪問(wèn)：C B Ep(8)ABCDEFGiP-AP-DP-G訪問(wèn)：訪問(wèn)：C B EP=NULL(9)ABCDEFGiP-A訪問(wèn)：訪問(wèn)：C B E G Dp(11)AB

33、CDEFGiP-AP-F訪問(wèn)：訪問(wèn)：C B E G Dp(12)ABCDEFGiP-AP-D訪問(wèn)：訪問(wèn)：C B E Gp(10)ABCDEFGiP-A訪問(wèn)：訪問(wèn)：C B E G D Fp=NULL(13)ABCDEFGi訪問(wèn)：訪問(wèn)：C B E G D F Ap(14)ABCDEFGi訪問(wèn)：訪問(wèn)：C B E G D F Ap=NULL(15)思考：思考：訪問(wèn)的第一個(gè)結(jié)點(diǎn)的特點(diǎn)訪問(wèn)的第一個(gè)結(jié)點(diǎn)的特點(diǎn) 前序，后序棧的操前序，后序棧的操 作作 層次遍歷？層次遍歷？四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述Status InOrderTraverse(BiTree T, Status(*

34、Visit)(TElemType e) InitStack(S); Push(S,T) /根指針進(jìn)棧根指針進(jìn)棧 while (!StackEmpt(S) while(GetTop(S,p)& p) Push(S,p-lchild); Pop(S,p); /空指針退?？罩羔樛藯?if (!StackEmpty(S) Pop(S,p); if(!Visit(p-data) return ERROR; Push(S, p-rchild); /if /while return OK; /InOrderTraverse四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述BiTNode *Go

35、FarLeft(BiTree T,Stack *S) / T為樹根結(jié)點(diǎn)的指針為樹根結(jié)點(diǎn)的指針 if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; /得到樹得到樹T最左葉子結(jié)點(diǎn)的指針最左葉子結(jié)點(diǎn)的指針void InorderTree(BiTree T, void (*visit) (TelemType& e) Stack *S; BiTree t,p; p=T-lchild; t = GoFarLeft(p, S); / / 找到最左下的結(jié)點(diǎn)找到最左下的結(jié)點(diǎn) while(t) visit(

36、t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) /棧不空時(shí)退棧棧不空時(shí)退棧 t = Pop(S); else t = NULL; /?？毡砻鞅闅v結(jié)束?？毡砻鞅闅v結(jié)束 / while / InorderTree 說(shuō)明：說(shuō)明：由一棵給定的二叉樹可以獲得三種遍歷序列，由一棵給定的二叉樹可以獲得三種遍歷序列，同樣，也可以由這些遍歷序列來(lái)重新構(gòu)造二同樣，也可以由這些遍歷序列來(lái)重新構(gòu)造二叉樹。叉樹。單用一個(gè)遍歷序列是無(wú)法構(gòu)造二叉樹的，因單用一個(gè)遍歷序列是無(wú)法構(gòu)造二叉樹的，因?yàn)闊o(wú)法從遍歷序列中區(qū)分二叉樹

37、的左、右子為無(wú)法從遍歷序列中區(qū)分二叉樹的左、右子樹。樹。利用中序遍歷序列，并結(jié)合先序遍歷序列或利用中序遍歷序列，并結(jié)合先序遍歷序列或后序遍歷序列就能重新構(gòu)造二叉樹后序遍歷序列就能重新構(gòu)造二叉樹。 本章實(shí)驗(yàn)內(nèi)容本章實(shí)驗(yàn)內(nèi)容 編寫一個(gè)程序，輸入先序遍歷序列和中序編寫一個(gè)程序，輸入先序遍歷序列和中序遍歷序列遍歷序列 ，由先序遍歷和中序遍歷序列，由先序遍歷和中序遍歷序列構(gòu)造出構(gòu)造出一棵二叉樹一棵二叉樹，然后用，然后用后序遍歷后序遍歷輸出該二叉樹。輸出該二叉樹。先序遍歷序列和中序遍歷序列的結(jié)點(diǎn)分布特點(diǎn)：先序遍歷序列和中序遍歷序列的結(jié)點(diǎn)分布特點(diǎn)：先序遍歷序列：先序遍歷序列： 中序遍歷序列：中序遍歷序列：

38、二叉樹的構(gòu)造步驟：二叉樹的構(gòu)造步驟： 1 1）從先序遍歷序列中取出第一個(gè)結(jié)點(diǎn)從先序遍歷序列中取出第一個(gè)結(jié)點(diǎn)，該結(jié)，該結(jié)點(diǎn)一定是二叉樹的點(diǎn)一定是二叉樹的根根。然后在。然后在中序遍歷序列中序遍歷序列中中找到根結(jié)點(diǎn)，根結(jié)點(diǎn)前面的結(jié)點(diǎn)序列就是找到根結(jié)點(diǎn)，根結(jié)點(diǎn)前面的結(jié)點(diǎn)序列就是左子左子樹樹的中序遍歷序列，根結(jié)點(diǎn)后面的結(jié)點(diǎn)序列就的中序遍歷序列，根結(jié)點(diǎn)后面的結(jié)點(diǎn)序列就是是右子樹右子樹的中序遍歷序列。的中序遍歷序列。 2 2）對(duì)根的左子樹先序遍歷序列和中序遍歷序）對(duì)根的左子樹先序遍歷序列和中序遍歷序列及右子樹的先序遍歷序列和中序遍歷序列，列及右子樹的先序遍歷序列和中序遍歷序列，再再執(zhí)行第一步執(zhí)行第一步，直到

39、得出所有葉子結(jié)點(diǎn)為止。，直到得出所有葉子結(jié)點(diǎn)為止。 a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列main() 輸入先序序列輸入先序序列=preod 輸入中序序列輸入中序序列=inod PreInOd(preod,1,n,inod,1,n,&root);void PreInOd(char preod, int i, int j, char inod, int k,int h,BiTree *t) 申請(qǐng)結(jié)點(diǎn)空間申請(qǐng)結(jié)點(diǎn)空間=t; t-data=preodi; 查找查找t-data在在inod中的位置中的位置=

40、m if (m=k) t-lchild=Null; else PreInOd(preod, i+1,i+m-k,inod,k,m-1,&(t-lchild); /遞歸建立左子樹遞歸建立左子樹 if (m=h) t-rchild=NULL; else PreInOd(preod,i+m-k+1,j inod,m+1,h &(t-rchild);練習(xí) 如圖所示二叉樹的中序遍歷序列是如圖所示二叉樹的中序遍歷序列是（ ）。）。 A AabcdgefabcdgefB Bdfebagcdfebagc C Cdbaefcgdbaefcg D Ddefbagcdefbagc練習(xí)1)已知一棵二叉

41、樹的先根序列為已知一棵二叉樹的先根序列為ABDGCFK，中，中根序列為根序列為DGBAFCK，則結(jié)點(diǎn)的后根序列為，則結(jié)點(diǎn)的后根序列為（ ）。）。 AACFKDBGBGDBFKCACKCFAGDBDABCDFKG 2)已知某二叉樹的后序遍歷序列是已知某二叉樹的后序遍歷序列是dabec，中，中序遍歷序列是序遍歷序列是debac，它的前序遍歷序列是，它的前序遍歷序列是（ ）。）。AacbedBdecab CdeabcDcedba利用中序遍歷序列，并結(jié)合先序遍歷序列或后利用中序遍歷序列，并結(jié)合先序遍歷序列或后序遍歷序列重新構(gòu)造二叉樹。序遍歷序列重新構(gòu)造二叉樹。 例一例一 先序：先序：ABCDEFGHI

42、J 中序：中序：CBDEAFHIGJ 例二例二 中序：中序：ABCDJEFHGI 后序：后序：BCJDAHIGFE 練習(xí)練習(xí)五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例2 2、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)( (先序遍歷先序遍歷) )3 3、求二叉樹的深度、求二叉樹的深度( (后序遍歷后序遍歷) )1 1、按先序遍歷序列建立二叉樹的二叉鏈表、按先序遍歷序列建立二叉樹的二叉鏈表 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如例如: :ABCD以空白字符以空白字符“ ”“ ”表示表示A(B( ,C( , ),D( , )空樹空樹

43、只含一個(gè)根結(jié)點(diǎn)只含一個(gè)根結(jié)點(diǎn)的二叉樹的二叉樹A以字符串以字符串“A ” ”表示表示以下列字符串表示以下列字符串表示遍歷算法應(yīng)用遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ABCDEFG A B C D E F G status CreateBitree(BiTree&T) scanf(&ch); if(ch= |ch=n) T=NULL; else if(!(T=(BiTnode*)malloc(sizeof(BiTnode) exit(overflow); T-data=ch

44、; CreateBitree(T-lchild); CreateBitree(T-rchild); return OK; A B C D A BCD上頁(yè)算法執(zhí)行過(guò)程舉例如下：上頁(yè)算法執(zhí)行過(guò)程舉例如下：ATBCD2 2、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹，在遍歷遍歷二叉樹，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。需在遍歷算法中增添一個(gè)需在遍歷算法中增添一個(gè)“計(jì)數(shù)計(jì)數(shù)”的參數(shù)，的參數(shù)，并將算法中并將算法中“訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn)”的操作改為：若是的操作改為：若是葉子，則計(jì)數(shù)器增

45、葉子，則計(jì)數(shù)器增1 1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法ABCDEFGint BitreeLeafCount(BiTree T) if (T=NULL) return 0; else if (T-lchild=N

46、ULL &T-rchild=NULL) return 1; else return BitreeLeafCount(T-lchild)+ BitreeLeafCount(T-rchild); ABCDEFGl統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)算法統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)算法int BitreeCount(BiTree T) if (T=NULL) return 0; else return BitreeCount(T-lchild)+ BitreeCount(T-rchild)+ 1; l求二叉樹深度算法求二叉樹深度算法int BitreeDepth(BiTree T) if (T=NULL) dept

47、h=0; else ldepth=BitreeDepth(T-lchild); rdepth=BitreeDepth(T-rchild); depth=1+(ldepthrdepth?ldepth:rdepth); return depth; ABCDEFG線索二叉樹線索二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線線性序列性序列。ABCDEFGHK例如例如: :先序序列先序序列: : A B C D E F G H

48、 K中序序列中序序列: : B D C A H G K F E后序序列后序序列: : D C B H K G F E A指向該線性序列中的指向該線性序列中的“前驅(qū)前驅(qū)”和和 “后繼后繼” 的指針，稱作的指針，稱作“線索線索”與其相應(yīng)的二叉樹，稱與其相應(yīng)的二叉樹，稱作作 “線索二叉樹線索二叉樹”包含包含 “線索線索” 的存儲(chǔ)結(jié)構(gòu)，的存儲(chǔ)結(jié)構(gòu)，稱作稱作 “線索鏈表線索鏈表”A B C D E F G H K D C B E 對(duì)對(duì)線索鏈表線索鏈表中結(jié)點(diǎn)的約定：中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域增加兩個(gè)標(biāo)志域：若該結(jié)點(diǎn)的左子樹不空，若該結(jié)點(diǎn)的左子樹不空，則則Lchild

49、域的指針指向其左子樹，且左標(biāo)志域的指針指向其左子樹，且左標(biāo)志域的值為域的值為“指針指針 Link”； 否則，否則，Lchild域的指針指向其域的指針指向其“前驅(qū)前驅(qū)”，且，且左標(biāo)志的值為左標(biāo)志的值為“線索線索 Thread” . lchild Ltag data Rtag rchild 若該結(jié)點(diǎn)的右子樹不空，若該結(jié)點(diǎn)的右子樹不空，則則rchild域的指針指向其右子樹，且右標(biāo)志域域的指針指向其右子樹，且右標(biāo)志域的值為的值為 “指針指針 Link”；否則，否則，rchild域的指針指向其域的指針指向其“后繼后繼”，且右，且右標(biāo)志的值為標(biāo)志的值為“線索線索 Thread”。 如此定義的二叉樹的存儲(chǔ)結(jié)

50、構(gòu)稱作如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈線索鏈表表”。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針左右指針 PointerThr LTag, RTag; / 左右標(biāo)志左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表線索鏈表的類型描述：的類型描述： typedef enum PointerTag Link, Thread ; / Link=0:指針，指針，Thread=1:線索線索 lchild Ltag data Rtag rchild ABCDE A B D

51、 C ET00001111 11typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; PointTag Ltag , Rtag; BiThrNode ,*BiThrTree; lchild Ltag data Rtag rchild 結(jié)點(diǎn)定義：結(jié)點(diǎn)定義：Typedef enum PointerTag Link, Thread ;先序序列：先序序列：ABCDE先序線索二叉樹先序線索二叉樹ABCDE A B D C ET0000111111中序序列：中序序列：BCAED中序線索二叉樹中序線索二叉樹AB

52、CDE A B D C ET0000111111后序序列：后序序列：CBEDA后序線索二叉樹后序線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法 for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在線索鏈表中添加了遍歷中得到的由于在線索鏈表中添加了遍歷中得到的“前前驅(qū)驅(qū)”和和“后繼后繼”的信息，從而簡(jiǎn)化了遍歷的的信息，從而簡(jiǎn)化了遍歷的算法。算法。例如例如: 對(duì)中序線索化鏈表的遍歷算法對(duì)中序線索化鏈表的遍歷算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？ 在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？左子樹上處于左子樹

53、上處于“最左下最左下”（沒有左子樹）的（沒有左子樹）的結(jié)點(diǎn)。結(jié)點(diǎn)。若若無(wú)右子樹，無(wú)右子樹，則為則為后繼線索所指結(jié)點(diǎn)；后繼線索所指結(jié)點(diǎn)；否則為否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問(wèn)對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)。的第一個(gè)結(jié)點(diǎn)。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結(jié)點(diǎn)指向根結(jié)點(diǎn) while (p != T) / 空樹或遍歷結(jié)束時(shí)，空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=Link) p = p-lchild; / 第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn) while

54、(p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問(wèn)后繼結(jié)點(diǎn)訪問(wèn)后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根進(jìn)至其右子樹根 / InOrderTraverse_Thr在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問(wèn)結(jié)點(diǎn)的針域，以保存當(dāng)前訪問(wèn)結(jié)點(diǎn)的“前驅(qū)前驅(qū)”和和“后繼后繼”信息。信息。遍歷過(guò)程中，附設(shè)指針遍歷過(guò)程中，附設(shè)指針pre, 并始終保持并始終保持指針指針pre指向當(dāng)前訪問(wèn)的、指針指向當(dāng)前訪問(wèn)的、指針p所指結(jié)點(diǎn)所指結(jié)點(diǎn)的的前驅(qū)前驅(qū)。三、如何建立線索鏈表？

55、三、如何建立線索鏈表？void InThreading(BiThrTree p) if (p) / 對(duì)以對(duì)以p為根的非空二叉樹進(jìn)行線索化為根的非空二叉樹進(jìn)行線索化 InThreading(p-lchild); / 左子樹線索化左子樹線索化 if (!p-lchild) / 建前驅(qū)線索建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持保持 pre 指向指向 p 的前驅(qū)的前驅(qū) InThreading(p-rchild

56、); / 右子樹線索化右子樹線索化 / if / InThreadingStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 構(gòu)建中序線索鏈表構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加頭結(jié)點(diǎn)添加頭結(jié)點(diǎn) return OK; / InOrderThreading if (!T) Thrt-lchild

57、 = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個(gè)結(jié)點(diǎn)處理最后一個(gè)結(jié)點(diǎn) pre-RTag = Thread; Thrt-rchild = pre; 6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 第六章第六章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林 6.4.1 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu) 6.4.2

58、 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 6.4.3 樹和森林的遍歷樹和森林的遍歷6.4.1 樹的三種存儲(chǔ)結(jié)構(gòu)樹的三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法一、雙親表示法二、孩子鏈表表示法二、孩子鏈表表示法三、樹的二叉鏈表三、樹的二叉鏈表(孩子孩子-兄弟）存儲(chǔ)表示法兄弟）存儲(chǔ)表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=6data parent一、雙親表示法一、雙親表示法 typedef struct PTNode Elem data; int parent; / 雙親位置域雙親位置域 PTNode; data parent#define MAX_TRE

59、E_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述語(yǔ)言的類型描述:typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):abcdefhgi6012345789acdefghibdata fc 2 3 4 5 9 7 8 6如何找雙親結(jié)點(diǎn)如何找雙親結(jié)點(diǎn)l孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)單鏈表存儲(chǔ)，再，再用含用含n n個(gè)元素的個(gè)元素的結(jié)構(gòu)數(shù)組結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表指向每個(gè)孩子鏈表二、孩子鏈表表示法二、孩子鏈表表示法l帶雙親的孩子

60、鏈表帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgitypedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): child nextC C語(yǔ)言的類型描述語(yǔ)言的類型描述: : typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹結(jié)構(gòu)樹結(jié)構(gòu):三、孩子兄弟表示法三、孩子兄弟表示法(二叉樹表示法二叉樹表示法)l實(shí)現(xiàn)：用二叉