數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Six Tree

1、數(shù)據(jù)結(jié)構(gòu)Chapter Six Tree1、樹和森林的概念n概念n二叉樹 (Binary Tree)n二叉樹的表示n二叉樹遍歷 (Binary Tree Traversal)n線索化二叉樹 (Threaded Binary Tree)n堆 ( Heap )n樹與森林 (Tree & Forest)n二叉樹的計(jì)數(shù)n霍夫曼樹 (Huffman Tree)1、樹和森林的概念樹的定義 樹是由n (n 0)個(gè)結(jié)點(diǎn)組成的有限集合。如果n = 0，稱為空樹；如果n 0，則 有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)； 除根以外的其它結(jié)點(diǎn)劃分為m (m 0)個(gè)互不相交的有限集合T0

2、, T1, , Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。1、樹和森林的概念樹的特點(diǎn) (1) 樹的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。(2) 樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。1、樹和森林的概念n結(jié)點(diǎn)(node)n結(jié)點(diǎn)的度(degree)n分支(branch)結(jié)點(diǎn)n葉(leaf)結(jié)點(diǎn)n子女(child)結(jié)點(diǎn)n雙親(parent)結(jié)點(diǎn)n兄弟(sibling)結(jié)點(diǎn)n祖先(ancestor)結(jié)點(diǎn)n子孫(descendant)結(jié)點(diǎn)n結(jié)點(diǎn)所處層次(level)n樹的高度/深度(de

3、pth)n樹的度(degree)n有序樹n無(wú)序樹n森林1、樹和森林的概念樹的定義還可形式化的描述為二元組的形式： T(D，R)其中：D為樹T中結(jié)點(diǎn)的集合，R為樹中結(jié)點(diǎn)之間關(guān)系的集合。當(dāng)樹為空樹時(shí)，D；當(dāng)樹T不為空樹時(shí)有： DRootDF其中，Root為樹T的根結(jié)點(diǎn)，DF為樹T的根Root的子樹集合。DF可由下式表示： DFD1D2Dm且且DiDj(ij，1im，1jm)當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n1時(shí)，R；當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n1時(shí)有：R，i1，2，m。其中，Root為樹T的根結(jié)點(diǎn)，ri是樹T的根結(jié)點(diǎn)Root的子樹Ti的根結(jié)點(diǎn)。1、樹和森林的概念線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū)) 根結(jié)點(diǎn) (無(wú)前驅(qū))

4、最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼)多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、 一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、 多個(gè)后繼)n 樹和線性結(jié)構(gòu)的對(duì)比2、二叉樹 (Binary Tree)n2.1、二叉樹概念n2.2、二叉樹的表示n2.3、二叉樹遍歷 (Binary Tree Traversal)n2.4、線索化二叉樹 (Threaded Binary Tree)n2.5、堆 ( Heap )n2.6、樹與森林 (Tree & Forest)n2.7、二叉樹的計(jì)數(shù)n2.8、霍夫曼樹 (Huffman Tree)2.1、二叉樹概念n 定義 一棵二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空，或者是由一個(gè)根結(jié)

