




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、Data Structure計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第第6 6章章 樹與二叉樹樹與二叉樹樹的定義和基本術(shù)語(yǔ)樹的定義和基本術(shù)語(yǔ)二叉樹二叉樹遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹樹和森林樹和森林HuffmanHuffman樹及其應(yīng)用樹及其應(yīng)用小結(jié)與練習(xí)小結(jié)與練習(xí)1. 1. 掌握二叉樹的基本概念、掌握二叉樹的基本概念、性質(zhì)性質(zhì)和存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)2. 2. 熟練掌握二叉樹的熟練掌握二叉樹的前、中、后序遍歷方法前、中、后序遍歷方法3. 3. 了解了解線索化線索化二叉樹的思想二叉樹的思想4. 4. 熟練掌握熟練掌握霍夫曼樹霍夫曼樹的實(shí)現(xiàn)方法、構(gòu)造的實(shí)現(xiàn)方法、構(gòu)造霍夫曼編碼霍夫曼編碼的方法的方法5. 5
2、. 掌握森林與二叉樹的轉(zhuǎn)換,樹的遍歷方法掌握森林與二叉樹的轉(zhuǎn)換,樹的遍歷方法教學(xué)目標(biāo)教學(xué)目標(biāo)6.1樹的定義和基本術(shù)語(yǔ)樹的定義和基本術(shù)語(yǔ) 1、定義、定義定義:樹定義:樹(tree)是是n(n0)個(gè)結(jié)點(diǎn)的有限集個(gè)結(jié)點(diǎn)的有限集T,其中:其中:有且僅有一個(gè)特定的結(jié)點(diǎn),稱為樹的根有且僅有一個(gè)特定的結(jié)點(diǎn),稱為樹的根(root)當(dāng)當(dāng)n1時(shí),其余結(jié)點(diǎn)可分為時(shí),其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有個(gè)互不相交的有限集限集T1,T2,Tm,其中每一個(gè)集合本身又是一棵其中每一個(gè)集合本身又是一棵樹,稱為根的子樹樹,稱為根的子樹(subtree)特點(diǎn):特點(diǎn):樹中有且僅有一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)(根樹中有且僅有一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)(根R
3、oot);可有多個(gè)結(jié)點(diǎn)沒有后繼(葉子可有多個(gè)結(jié)點(diǎn)沒有后繼(葉子leaf)其余結(jié)點(diǎn)僅有一個(gè)前驅(qū),可有多個(gè)后繼其余結(jié)點(diǎn)僅有一個(gè)前驅(qū),可有多個(gè)后繼A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹 2 2、基本術(shù)語(yǔ)基本術(shù)語(yǔ)結(jié)點(diǎn)結(jié)點(diǎn)(node)(node)表示樹中的元素,包括數(shù)據(jù)項(xiàng)及若干表示樹中的元素,包括數(shù)據(jù)項(xiàng)及若干 指向其子樹的分支。指向其子樹的分支。孩子孩子(child)(child)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子( ( 結(jié)點(diǎn)的直接后繼)結(jié)點(diǎn)的直接后繼)雙親雙親(parents)(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙孩
4、子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙 親(結(jié)點(diǎn)的直接前驅(qū))親(結(jié)點(diǎn)的直接前驅(qū))兄弟兄弟(sibling)(sibling)同一雙親的孩子同一雙親的孩子祖先祖先、子孫子孫、堂兄弟堂兄弟7結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)(degree)結(jié)點(diǎn)擁有的子樹數(shù)結(jié)點(diǎn)擁有的子樹數(shù)樹的度樹的度一棵樹中最大的結(jié)點(diǎn)度數(shù)一棵樹中最大的結(jié)點(diǎn)度數(shù)樹的深度樹的深度(depth)(depth)樹中結(jié)點(diǎn)的最大層數(shù)樹中結(jié)點(diǎn)的最大層數(shù)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)(level)從根結(jié)點(diǎn)算起,根為第一層,從根結(jié)點(diǎn)算起,根為第一層, 它的孩子為第二層它的孩子為第二層森林森林(forest)(forest)m(mm(m0)0)棵互不相交的樹
5、的集合棵互不相交的樹的集合ABCDEFGHIJKLM結(jié)點(diǎn)結(jié)點(diǎn)A A的度:的度:3 3結(jié)點(diǎn)結(jié)點(diǎn)B B的度:的度:2 2結(jié)點(diǎn)結(jié)點(diǎn)M M的度:的度:0 0葉子:葉子:K K,L L,F(xiàn) F,G G,M M,I I,J J結(jié)點(diǎn)結(jié)點(diǎn)A A的孩子:的孩子:B B,C C,D D結(jié)點(diǎn)結(jié)點(diǎn)I I和和L L的雙親:的雙親:D D、 E E結(jié)點(diǎn)結(jié)點(diǎn)B B,C C,D D為兄弟為兄弟結(jié)點(diǎn)結(jié)點(diǎn)K K,L L為兄弟為兄弟樹的度:樹的度:3 3結(jié)點(diǎn)結(jié)點(diǎn)A A的層次:的層次:1 1結(jié)點(diǎn)結(jié)點(diǎn)M M的層次:的層次:4 4樹的深度:樹的深度:4 4結(jié)點(diǎn)結(jié)點(diǎn)F F,G G為堂兄弟為堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)A A是結(jié)點(diǎn)是結(jié)點(diǎn)F F,G G的祖
6、先的祖先返回返回6.26.2 二叉樹二叉樹 1 1、二叉樹的定義、二叉樹的定義 二叉樹(二叉樹(Binary TreeBinary Tree)是)是n(nn(n0)0)個(gè)結(jié)點(diǎn)的有限個(gè)結(jié)點(diǎn)的有限集,它或?yàn)榭諛浼?,它或?yàn)榭諛? (n=0)n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。為左子樹和右子樹的互不相交的二叉樹構(gòu)成。 特點(diǎn)特點(diǎn)每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹至多有二棵子樹( (結(jié)點(diǎn)度可能是結(jié)點(diǎn)度可能是0 0、1 1、2)2)二叉樹的子樹有二叉樹的子樹有左、右之分左、右之分,其次序不能任意顛倒,其次序不能任意顛倒二叉樹的基本形態(tài)二叉樹的基本
7、形態(tài)右子樹為空右子樹為空左子樹為空左子樹為空左、右子樹左、右子樹均非空均非空只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)的二叉樹的二叉樹空二叉樹空二叉樹 普通樹(多叉樹)若不轉(zhuǎn)化為二叉樹,運(yùn)算普通樹(多叉樹)若不轉(zhuǎn)化為二叉樹,運(yùn)算很難實(shí)現(xiàn)很難實(shí)現(xiàn)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “叉叉” 的樹的樹? 二叉樹的結(jié)構(gòu)最簡(jiǎn)單,規(guī)律性最強(qiáng);二叉樹的結(jié)構(gòu)最簡(jiǎn)單,規(guī)律性最強(qiáng); 可以證明,所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹可以證明,所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹,不失一般性。,不失一般性。 練習(xí)練習(xí)5 5種種/2/2種種2 2、二叉樹性質(zhì)二叉樹性質(zhì)(用歸納法證明)(用歸納法證明)性質(zhì)性質(zhì)1 1:在二叉樹
8、的第:在二叉樹的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)(個(gè)結(jié)點(diǎn)(i i1 1)。)。證明:證明:a.a.當(dāng)當(dāng)i = 1i = 1時(shí),時(shí),2 20 0 = 1= 1,只有一個(gè)根結(jié)點(diǎn),正確。,只有一個(gè)根結(jié)點(diǎn),正確。 b.b.假設(shè)對(duì)所有的假設(shè)對(duì)所有的j j,1 1 j j i i,命題成立,即,命題成立,即 第第j j層上至多有層上至多有2 2j j個(gè)結(jié)點(diǎn)。下面證明當(dāng)就個(gè)結(jié)點(diǎn)。下面證明當(dāng)就j = ij = i時(shí)時(shí)結(jié)結(jié) 論也成立。論也成立。c.c.由歸納假設(shè),第由歸納假設(shè),第i - 1i - 1層上最多有層上最多有2 2i - 2i - 2個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度數(shù)最大為由
9、于二叉樹每個(gè)結(jié)點(diǎn)的度數(shù)最大為2 2,所以第,所以第i i層層上的最大結(jié)點(diǎn)數(shù)為第上的最大結(jié)點(diǎn)數(shù)為第i - 1i - 1層上的最大結(jié)點(diǎn)數(shù)的層上的最大結(jié)點(diǎn)數(shù)的2 2倍,即倍,即2 2i-1i-1個(gè)。個(gè)。提問:第提問:第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)?個(gè)結(jié)點(diǎn)?114性質(zhì)性質(zhì)2 深度為深度為k的二叉樹至多有的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)證明:由性質(zhì)證明:由性質(zhì)1可知,第可知,第i層的最大結(jié)點(diǎn)數(shù)為層的最大結(jié)點(diǎn)數(shù)為2i-1,所以所以,深度為深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為的二叉樹的最大結(jié)點(diǎn)數(shù)為i=1k2i-1= 2k-1提問:深度為提問:深度為k k時(shí)至少有時(shí)至少有 個(gè)結(jié)點(diǎn)?個(gè)結(jié)點(diǎn)?k15性質(zhì)
10、性質(zhì)3 3 任何一棵二叉樹任何一棵二叉樹T T,若其終端結(jié)點(diǎn)數(shù)為,若其終端結(jié)點(diǎn)數(shù)為n n0 0 ,度為,度為2 2的的 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n2 2,則,則n n0 0=n=n2 2+1 +1 。 證明:設(shè)證明:設(shè)n1為二叉樹中度為為二叉樹中度為1 的結(jié)點(diǎn)數(shù)。該二叉樹的結(jié)點(diǎn)總的結(jié)點(diǎn)數(shù)。該二叉樹的結(jié)點(diǎn)總 數(shù)數(shù)n為度分別為為度分別為0,1,2的結(jié)點(diǎn)數(shù)之和,即的結(jié)點(diǎn)數(shù)之和,即 n=n0+n1+n2 (1) 除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有一條邊進(jìn)入,設(shè)邊數(shù)為除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有一條邊進(jìn)入,設(shè)邊數(shù)為e,有有n = e + 1。由于這些邊是由度為。由于這些邊是由度為1或或2的的結(jié)點(diǎn)射出的的結(jié)點(diǎn)射出的,所以又
11、有的,所以又有e=n1+2n2,于是得,于是得 n=e+1=n1+2n2+1 (2) 由(由(1)和()和(2)得)得 n0+n1+n2=n1+2n2+1, 即即 n0=n2+1 兩種特殊形式的二叉樹兩種特殊形式的二叉樹滿二叉樹滿二叉樹定義:深度為定義:深度為k且有且有2k-1個(gè)結(jié)點(diǎn)的二叉樹是滿二叉樹。個(gè)結(jié)點(diǎn)的二叉樹是滿二叉樹。 (每一層上的結(jié)點(diǎn)數(shù)都是最大每一層上的結(jié)點(diǎn)數(shù)都是最大)完全二叉樹完全二叉樹定義:深度為定義:深度為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)一一對(duì)應(yīng)時(shí),稱為
12、結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),稱為完全二叉樹。完全二叉樹。特點(diǎn)特點(diǎn):葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn),若其右分支下子孫的最大層次為對(duì)任一結(jié)點(diǎn),若其右分支下子孫的最大層次為L(zhǎng),則其左分支下子孫的最大層次必為則其左分支下子孫的最大層次必為L(zhǎng) 或或L+1二叉樹二叉樹1231145891213671014151231145891267101234567123456性質(zhì)性質(zhì)4 有有n個(gè)結(jié)點(diǎn)(個(gè)結(jié)點(diǎn)(n0)的)的完全二叉樹完全二叉樹的高度為的高度為 log2 (n)+1。性質(zhì)性質(zhì)5 如果對(duì)一棵有如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的完全二叉樹完全二叉樹的結(jié)點(diǎn)按層的結(jié)點(diǎn)按層序編號(hào)
13、,則對(duì)任一結(jié)點(diǎn)序編號(hào),則對(duì)任一結(jié)點(diǎn)i(1in),有:有:(1)如果如果i=1,則結(jié)點(diǎn)則結(jié)點(diǎn)i是二叉樹的根,無(wú)雙親;如果是二叉樹的根,無(wú)雙親;如果i1,則其雙親是則其雙親是 i/2 (2)如果如果2in,則結(jié)點(diǎn)則結(jié)點(diǎn)i無(wú)左孩子;如果無(wú)左孩子;如果2in,則其則其 左左孩子是孩子是2i(3)如果如果2i+1n,則結(jié)點(diǎn)則結(jié)點(diǎn)i無(wú)右孩子;如果無(wú)右孩子;如果2i+1n,則則其右孩子是其右孩子是2i+13、二叉樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu))順序存儲(chǔ)結(jié)構(gòu)將完全二叉樹編號(hào)為將完全二叉樹編號(hào)為i的結(jié)點(diǎn)元素按編號(hào)從的結(jié)點(diǎn)元素按編號(hào)從小到大小到大 依次存儲(chǔ)在一維數(shù)組中。依次存儲(chǔ)在一維數(shù)組中。 順
14、序存儲(chǔ)結(jié)構(gòu)的特點(diǎn):順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn): 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中, 適于存滿適于存滿二叉樹和完全二叉樹二叉樹和完全二叉樹(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表)typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree;lchild data rchild 空指針個(gè)數(shù):空指針個(gè)數(shù):2 2* *n n0 0+1+1* *n n1 1+0+0* *n n2 2=2n=2n0 0+n+n1 1=n=n0 0+n+n1 1+ +n n0 0=
15、n=n0 0+n+n1 1+ +n n2 2+1+1=n+1=n+1在在n n個(gè)結(jié)點(diǎn)的二叉鏈表中,有個(gè)結(jié)點(diǎn)的二叉鏈表中,有( )( )個(gè)空指針域個(gè)空指針域? ?ABCDEFG AB CDEFG在在n n個(gè)結(jié)點(diǎn)的二叉鏈表中,個(gè)結(jié)點(diǎn)的二叉鏈表中,第個(gè)結(jié)點(diǎn)有兩個(gè)指針域,每個(gè)結(jié)點(diǎn)又是其父結(jié)第個(gè)結(jié)點(diǎn)有兩個(gè)指針域,每個(gè)結(jié)點(diǎn)又是其父結(jié)點(diǎn)的一個(gè)指針域所指,而根沒有父,所以,有點(diǎn)的一個(gè)指針域所指,而根沒有父,所以,有n-1n-1個(gè)非空指針,所以,空個(gè)非空指針,所以,空指針指針2n-(n-1)=n+12n-(n-1)=n+1三叉鏈表三叉鏈表lchild data parent rchildABCDEFG A B
16、C DE F G返回返回6.36.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹1.遍歷遍歷DL LR RDLR(先序)先序) LDR(中序)(中序)LRD(后序)(后序)DRL RDL RLD先序遍歷:先訪問根結(jié)點(diǎn)先序遍歷:先訪問根結(jié)點(diǎn), ,然后分別先序遍歷左子樹、然后分別先序遍歷左子樹、右子樹。右子樹。中序遍歷:先中序遍歷左子樹,然后訪問根結(jié)點(diǎn),最中序遍歷:先中序遍歷左子樹,然后訪問根結(jié)點(diǎn),最后中序遍歷右子樹。后中序遍歷右子樹。后序遍歷:先后序遍歷左、右子樹,然后訪問根結(jié)點(diǎn)后序遍歷:先后序遍歷左、右子樹,然后訪問根結(jié)點(diǎn)。遍歷二叉樹遍歷二叉樹算法算法6.1先序遍歷二叉樹的遞歸算法先序遍歷二
17、叉樹的遞歸算法Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e) if(T) if(Visit(T-data) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/PreOrderTraverse-+/a*b-efcd先序遍歷:先序遍歷:中序遍歷:中序遍歷:后序遍歷:后序遍歷:- -+ + a a * * b b - -c c d d / /e e f
18、f- -+ +a a* *b b- -c cd d/ /e ef f+ +a a* *b b- -c c d d/ /e e f f- -例:例:算法算法6.2 中序遍歷二叉樹中序遍歷二叉樹T的非遞歸算法的非遞歸算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) InitStack(S);Push(S,T); while (!StackEmpty(S) while(GetTop(S,p) & p)Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p);if(!V
19、isit(p-data)return ERROR; Push(S,p-rchild); /if /while return OK;/InorderTraverseABCDEFG算法算法6.3 改進(jìn)的中序遍歷二叉樹改進(jìn)的中序遍歷二叉樹T的非遞歸算法的非遞歸算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) InitStack(S);p=T; while (p|!StackEmpty(S) if(p)Push(S,p);p=p-lchild; else Pop(S,p); if(!Visit(p-data)return ERR
20、OR; p=p-rchild; /else /while return OK;/InorderTraverse ABCDEFG算法算法6.4 先序輸入二叉樹的結(jié)點(diǎn)先序輸入二叉樹的結(jié)點(diǎn),構(gòu)造二叉樹構(gòu)造二叉樹Status CreateBiTree(BiTree &T) scanf(&ch); if(ch= )T=NULL; else if(!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;/
21、CreateBiTree; 例例:ABCDEGF ABCDEFG若二叉樹中各結(jié)點(diǎn)的值均不相同,則:若二叉樹中各結(jié)點(diǎn)的值均不相同,則: 由二叉樹的前序序列和中序序列,或由其后序序列由二叉樹的前序序列和中序序列,或由其后序序列和中序序列均和中序序列均能唯一能唯一地確定一棵二叉樹,但由前序序列地確定一棵二叉樹,但由前序序列 和后序序列卻和后序序列卻不一定能唯一不一定能唯一地確定一棵二叉樹。地確定一棵二叉樹。 遍歷二叉樹是以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一遍歷二叉樹是以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一個(gè)線性序列,得到二叉樹中結(jié)點(diǎn)的先序序列或中序序列個(gè)線性序列,得到二叉樹中結(jié)點(diǎn)的先序序列或中序序列或后序序列
22、。這實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化或后序序列。這實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作。操作。 重要結(jié)論重要結(jié)論2.線索二叉樹線索二叉樹算法算法6.5 中序遍歷中序線索化樹(不需要棧)中序遍歷中序線索化樹(不需要棧)Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e) p=T-lchild; while(p!=T) while(p-LTag=Link)p=p-lchild; if(!Visit(p-data)return ERROR; while(p-RTag=Thread & p-rchild!=T)
23、 p=p-rchild;Visit(p-data); p=p-rchild; return OK:/InOrderTraverse_Thr算法算法6.6 中序遍歷并線索化二叉樹(遍歷的同時(shí)修改空指針)中序遍歷并線索化二叉樹(遍歷的同時(shí)修改空指針)Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-Ltag=Link;Thrt-Rtag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-l
24、child=Thrt;else Thrt-lchild=T;pre=Thrt; InThreading(T); pre-rchild=Thrt;pre-Rtag=Thread; Thrt-rchild=pre;return OK; 算法算法6.7(線索化(線索化p所指二叉樹)所指二叉樹)總是在當(dāng)前結(jié)點(diǎn)中處理其左線索,在下一個(gè)結(jié)點(diǎn)中處理當(dāng)前結(jié)點(diǎn)的右線索總是在當(dāng)前結(jié)點(diǎn)中處理其左線索,在下一個(gè)結(jié)點(diǎn)中處理當(dāng)前結(jié)點(diǎn)的右線索void InThreading(BiThrTree p) if(p) InThreading(p-lchild); if(!p-lchild)p-LTag=Thread;p-lchi
25、ld=pre;) if(!pre-rchild) pre-RTag=Thread;pre-rchild=p; pre=p; inThreading(p-rchild); 6.46.4 樹和森林樹和森林1 1、樹的存儲(chǔ)結(jié)構(gòu)、樹的存儲(chǔ)結(jié)構(gòu)(1 1)雙親表示法)雙親表示法實(shí)現(xiàn):定義實(shí)現(xiàn):定義結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組存放樹的結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)含存放樹的結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)含兩個(gè)域:兩個(gè)域:數(shù)據(jù)域:存放結(jié)點(diǎn)本身信息數(shù)據(jù)域:存放結(jié)點(diǎn)本身信息雙親域:指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中雙親域:指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置位置特點(diǎn):找雙親容易,找孩子難特點(diǎn):找雙親容易,找孩子難typedef struct PTNode TEl
26、emType data; int parent; PTNode;abcdefhgiacdefghib-101124440501234678dataparent如何找孩子結(jié)點(diǎn)?如何找孩子結(jié)點(diǎn)?(2 2)孩子表示法)孩子表示法 孩子鏈表:每個(gè)結(jié)點(diǎn)的孩子鏈表:每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)用單鏈表存儲(chǔ),再用含,再用含n n個(gè)元素的個(gè)元素的結(jié)構(gòu)結(jié)構(gòu)數(shù)組數(shù)組指向每個(gè)孩子鏈表指向每個(gè)孩子鏈表孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)typedef struct CTNode int child; /該結(jié)點(diǎn)在表頭數(shù)組中該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo)下標(biāo) struct CTNode *next; /指向下一孩子結(jié)點(diǎn)指向下一孩子結(jié)點(diǎn) *
27、ChildPtr;表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)typedef struct TElemType data; /數(shù)據(jù)域數(shù)據(jù)域 ChildPtr firstchild /孩子鏈表頭指針孩子鏈表頭指針 CTBox;表頭結(jié)點(diǎn)數(shù)組表頭結(jié)點(diǎn)數(shù)組Thpedef struct CTBox nodesMAX_TREE_SIZE; int n,r; /結(jié)點(diǎn)數(shù)和根的位置結(jié)點(diǎn)數(shù)和根的位置CTree; abcdefhgiabcdefhgi6012345789acdefghibdatafirstchild 12 3 48 6 7 5如何找雙親結(jié)點(diǎn)如何找雙親結(jié)點(diǎn)? ?39(3 3)孩子兄弟表示法(二叉樹表示法)孩子兄弟表示法(二叉樹表
28、示法) 用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),鏈表中每個(gè)結(jié)點(diǎn)的兩用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)結(jié)點(diǎn)typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling;CSNode,*CSTree;abcdefhgi a b c d e f ghi2 2、森林與二叉樹轉(zhuǎn)換森林與二叉樹轉(zhuǎn)換ACBED樹樹ABCDE二叉二叉樹樹 A BC D E (1)樹轉(zhuǎn)換成)樹轉(zhuǎn)換成二叉二叉樹樹將樹轉(zhuǎn)換成二叉樹將樹轉(zhuǎn)換成二叉樹加線:加線
29、:在兄弟之間加一連線在兄弟之間加一連線擦線:擦線:對(duì)每個(gè)結(jié)點(diǎn),擦去它(除最左面孩子)與其對(duì)每個(gè)結(jié)點(diǎn),擦去它(除最左面孩子)與其 余孩子之間的關(guān)系余孩子之間的關(guān)系旋轉(zhuǎn):旋轉(zhuǎn):以樹的根結(jié)點(diǎn)為軸心,將整樹順時(shí)針轉(zhuǎn)以樹的根結(jié)點(diǎn)為軸心,將整樹順時(shí)針轉(zhuǎn)4545ABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空!樹轉(zhuǎn)換成的二叉樹其右子樹一定為空! 二叉樹中的左子是其樹中的第一個(gè)孩子,右子是其樹中二叉樹中的左子是其樹中的第一個(gè)孩子,右子是其樹中的兄弟。按樹轉(zhuǎn)二叉樹的逆操作完成轉(zhuǎn)換的兄弟。按樹轉(zhuǎn)二叉樹的逆操作完成轉(zhuǎn)換ABCDEFGHIABCDEFGHI(2)二叉二叉樹轉(zhuǎn)換成樹樹轉(zhuǎn)換成樹將各棵樹
30、的根看作兄弟,按樹的方式轉(zhuǎn)換成二叉樹將各棵樹的根看作兄弟,按樹的方式轉(zhuǎn)換成二叉樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJ(3 3)森林轉(zhuǎn)換成二叉樹)森林轉(zhuǎn)換成二叉樹(4 4)二叉樹轉(zhuǎn)換成森林)二叉樹轉(zhuǎn)換成森林ABCDEFGHIJABCDEFGHIJABCDEFGHIJ首先,將二叉樹首先,將二叉樹“拆開拆開”然后,將拆天的各棵二叉樹轉(zhuǎn)換成樹然后,將拆天的各棵二叉樹轉(zhuǎn)換成樹3、樹和森林的遍歷、樹和森林的遍歷 樹的遍歷樹的遍歷v先根(序)遍歷:先訪問樹的根結(jié)點(diǎn),然后依先根(序)遍歷:先訪問樹的根結(jié)點(diǎn),然后依次次先根遍歷根的每棵子樹先根遍歷根的每棵子樹v后根(序)遍歷:先依次后根遍
31、歷每棵子樹,后根(序)遍歷:先依次后根遍歷每棵子樹,然然后訪問根結(jié)點(diǎn)后訪問根結(jié)點(diǎn)v按層次遍歷:先訪問第一層上的結(jié)點(diǎn),然后依按層次遍歷:先訪問第一層上的結(jié)點(diǎn),然后依次次遍歷第二層,遍歷第二層,第第n n層的結(jié)點(diǎn)層的結(jié)點(diǎn)ABCDEFGHIJKLMNO先根遍歷:先根遍歷:后根遍歷:后根遍歷:層次遍歷:層次遍歷:ABEFIG CDHJ KLNOMEIFGBCJKNOLMHDAABCDEFGHI J KLMNO討論:若采用討論:若采用“先轉(zhuǎn)換,后遍歷先轉(zhuǎn)換,后遍歷”方式,結(jié)果是否一樣?方式,結(jié)果是否一樣?a ab bd de ec c先序遍歷:先序遍歷:后序遍歷:后序遍歷:中序遍歷:中序遍歷:d e c
32、 b ad e c b aa ab bd de ec ca b c d ea b c d eb d c e ab d c e a1. 1. 樹的樹的先根遍歷先根遍歷相當(dāng)于對(duì)應(yīng)二叉樹的相當(dāng)于對(duì)應(yīng)二叉樹的先序遍歷先序遍歷; 2. 2. 樹的樹的后序遍歷后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹的相當(dāng)于對(duì)應(yīng)二叉樹的中序遍歷中序遍歷;3. 3. 樹沒有中序遍歷,因?yàn)樽訕錈o(wú)左右之分。樹沒有中序遍歷,因?yàn)樽訕錈o(wú)左右之分。結(jié)論:結(jié)論:先序遍歷先序遍歷F若森林為空,返回;若森林為空,返回;F訪問森林中第一棵樹的根結(jié)點(diǎn);訪問森林中第一棵樹的根結(jié)點(diǎn);F先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林;先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林;F先序遍
33、歷除去第一棵樹之后剩余的樹構(gòu)成先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。的森林。中序遍歷(中序遍歷(后序遍歷每一棵樹后序遍歷每一棵樹)F若森林為空,返回;若森林為空,返回;F中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林;森林;F訪問第一棵樹的根結(jié)點(diǎn);訪問第一棵樹的根結(jié)點(diǎn);F中序遍歷除去第一棵樹之后剩余的樹構(gòu)成中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。的森林。森林的遍歷森林的遍歷例:例:先序序列:先序序列:中序序列:中序序列:A B C D E F G H I JB C D A F E H J I G先序序列:先序序列:中序序列:中序序列:A B C D E
34、F G H I JB C D A F E H J I G結(jié)論:森林的先序和中序遍歷與其等價(jià)結(jié)論:森林的先序和中序遍歷與其等價(jià)二叉樹的兩種遍歷結(jié)果對(duì)應(yīng)相同。二叉樹的兩種遍歷結(jié)果對(duì)應(yīng)相同。路徑:路徑:從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支稱為這從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支稱為這兩個(gè)結(jié)點(diǎn)之間的路徑。兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長(zhǎng)度:路徑長(zhǎng)度:路徑上分支的數(shù)目稱為路徑長(zhǎng)度。路徑上分支的數(shù)目稱為路徑長(zhǎng)度。結(jié)點(diǎn)的權(quán):結(jié)點(diǎn)的權(quán):將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值,將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值,則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度:結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度:從根結(jié)點(diǎn)到該
35、結(jié)點(diǎn)之間的路徑從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用1 1、基本概念、基本概念樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度是樹的帶權(quán)路徑長(zhǎng)度是所有葉子結(jié)點(diǎn)所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度的帶權(quán)路徑長(zhǎng)度之和,記為之和,記為 WPL= WPL= 其中:其中:n n 為葉子結(jié)點(diǎn)數(shù)目為葉子結(jié)點(diǎn)數(shù)目 w wi i為第為第i i 個(gè)葉子結(jié)點(diǎn)的權(quán)值個(gè)葉子結(jié)點(diǎn)的權(quán)值 l li i 為第為第i i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。niiilw1哈夫曼樹哈夫曼樹 用用n n個(gè)權(quán)值構(gòu)造二叉樹,其中帶權(quán)路徑長(zhǎng)度最小個(gè)權(quán)值構(gòu)
36、造二叉樹,其中帶權(quán)路徑長(zhǎng)度最小的 二 叉 樹 為 最 優(yōu) 二 叉 樹 , 也 稱 為 哈 夫 曼 樹的 二 叉 樹 為 最 優(yōu) 二 叉 樹 , 也 稱 為 哈 夫 曼 樹(Huffman tree)(Huffman tree)。哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用例:有例:有4 4個(gè)結(jié)點(diǎn),權(quán)值分別為個(gè)結(jié)點(diǎn),權(quán)值分別為7 7,5 5,2 2,4 4,構(gòu)造有,構(gòu)造有4 4個(gè)葉子結(jié)點(diǎn)的二叉樹個(gè)葉子結(jié)點(diǎn)的二叉樹a ab bc cd d7 75 52 24 4WPL=7WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36d dc ca ab b2 24 47 75 5WPL
37、=7WPL=7* *3+53+5* *3+23+2* *1+41+4* *2=462=46a ab bc cd d7 75 52 24 4WPL=7WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=352 2、構(gòu)造哈夫曼樹、構(gòu)造哈夫曼樹根據(jù)給定的根據(jù)給定的n n個(gè)權(quán)值個(gè)權(quán)值 w w1 1,w,w2 2, ,w wn n ,構(gòu)造構(gòu)造n n棵只棵只有根結(jié)點(diǎn)的二叉樹有根結(jié)點(diǎn)的二叉樹。在在此集合此集合中選取兩棵根結(jié)點(diǎn)中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左權(quán)值最小的樹作左右子樹右子樹,構(gòu)造一棵新的二叉樹,置新二叉樹根結(jié),構(gòu)造一棵新的二叉樹,置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)
38、權(quán)值之和。點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。在在集合集合中中刪除這兩棵樹刪除這兩棵樹,同時(shí)將新得到的二叉,同時(shí)將新得到的二叉樹加入樹加入到集合到集合中。中。重復(fù)上述兩步,重復(fù)上述兩步,直到只含一棵樹為止直到只含一棵樹為止,這棵樹,這棵樹即即霍霍夫曼樹。夫曼樹?;舴蚵鼧涞臉?gòu)造過程霍夫曼樹的構(gòu)造過程HuffmanHuffman樹的構(gòu)造過程樹的構(gòu)造過程7 75 54 42 25 5181811116 64 42 27 7WPL=7WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=35哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用引入:在遠(yuǎn)程通訊中,要將待傳字符轉(zhuǎn)換成由二進(jìn)制引入:在
39、遠(yuǎn)程通訊中,要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串。組成的字符串。 設(shè)要傳送的字符為:設(shè)要傳送的字符為: ABACCDAABACCDA 若編碼為:若編碼為:A00 BA00 B0101 C C1010 D-D-1111 若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼,即讓待傳若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼,即讓待傳字符串中字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼,則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。00000101000010101010111100003 3、哈夫曼樹的應(yīng)用、哈夫曼樹的應(yīng)用( (哈夫曼編碼哈夫曼編碼) )ABACCD
40、AABACCDA哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用設(shè)要傳送的字符為:設(shè)要傳送的字符為:ABACCDAABACCDA若編碼為:若編碼為:A0 B00 C1 D-01 A0 B00 C1 D-01 關(guān)鍵:要設(shè)計(jì)關(guān)鍵:要設(shè)計(jì)長(zhǎng)度不等的編碼長(zhǎng)度不等的編碼,則必須,則必須使任一字符使任一字符的編碼都不是另一個(gè)字符的編碼的前綴的編碼都不是另一個(gè)字符的編碼的前綴。這。這種編碼稱作前綴編碼。種編碼稱作前綴編碼。 ABAABACCDACCDA 000011010但:但: 00000000 AAAA ABA BB AAAA ABA BB重碼重碼哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用設(shè)設(shè)A A、B B、C C、D D的使用
41、頻率分別為的使用頻率分別為7 7,2 2,5 5,4 4則如何為它們編碼,使其滿足前綴編碼?則如何為它們編碼,使其滿足前綴編碼?0 01101100 0101010101111110 0以各字符的權(quán)值構(gòu)造以各字符的權(quán)值構(gòu)造huffmanhuffman樹,然后編碼:左分支樹,然后編碼:左分支用用“0”0”表示;右分支用表示;右分支用“1”1”表示表示ABACCDAABACCDA哈夫曼編碼:哈夫曼編碼:5 5181811116 64 42 27 7C CA AB BD D100011A A:0 0B B:110110C C:1010D D:111111哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用例:已知某系統(tǒng)
42、在通訊時(shí),只出現(xiàn)例:已知某系統(tǒng)在通訊時(shí),只出現(xiàn)C C,A A,S S,T T,B B五種字符,它們出現(xiàn)的頻率依次為五種字符,它們出現(xiàn)的頻率依次為2 2,4 4,2 2,3 3,3 3,試設(shè)計(jì)試設(shè)計(jì)HuffmanHuffman編碼。編碼。 148464220001113301 T B A C S出現(xiàn)頻率越大的字出現(xiàn)頻率越大的字符,其符,其HuffmanHuffman編編碼越短。碼越短。由由HuffmanHuffman樹得樹得HuffmanHuffman編碼為:編碼為: T B A C S T B A C S 00 01 10 110 111 00 01 10 110 111243362 4 8返
43、回返回哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 霍夫曼編碼是霍夫曼編碼是不等長(zhǎng)編碼不等長(zhǎng)編碼 霍夫曼編碼是霍夫曼編碼是前綴編碼前綴編碼,即任一字符的編碼都不,即任一字符的編碼都不是另一字符編碼的前綴是另一字符編碼的前綴 霍夫曼編碼樹中沒有度為霍夫曼編碼樹中沒有度為1 1的結(jié)點(diǎn)。若葉子結(jié)點(diǎn)的結(jié)點(diǎn)。若葉子結(jié)點(diǎn)的個(gè)數(shù)為的個(gè)數(shù)為n n,則霍夫曼編碼樹的,則霍夫曼編碼樹的結(jié)點(diǎn)總數(shù)為結(jié)點(diǎn)總數(shù)為 2n-12n-1 發(fā)送過程:根據(jù)由發(fā)送過程:根據(jù)由霍夫曼樹得到的編碼表霍夫曼樹得到的編碼表送出字送出字符數(shù)據(jù)符數(shù)據(jù) 接收過程:按接收過程:按左左0 0、右、右1 1的規(guī)定,從根結(jié)點(diǎn)走到一的規(guī)定,從根結(jié)點(diǎn)走到一個(gè)葉結(jié)點(diǎn),完成
44、一個(gè)字符的譯碼。反復(fù)此過程,個(gè)葉結(jié)點(diǎn),完成一個(gè)字符的譯碼。反復(fù)此過程,直到接收數(shù)據(jù)結(jié)束直到接收數(shù)據(jù)結(jié)束霍夫曼編碼的幾點(diǎn)結(jié)論霍夫曼編碼的幾點(diǎn)結(jié)論-61-樹的計(jì)數(shù)問題樹的計(jì)數(shù)問題具有具有n n個(gè)結(jié)點(diǎn)的不同形態(tài)的樹有多少棵?個(gè)結(jié)點(diǎn)的不同形態(tài)的樹有多少棵?二叉樹二叉樹T T和和T T 相似相似二者均為空樹,或二者均為空樹,或二者均不為空樹,且它們的左右子樹分別相似二者均不為空樹,且它們的左右子樹分別相似二叉樹二叉樹T T和和T T 等價(jià)等價(jià)二者相似,且所有對(duì)應(yīng)結(jié)點(diǎn)上的數(shù)據(jù)元素均相同二者相似,且所有對(duì)應(yīng)結(jié)點(diǎn)上的數(shù)據(jù)元素均相同 樹的計(jì)數(shù)樹的計(jì)數(shù)-62-二叉樹的計(jì)數(shù)問題二叉樹的計(jì)數(shù)問題具有具有n n個(gè)結(jié)點(diǎn)、
45、互不相似的二叉樹的數(shù)目個(gè)結(jié)點(diǎn)、互不相似的二叉樹的數(shù)目b bn n具有具有n n 個(gè)結(jié)點(diǎn)的樹的數(shù)目個(gè)結(jié)點(diǎn)的樹的數(shù)目t tn n= =b bn n-1-1(依據(jù):森林與二叉樹的相互轉(zhuǎn)換)(依據(jù):森林與二叉樹的相互轉(zhuǎn)換)nnCn2n11b 樹的計(jì)數(shù)樹的計(jì)數(shù)課堂練習(xí)課堂練習(xí)一、下面是有關(guān)二叉樹的敘述,請(qǐng)判斷正誤。一、下面是有關(guān)二叉樹的敘述,請(qǐng)判斷正誤。( )1.1.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1 1。 ( )2.2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 ( )3.3.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。樹。 ( )4.4.完全二叉樹中所有結(jié)點(diǎn),如果不存在非空左子樹完全二叉樹中所有結(jié)點(diǎn),如果不存在非空左子樹,則在非空右子樹。,則在非空右子樹。 ( )5.5.對(duì)于一棵非空二叉樹,它的根結(jié)點(diǎn)作為第一層,對(duì)于一棵非空二叉樹,它的根結(jié)點(diǎn)作為第一層,則它的第則它的第i i層上最多能有層上最多能有2 2i i1 1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 ( )6.6.用二叉鏈表法存儲(chǔ)包含用二叉鏈表法存儲(chǔ)包含n n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的2n2n個(gè)指針區(qū)域中有個(gè)指針區(qū)域中有n+1n+1個(gè)為空指針。個(gè)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 試乘試駕話術(shù)-君越060801
- 散打課件教學(xué)課件
- 教學(xué)課件配色
- 2025廣西來(lái)賓事業(yè)單位考試-方式筆試歷年典型考題及考點(diǎn)剖析附帶答案詳解
- 變形計(jì)教學(xué)課件
- 文字創(chuàng)作比賽活動(dòng)方案
- 春季創(chuàng)業(yè)活動(dòng)方案
- 文藝懷舊課堂活動(dòng)方案
- 春季奔馳活動(dòng)方案
- 明日擺攤活動(dòng)方案
- 配電室巡檢記錄表
- 卓越績(jī)效評(píng)價(jià)準(zhǔn)則概述(專業(yè)性權(quán)威性實(shí)用性)
- GB/T 30142-2013平面型電磁屏蔽材料屏蔽效能測(cè)量方法
- GB/T 29894-2013木材鑒別方法通則
- 國(guó)資進(jìn)場(chǎng)交易工作流程講座
- 當(dāng)代法律英語(yǔ)翻譯全
- 制冷操作證培訓(xùn)教材制冷與空調(diào)設(shè)備運(yùn)行操作作業(yè)培訓(xùn)教程課件
- 湖南省長(zhǎng)沙市望城區(qū)2020-2021學(xué)年八年級(jí)下學(xué)期期末考試歷史試卷
- 煙葉烘烤調(diào)制理論考試試題
- DB23-T 3336-2022懸掛式單軌交通技術(shù)標(biāo)準(zhǔn)-(高清最新)
- 服刑人員心理健康教育課件
評(píng)論
0/150
提交評(píng)論