數(shù)據(jù)結構第次課第六章樹和二叉樹

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

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

樹是由

n(n

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

有一個特定的稱之為根(root)的結點，它只有直接后繼，但沒有直接前驅；

除根以外的其它結點劃分為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是根，其余結點可以劃分為3個互不相交的集合：

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

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

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

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

孩子結點：結點的子樹的根稱為該結點的孩子；

雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；

兄弟結點：同一雙親的孩子結點；

堂兄結點：同一層上結點；

結點層次：根結點的層定義為1；根的孩子為第二層結點，依次類推；

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

結點的度：結點子樹的個數(shù)；

樹的度：樹中最大的結點度。

葉子結點：也叫終端結點，是度為0的結點；

分枝結點：度不為0的結點（非終端結點）；

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

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

無序樹：不考慮子樹的順序；第5頁，課件共29頁，創(chuàng)作于2023年2月ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F(xiàn)結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點A是結點F，G的祖先第6頁，課件共29頁，創(chuàng)作于2023年2月練習1.假設在樹中，結點x是結點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)哪個是根結點？(2)哪些是葉子結點？(3)哪個是g的雙親？(4)哪些是g的祖先？(5)哪些是g的孩子？(6)哪些是e的子孫？(7)哪些是e的兄弟？哪些是f的兄弟？(8)結點b和n的層次各是多少？(9)樹的深度是多少？(10)以結點c為根的子樹的深度是多少？(11)樹的度數(shù)是多少？第7頁，課件共29頁，創(chuàng)作于2023年2月練習1.假設在樹中，結點x是結點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)哪個是根結點？(2)哪些是葉子結點？(3)哪個是g的雙親？(4)哪些是g的祖先？(5)哪些是g的孩子？(6)哪些是e的子孫？(7)哪些是e的兄弟？哪些是f的兄弟？(8)結點b和n的層次各是多少？(9)樹的深度是多少？(10)以結點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二叉樹二叉樹在樹結構的應用中起著非常重要的作用，因為對二叉樹的許多操作算法簡單，而任何樹都可以與二樹相互轉換，這樣就解決了樹的存儲結構及其運算中存在的復雜性。6.2.1二叉樹的定義定義：二叉樹是由n(n>=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。這也是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個概念。第10頁，課件共29頁，創(chuàng)作于2023年2月二叉樹結點的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進行區(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)的左子樹有四個結點，(b)的左子樹有兩個結點，(a)

A

G

E

D

B

C

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

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個結點(i>=1)。證明：用數(shù)學歸納法證明：歸納基礎：i=1時，有2i-1=20=1,因為第1層上只有一個根結點，所以命題成立。歸納假設：假設對所有的j（1≤j<i）命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。歸納步驟：根據(jù)歸納假設，第i-1層上至多有2i-2個結點，由于二叉樹的每個結點至多有兩個孩子，故第i層上的結點數(shù)至多是第i-1層上的最大結點數(shù)的2倍。即j=i時，該層上至多有2*2i-2＝2i-1個結點，故命題成立。第14頁，課件共29頁，創(chuàng)作于2023年2月6.2.2二叉樹的性質(zhì)二叉樹具有下列重要性質(zhì)：性質(zhì)2：深度為k的二叉樹至多有2k－1個結點（k>=1)。證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數(shù)時，其樹中結點數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的結點數(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：對任何一棵二叉樹，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0＝n2＋1。證明：n1為二叉樹T中度為1的結點數(shù)因為：二叉樹中所有結點的度均小于或等于2所以：其結點總數(shù)n=n0+n1+n2

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

又：分支由度為1和度為2的結點引出，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個結點的二叉樹稱為滿二叉樹。下圖是一棵滿二叉樹，對結點進行了順序編號。依層序編號。123114589121367101415第17頁，課件共29頁，創(chuàng)作于2023年2月

如果深度為k、有n個結點的二叉樹中各結點能夠與深度為k的順序編號的滿二叉樹從1到n標號的結點相對應，則稱這樣的二叉樹為完全二叉樹，滿二叉樹是完全二叉樹的特例。123114589126710完全二叉樹1234567123456非完全二叉樹第18頁，課件共29頁，創(chuàng)作于2023年2月從滿二叉樹及完全二叉樹定義還可以知道，滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。滿二叉樹的葉子結點全都在最底層，而完全二叉樹的葉子結點可以分布在最下面兩層。圖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個結點的完全二叉樹的深度為log2n+1符號x表示不大于x的最大整數(shù)。證明：設完全二叉樹的深度為k，由完全二叉樹定義可得：深度為k的完全二叉樹的前k-1層是滿二叉樹，共有2k-1-1個結點，第k層上還有若干個結點，因此有n>2k-1-1,……

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

1≤j≤log2n,i=2j-1=>j+1層第一個結點的編號

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

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

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

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

n=2n0+n