數(shù)據(jù)結(jié)構(gòu)第次課第六章樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)第次課第六章樹和二叉樹第1頁，課件共29頁，創(chuàng)作于2023年2月

樹結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程等等。樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念第2頁，課件共29頁，創(chuàng)作于2023年2月樹的定義

樹是由

n(n

0)個結(jié)點(diǎn)組成的有限集合。如果n=0，稱為空樹；如果n>0，則

有一個特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；

除根以外的其它結(jié)點(diǎn)劃分為m(m

0)個互不相交的有限集合T0,T1,…,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹。第3頁，課件共29頁，創(chuàng)作于2023年2月例：下面的圖是一棵樹T={A,B,C,D,E,F,G,H,I,J}A是根，其余結(jié)點(diǎn)可以劃分為3個互不相交的集合：

T1={B,E,F},T2={C,G},T3={D,H,I,J}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。

例如對于T1，B是根，其余結(jié)點(diǎn)可以劃分為2個互不相交的集合：

T11={E}，T12={F}，T11,T12是B的子樹。height=3ACGBDEFHIJ第4頁，課件共29頁，創(chuàng)作于2023年2月樹的基本術(shù)語

樹結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹的分支；

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；

雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親；

兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；

堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；

結(jié)點(diǎn)層次：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依次類推；

樹的高（深）度：樹中結(jié)點(diǎn)的最大層數(shù)；

結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個數(shù)；

樹的度：樹中最大的結(jié)點(diǎn)度。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)；

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)（非終端結(jié)點(diǎn)）；

森林：互不相交的樹集合；

有序樹：將數(shù)中每個結(jié)點(diǎn)的各子樹看成是從左到右有次序的；

無序樹：不考慮子樹的順序；第5頁，課件共29頁，創(chuàng)作于2023年2月ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先第6頁，課件共29頁，創(chuàng)作于2023年2月練習(xí)1.假設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時，用（x,y）來表示樹邊，已知一棵樹邊的集合為：{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用樹形圖表示出此樹，并回答下列問題：(1)哪個是根結(jié)點(diǎn)？(2)哪些是葉子結(jié)點(diǎn)？(3)哪個是g的雙親？(4)哪些是g的祖先？(5)哪些是g的孩子？(6)哪些是e的子孫？(7)哪些是e的兄弟？哪些是f的兄弟？(8)結(jié)點(diǎn)b和n的層次各是多少？(9)樹的深度是多少？(10)以結(jié)點(diǎn)c為根的子樹的深度是多少？(11)樹的度數(shù)是多少？第7頁，課件共29頁，創(chuàng)作于2023年2月練習(xí)1.假設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時，用（x,y）來表示樹邊，已知一棵樹邊的集合為：{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用樹形圖表示出此樹，并回答下列問題：(1)哪個是根結(jié)點(diǎn)？(2)哪些是葉子結(jié)點(diǎn)？(3)哪個是g的雙親？(4)哪些是g的祖先？(5)哪些是g的孩子？(6)哪些是e的子孫？(7)哪些是e的兄弟？哪些是f的兄弟？(8)結(jié)點(diǎn)b和n的層次各是多少？(9)樹的深度是多少？(10)以結(jié)點(diǎn)c為根的子樹的深度是多少？(11)樹的度數(shù)是多少？abcidhfgmnlekj(1)a(2)m、n、d、l、f、k、j(3)c(4)a、c(5)k、j(6)i、m、n(7)d；h、g(8)2；5(9)5(10)3(11)3第8頁，課件共29頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義，p118第9頁，課件共29頁，創(chuàng)作于2023年2月6.2二叉樹二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷Χ鏄涞脑S多操作算法簡單，而任何樹都可以與二樹相互轉(zhuǎn)換，這樣就解決了樹的存儲結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。6.2.1二叉樹的定義定義：二叉樹是由n(n>=0)個結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。這也是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個概念。第10頁，課件共29頁，創(chuàng)作于2023年2月二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。下圖列出二叉樹的5種基本形態(tài)，(C)和（d）是不同的兩棵二叉樹。

(a)空二叉樹AAAA(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹第11頁，課件共29頁，創(chuàng)作于2023年2月

A

F

G

E

D

C

B

(a)、(b)是不同的二叉樹，(a)的左子樹有四個結(jié)點(diǎn)，(b)的左子樹有兩個結(jié)點(diǎn)，(a)

A

G

E

D

B

C

F(b)第12頁，課件共29頁，創(chuàng)作于2023年2月應(yīng)用舉例例1可以用二叉樹表示表達(dá)式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-第13頁，課件共29頁，創(chuàng)作于2023年2月6.2.2二叉樹的性質(zhì)二叉樹具有下列重要性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)(i>=1)。證明：用數(shù)學(xué)歸納法證明：歸納基礎(chǔ)：i=1時，有2i-1=20=1,因?yàn)榈?層上只有一個根結(jié)點(diǎn)，所以命題成立。歸納假設(shè)：假設(shè)對所有的j（1≤j<i）命題成立，即第j層上至多有2j-1個結(jié)點(diǎn)，證明j=i時命題亦成立。歸納步驟：根據(jù)歸納假設(shè)，第i-1層上至多有2i-2個結(jié)點(diǎn)，由于二叉樹的每個結(jié)點(diǎn)至多有兩個孩子，故第i層上的結(jié)點(diǎn)數(shù)至多是第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍。即j=i時，該層上至多有2*2i-2＝2i-1個結(jié)點(diǎn)，故命題成立。第14頁，課件共29頁，創(chuàng)作于2023年2月6.2.2二叉樹的性質(zhì)二叉樹具有下列重要性質(zhì)：性質(zhì)2：深度為k的二叉樹至多有2k－1個結(jié)點(diǎn)（k>=1)。證明：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時，其樹中結(jié)點(diǎn)數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的結(jié)點(diǎn)數(shù)至多為：