5、點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EF2.1、二叉樹概念n 5種形態(tài)2.1、二叉樹概念n N個(gè)節(jié)點(diǎn)有多少種形態(tài)？2.1、二叉樹概念n N個(gè)節(jié)點(diǎn)有多少種形態(tài)？NNCN2*)1/(1 (2.1、二叉樹概念n兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。2.1、二叉樹概念n兩類特殊的二叉樹：完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。2.1、二叉樹概念n特殊二叉樹的練習(xí)：在一棵深度為K的滿二叉樹的總節(jié)點(diǎn)數(shù)目_。在一棵深度為K的完全二叉樹的節(jié)點(diǎn)總數(shù)：最小為為_ ；最大為_ 。2k

6、-1 2k-1 2k-12.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1 個(gè)結(jié)點(diǎn)。(i 1) 證明用數(shù)學(xué)歸納法性質(zhì)2 高度為k的二叉樹最多有 2k-1個(gè)結(jié)點(diǎn)。(k 1) 證明用求等比級(jí)數(shù)前k項(xiàng)和的公式2.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)3 對(duì)任何一棵二叉樹, 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2, 則有 n0n21。證明：若設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有 2n2 + n1 = n0 + n1 +

7、 n2 - 1 n2 = n0 - 1 n0 = n2 + 1 2.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)3 練習(xí)在一棵二叉樹中，假定度為2的結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，度為1結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，則葉結(jié)點(diǎn)數(shù)為_個(gè)。在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有_個(gè)。 5*2+6*1+1-(5+6) =62*3+1*2+2*1+1-(2+1+2) =62.1、二叉樹概念n二叉樹的性質(zhì)性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 log2(n) +1證明：設(shè)完全二叉樹的高度為h，則有 2h-1 - 1 n 2h- 1 2h-1 n 2h 取對(duì)數(shù) h -1 log2(n

8、) 1, 則 i 的雙親為i /2n 若2*i= n, 則 i 的左子女為2*i 若2* i +1data=x) return bt; /*查找成功返回*/*在bt-lchild為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-lchild!=NULL) return(Search(bt-lchild,x); /*在bt-rchild為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x*/ if (bt-rchild!=NULL) return(Search(bt-rchild,x); return NULL; /*查找失敗返回*/3、二叉樹遍歷的應(yīng)用n統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)的數(shù)目(BinaryTree.c

9、pp)/*開始時(shí)，bt為根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針，返回值為bt的葉子數(shù)*/int CountLeaf2(BiTree bt) if (bt=NULL) return(0); if (bt-lchild=NULL & bt-rchild=NULL) return(1); return( CountLeaf2(bt-lchild) + CountLeaf2(bt-rchild) );3、二叉樹遍歷的應(yīng)用n統(tǒng)計(jì)二叉樹深度int Depth (BinaryTree bt ) / 返回二叉樹的深度 int depthval,depthLeft, depthRight; if ( bt = NULL ) d

10、epthval = 0; else depthLeft = Depth( bt-lchild ); depthRight= Depth( bt-rchild ); depthval =1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;3、二叉樹遍歷的應(yīng)用n表達(dá)式樣求解 求解 3x2+x-1/x+5 ？ 前綴表達(dá)式 +-+*3*xxx/1x5 后綴表達(dá)式 3xx*x+1x/-5+ 中綴表達(dá)式 3*x*x+x-1/x+5 前綴表達(dá)式和后綴表達(dá)式分別稱為波蘭式和逆波蘭式，它們?cè)诰幾g程序中有著非常重要的作用4、線索

11、二叉樹n引二叉樹遍歷可以通過(guò)遞歸或堆棧實(shí)現(xiàn)，究其原因可以發(fā)現(xiàn)是因?yàn)槎鏄涞逆準(zhǔn)菃蜗虻?。如果，不用堆棧?lái)實(shí)現(xiàn)遍歷，可以有如下方法： 三叉表結(jié)構(gòu) 二叉表結(jié)構(gòu)+“倒鏈”操作 線索二叉樹4、線索二叉樹n結(jié)構(gòu)一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉鏈表存儲(chǔ)結(jié)構(gòu)，在2n個(gè)指針域中只有n1個(gè)指針域是用來(lái)存儲(chǔ)結(jié)點(diǎn)孩子的地址，而另外n1個(gè)指針域存放的都是NULL。 可利用這些空指針域來(lái)指示結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索(thread)，加了線索的二叉樹稱為線索二叉樹 。4、線索二叉樹n結(jié)構(gòu)定義LeftThread = 0, LeftChild為左子女指針為

12、左子女指針LeftThread = 1, LeftChild為前驅(qū)線索為前驅(qū)線索RightThread = 0, RightChild為右子女指針為右子女指針RightThread = 1, RighrChild為后繼指針為后繼指針教材：ltag LeftThreadrtagRightThread4、線索二叉樹n結(jié)構(gòu)圖示4、線索二叉樹n帶頭節(jié)點(diǎn)的結(jié)構(gòu)圖示去除2個(gè)空置點(diǎn)，設(shè)置頭節(jié)點(diǎn)。4、線索二叉樹n另一種結(jié)構(gòu)定義增加Pred指針和Succ指針的二叉樹。4、線索二叉樹n數(shù)據(jù)結(jié)構(gòu)typedef char datatype;typedef struct BiThrNode datatype data;

13、 struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag:1; unsigned rtag:1; BiThrNodeType,*BiThrTree;4、線索二叉樹n基本操作(1) 建立一棵中序線索二叉樹(2) 在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)(3) 在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)(4) 在中序線索二叉樹上查找任意結(jié)點(diǎn)在先序下的后繼(5) 在中序線索二叉樹上查找任意結(jié)點(diǎn)在后序下的前驅(qū)(6) 在中序線索二叉樹上查找值為x的結(jié)點(diǎn)(7) 在中序線索二叉樹上的插入(8) 在中序線索二叉樹上的刪除4、線索

14、二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(1) 建立一棵中序線索二叉樹建立線索二叉樹，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過(guò)程中，訪問(wèn)結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過(guò)程，設(shè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(2)在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)如果該結(jié)點(diǎn)的左標(biāo)志為1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；如果該結(jié)點(diǎn)的左標(biāo)志為0，表明該結(jié)點(diǎn)有左孩子 ,它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子

15、為根結(jié)點(diǎn)的子樹的最右結(jié)點(diǎn)：while (pre-rtag=0) pre=pre-rchild;4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(3) 在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn) 如果該結(jié)點(diǎn)的右標(biāo)志為1，那么其右指針域所指向的結(jié)點(diǎn) 便是它的后繼結(jié)點(diǎn)；如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié) 點(diǎn)有右孩子，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn) 的子樹的最左結(jié)點(diǎn) : while (post-rtag=0) post=post-lchild;4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(4) 在中序線索二叉樹上查找任意結(jié)點(diǎn)在先序下的后繼若一個(gè)結(jié)點(diǎn)是某子樹在中序下的最后一個(gè)

16、結(jié)點(diǎn)，則它必是該子樹在先序下的最后一個(gè)結(jié)點(diǎn)4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(5) 在中序線索二叉樹上查找任意結(jié)點(diǎn)在后序下的前驅(qū)若一個(gè)結(jié)點(diǎn)是某子樹在中序下的第一個(gè)結(jié)點(diǎn)，則它必是該子樹在后序下的第一個(gè)結(jié)點(diǎn)。4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(6) 在中序線索二叉樹上查找值為x的結(jié)點(diǎn)利用在中序線索二叉樹上尋找后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹的所有結(jié)點(diǎn)4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(7) 在中序線索二叉樹上的插入4、線索二叉樹n操作實(shí)現(xiàn) (BiThrTree.cpp)(8) 在中序線索二叉樹上的刪除5、霍夫曼樹 (Hu

17、ffman Tree)n定義哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹。 路徑長(zhǎng)度 (Path Length)：兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹的路徑長(zhǎng)度是各結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度之和。5、霍夫曼樹 (Huffman Tree)n圖示具有不同路徑長(zhǎng)度的二叉樹5、霍夫曼樹 (Huffman Tree)n路徑最小值n個(gè)結(jié)點(diǎn)的二叉樹的路徑長(zhǎng)度不小于下述數(shù)列前n項(xiàng)的和，即：其路徑長(zhǎng)度最小為：1021)(logniiPL1021)(logniiPL3322221105、霍夫曼樹 (Huffman Tree)n帶權(quán)

18、路徑長(zhǎng)度 ( Weighted Path Length, WPL )樹的帶權(quán)路徑長(zhǎng)度是樹的各葉結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長(zhǎng)度的乘積的和。10niiilwWPL27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 545、霍夫曼樹 (Huffman Tree)帶權(quán)路徑長(zhǎng)度達(dá)到最小的擴(kuò)充二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。如何構(gòu)造霍夫曼樹 ？5、霍夫曼樹 (Huffman Tree)n算法(1) 由給定的n個(gè)權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有n棵擴(kuò)充二叉樹的森林F = T0, T1,

19、T2, , Tn-1，其中每一棵擴(kuò)充二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空。(2) 重復(fù)以下步驟, 直到F中僅剩下一棵樹為止： 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。 在F中刪去這兩棵二叉樹。 把新的二叉樹加入F。5、霍夫曼樹 (Huffman Tree)n算法圖示9例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 56275276976713952767139527952716671329000011110001111001015、霍夫曼樹 (Huffman Tree)

20、n算法實(shí)現(xiàn)：設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹最多2n1個(gè)結(jié)點(diǎn)。weight域保存結(jié)點(diǎn)的權(quán)值，lchild和rchild域分別保存該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)。5、霍夫曼樹 (Huffman Tree)n算法應(yīng)用：主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報(bào)文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 。 若給每個(gè)字符以等長(zhǎng)編碼 A : 00 T : 10 C : 01 S : 11則總編碼長(zhǎng)度為 ( 2

21、+7+4+5 ) * 2 = 36. 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。 因各字符出現(xiàn)的概率為 2/18, 7/18, 4/18, 5/18 。5、霍夫曼樹 (Huffman Tree)n算法應(yīng)用：化整為 2, 7, 4, 5 ，以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立霍夫曼樹。左分支賦 0，右分支賦 1，得霍夫曼編碼(變長(zhǎng)編碼)。 A : 0 T : 10 C : 110 S : 111它的總編碼長(zhǎng)度：7*1+5*2+( 2+4 )*3 = 35。比等長(zhǎng)編碼的情形要短。 總編碼長(zhǎng)度正好等于霍夫曼樹的帶權(quán)路徑長(zhǎng)度WPL。 霍夫曼編碼是一種無(wú)前綴編碼。解碼時(shí)不會(huì)混淆。6、樹n