20+21+…+2k-1=1*(1-2k)/(1-2)=2k-1故命題正確。等比數(shù)列求和公式：a1*(1-qn)/(1-q)第15頁，課件共29頁，創(chuàng)作于2023年2月1234567123114589121367101415性質(zhì)3：對任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。證明：n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個分支進(jìn)入設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點(diǎn)引出，B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1第16頁，課件共29頁，創(chuàng)作于2023年2月

兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。下圖是一棵滿二叉樹，對結(jié)點(diǎn)進(jìn)行了順序編號。依層序編號。123114589121367101415第17頁，課件共29頁，創(chuàng)作于2023年2月

如果深度為k、有n個結(jié)點(diǎn)的二叉樹中各結(jié)點(diǎn)能夠與深度為k的順序編號的滿二叉樹從1到n標(biāo)號的結(jié)點(diǎn)相對應(yīng)，則稱這樣的二叉樹為完全二叉樹，滿二叉樹是完全二叉樹的特例。123114589126710完全二叉樹1234567123456非完全二叉樹第18頁，課件共29頁，創(chuàng)作于2023年2月從滿二叉樹及完全二叉樹定義還可以知道，滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。滿二叉樹的葉子結(jié)點(diǎn)全都在最底層，而完全二叉樹的葉子結(jié)點(diǎn)可以分布在最下面兩層。圖6-6所示為兩個深度為3的滿二叉樹和完全二叉樹。

A

G

F

E

D

C

B

A

E

D

C

B圖深度為3的滿二叉樹和完全二叉樹第19頁，課件共29頁，創(chuàng)作于2023年2月

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉樹(c)不是完全二叉樹

A

G

F

E

D

C

B第20頁，課件共29頁，創(chuàng)作于2023年2月性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1符號x表示不大于x的最大整數(shù)。證明：設(shè)完全二叉樹的深度為k，由完全二叉樹定義可得：深度為k的完全二叉樹的前k-1層是滿二叉樹，共有2k-1-1個結(jié)點(diǎn)，第k層上還有若干個結(jié)點(diǎn)，因此有n>2k-1-1,……

①另一方面，n又不會超過深度為k的滿二叉樹的總結(jié)點(diǎn)數(shù)2k-1，又可得：n≤2k-1,……②由①②可推出2k-1≤n<2k

：，取對數(shù)后有：k-1

≤log2n

<k又因k-1和k是相鄰的兩個整數(shù)，故有：k=log2n+1第21頁，課件共29頁，創(chuàng)作于2023年2月練習(xí)1.已知一顆度為m的樹中有n1個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，……nm個度為m的結(jié)點(diǎn)，問該樹中有多少片葉子？解答：葉子數(shù)為：n0=1+0*n1+1*n2+2*n3+…(m-1)*nm說明：想象這棵樹是從一個根開始長起來的：當(dāng)一棵樹僅為根時，它的葉子數(shù)為1，每“長出”一個度為1的結(jié)點(diǎn)都不會增加葉子數(shù)，因此第二項(xiàng)為0，每長出一個度為2的結(jié)點(diǎn)時（無論是從哪一個結(jié)點(diǎn)長出）可以增加1片葉子，依次類推，每長出一個度為m的結(jié)點(diǎn)，就可以增加(m-1)片葉子。第22頁，課件共29頁，創(chuàng)作于2023年2月練習(xí)2.高度為h的完全二叉樹至少有多少個結(jié)點(diǎn)？至多有多少個結(jié)點(diǎn)？解答：高度為h的完全二叉樹至少情況為：前h-1層為滿二叉樹，第h層只有最左結(jié)點(diǎn)，至少有(2h-1-1)+1=2h-1個結(jié)點(diǎn)；至多情況為性質(zhì)2：2h-1。第23頁，課件共29頁，創(chuàng)作于2023年2月性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號,則對任一結(jié)點(diǎn)i（1≤i≤n),有：P125（1）如果i＝1，則結(jié)點(diǎn)i無雙親，是二叉樹的根；如果i>1，則其雙親的編號是i/2（2）如果2i>n，無左孩子；否則，其左孩子是結(jié)點(diǎn)2i。（3）如果2i＋1>n，則結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。123114589126710第24頁，課件共29頁，創(chuàng)作于2023年2月⑴i=1時，2i=2，2i+1=3。左孩子和右孩子剛好是結(jié)點(diǎn)2和3。⑵對于i>1，分兩種情況：設(shè)第j層的第一個結(jié)點(diǎn)的編號為i；

1≤j≤log2n,i=2j-1=>j+1層第一個結(jié)點(diǎn)的編號

j層第一個結(jié)點(diǎn)的左孩子必為第j+1層的第一個結(jié)點(diǎn)，其編號為2(j+1)-1=2j=2(2j-1)=2i，若n<2i，則無左孩子；j層第一個結(jié)點(diǎn)的右孩子必為第j+1層的第二個結(jié)點(diǎn)，其編號為2i+1，若n<2i+1，則無右孩子。第25頁，課件共29頁，創(chuàng)作于2023年2月⑵對于i>1，分兩種情況：設(shè)第j層的第一個結(jié)點(diǎn)的編號為i；

1≤j≤log2n,i=2j-1=>j+1層第一個結(jié)點(diǎn)的編號設(shè)第j層上某個結(jié)點(diǎn)的編號為i，且2i+1<n，則其左孩子為2i，右孩子為2i+1。

1≤j≤log2n,2j-1≤i<2j-1（為j層上第一個結(jié)點(diǎn)，不包括j層上最后一個結(jié)點(diǎn)）=>編號為i+1的結(jié)點(diǎn)，右兄弟或者堂兄弟若編號為i+1的結(jié)點(diǎn)有左孩子，則編號必為2i+1+1=2(i+1)，若編號為i+1的結(jié)點(diǎn)有右孩子，則編號必為2i+3=2(i+1)+1。所以，性質(zhì)5的(2)和(3)得證，（2）如果2i>n，無左孩子；否則，其左孩子是結(jié)點(diǎn)2i。（3）如果2i＋1>n，則結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。推出，性質(zhì)5的(1)

（1）如果i＝1，則結(jié)點(diǎn)i無雙親，是二叉樹的根；如果i>1，則其雙親的編號是i/2第26頁，課件共29頁，創(chuàng)作于2023年2月練習(xí)一顆完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是_______。A.250B.500C.501D.505解答：由二叉樹的性質(zhì)可知：n0=n2+1，且完全二叉樹的n1=0或者n1=1；已知二叉樹的總結(jié)點(diǎn)數(shù)n=n0+n1+n2，即有

n=2n0+n