22、樹的4種表示方法(1) 直觀表示法(2) 嵌套集合表示法(3) 凹入表示法(4) 廣義表表示法6、樹n樹的4種表示方法(1) 直觀表示法:倒著的分支樹的形式表示 6、樹n樹的4種表示方法(2) 嵌套集合表示法：根結(jié)點(diǎn)視為一個(gè)大的集合，其若干棵子樹構(gòu)成這個(gè)大集合中若干個(gè)互不相交的子集，如此嵌套下去，即構(gòu)成一棵樹的嵌套集合表示6、樹n樹的4種表示方法(3) 凹入表示法：主要用于樹的屏幕和打印輸出 。6、樹n樹的4種表示方法(4) 廣義表表示法：將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將書表示出來(lái)。(A,(B(D,E(H,I),F),C(G) 6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(1) 雙親表示法

23、(2) 孩子表示法(3) 雙親孩子表示法(4) 孩子兄弟表示法6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(1) 雙親表示法定義：由樹的定義可知：樹中的每個(gè)結(jié)點(diǎn)都有唯一的一個(gè)雙親結(jié)點(diǎn)，根據(jù)這一特性，可用一組連續(xù)的存儲(chǔ)空間（一維數(shù)組）存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)，數(shù)組中的一個(gè)元素表示樹中的一個(gè)結(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息以及結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(1) 雙親表示法圖示：6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(1) 雙親表示法數(shù)據(jù)結(jié)構(gòu)： #define MAXNODE typedef struct datatype data; int parent; NodeType; NodeType

24、tMAXNODE;6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法令每個(gè)結(jié)點(diǎn)包括一個(gè)結(jié)點(diǎn)信息域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)，通過(guò)各個(gè)指針域值反映出樹中各結(jié)點(diǎn)之間的邏輯關(guān)系。在這種表示法中，樹中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，形成了多條鏈表，所以這種方法又常稱為多重鏈表法。每個(gè)結(jié)點(diǎn)的度數(shù)各異,只有兩種可能性：每一個(gè)都單獨(dú)設(shè)置(不現(xiàn)實(shí))；或取最大度數(shù)(樹的度)，但空間浪費(fèi)。6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法圖示6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：多重鏈表方法數(shù)據(jù)結(jié)構(gòu) #define MAXSON typedef struct TreeNode ele

25、mtype data; struct TreeNode *sonMAXSON; NodeType;6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：孩子鏈表方法其主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個(gè)元素有兩個(gè)域組成，一個(gè)域用來(lái)存放結(jié)點(diǎn)信息，另一個(gè)用來(lái)存放指針，該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個(gè)域組成，一個(gè)存放孩子結(jié)點(diǎn)在一維數(shù)組中的序號(hào)，另一個(gè)是指針域，指向下一個(gè)孩子。6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：孩子鏈表圖示6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(2) 孩子表示法：孩子鏈表數(shù)據(jù)結(jié)構(gòu) #define MAXNODE typedef struct Child

26、Node int childcode; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; NodeType tMAXNODE;6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(3) 雙親孩子鏈表方法 雙親表示法是將雙親表示法和孩子表示法相結(jié)合的結(jié)果。其仍將各結(jié)點(diǎn)的孩子結(jié)點(diǎn)分別組成單鏈表，同時(shí)用一維數(shù)組順序存儲(chǔ)樹中的各結(jié)點(diǎn)，數(shù)組元素除了包括結(jié)點(diǎn)本身的信息和該結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈表的頭指針之外，還增設(shè)一個(gè)域，存儲(chǔ)該結(jié)點(diǎn)雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)。6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(3) 雙親孩

27、子鏈表圖示6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(3) 雙親孩子鏈表數(shù)據(jù)結(jié)構(gòu) #define MAXNODE typedef struct ChildNode int childcode,parent; struct ChildNode *nextchild; typedef struct elemtype data; struct ChildNode *firstchild; NodeType; NodeType tMAXNODE;6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(4)孩子兄弟鏈表方法在樹中，每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)的指針。6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(4)孩子兄

28、弟鏈表圖示6、樹n樹的4種存儲(chǔ)結(jié)構(gòu)(4)孩子兄弟鏈表數(shù)據(jù)結(jié)構(gòu) typedef struct TreeNode elemtype data; struct TreeNode *son; struct TreeNode *next; NodeType;7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹1：樹中所有相鄰兄弟之間加一條連線。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹2：樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹3：以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之結(jié)構(gòu)層次分明。7、樹、森林與二叉樹的轉(zhuǎn)換n樹轉(zhuǎn)換為二叉樹分析1： 可以證明，樹