數(shù)據(jù)結(jié)構(gòu)-基于Python語言（微課版） 課件T15-樹(二叉樹)

二叉樹第八章：樹

主講：周翔什么是二叉樹二叉樹是一類非常重要的特殊的樹形結(jié)構(gòu)二叉樹的定義：是n個結(jié)點的有限集合。在二叉樹中，每個結(jié)點至多有2個兒子，并且有左、右之分位于左邊的孩子叫做左孩子位于右邊的孩子叫做右孩子什么是二叉樹兩棵不同的二叉樹ABCDEABCDE什么是二叉樹二叉樹VS普通樹、有序樹：二叉樹與度數(shù)不超過2的樹不同，與度數(shù)不超過2的有序樹也不同。在普通的樹中，若結(jié)點只有一個兒子，無左右之說。二叉樹是有序樹，左子樹和右子樹次序不能顛倒，即使樹中某個結(jié)點只有一棵子樹，也要區(qū)別是左子樹還是右子樹。在有序樹中，雖然一個結(jié)點的兒子之間是有左右次序的，但若該結(jié)點只有一個兒子時，就無須區(qū)分其左右次序。在二叉樹中，即使是一個兒子也有左右之分。什么是二叉樹二叉樹的基本形態(tài)有五種：（1）空二叉樹；（2）僅有根結(jié)點的二叉樹；（3）僅有一棵左子樹的二叉樹；（4）僅有一棵右子樹的二叉樹；（5）有兩棵子樹的二叉樹；（1）A（2）AB（3）AB（4）ABC（5）二叉樹的分類兩種特殊的二叉樹滿二叉樹：一棵高度為k且有2k-1個結(jié)點的二叉樹。完全二叉樹（也叫近似滿二叉樹）：若將滿二叉樹最后一層的結(jié)點，從右向左連續(xù)缺若干結(jié)點，就是完全二叉樹。滿二叉樹完全二叉樹二叉樹的分類滿二叉樹：除葉子結(jié)點外，樹中的每個結(jié)點都有兩個孩子結(jié)點，每一層的結(jié)點數(shù)都達到最大。ABCDEFGHJIKLMNO二叉樹的分類在完全二叉樹（滿二叉樹）中，若某個結(jié)點沒有左兒子，則它一定沒有右兒子，即該結(jié)點是一個葉結(jié)點。完全二叉樹不是完全二叉樹二叉樹的分類對于完全二叉樹來說，它有以下特點：葉子結(jié)點只能出現(xiàn)在最下兩層；最下層的葉子結(jié)點一定集中在左邊連續(xù)位置；如果結(jié)點的度為1，那么該結(jié)點只有左孩子，不存在只有右孩子的情況；同樣結(jié)點數(shù)的二叉樹，完全二叉樹的深度最??；二叉樹的分類完全二叉樹與滿二叉樹的區(qū)別：滿二叉樹中每一層結(jié)點數(shù)都達到最大，沒有出現(xiàn)“缺胳膊少腿”的現(xiàn)象，在同樣深度的二叉樹中，滿二叉樹的結(jié)點最多。如果一棵深度為k的二叉樹有2k-1個結(jié)點，那么這就是一棵滿二叉樹。滿二叉樹是完全二叉樹的特殊情況，可以說滿二叉樹也是一棵完全二叉樹，但不能說完全二叉樹是滿二叉樹。二叉樹的性質(zhì)性質(zhì)1：若二叉樹的層次從

1

開始計數(shù),則，在二叉樹的第i層最多有

2i－1個結(jié)點。(i

1)4層若二叉樹的層次從

0

開始,則在二叉樹的第i

層最多有？個結(jié)點。(i

0)最多可以達到24-1個(8個)2i二叉樹的性質(zhì)性質(zhì)2：高度為

k

的二叉樹最多有2k-1個結(jié)點。性質(zhì)2推論：高度為k的二叉樹最少有?個結(jié)點。20212322利用等比數(shù)列和公式：20+21+22+…+2k-1=2k-1k二叉樹的性質(zhì)性質(zhì)3：具有n

(n

1)個結(jié)點的二叉樹的高度最多為？性質(zhì)3推論：具有n(n

1)個結(jié)點的二叉樹的高度最少為？n[log2n]＋1二叉樹的性質(zhì)性質(zhì)4：對任何一棵二叉樹,如果其葉結(jié)點有n0個,度為2的結(jié)點有n2個,則有n0＝n2＋1。

證明：若設(shè)度為1的結(jié)點有n1

個，總結(jié)點個數(shù)為

n，總邊數(shù)為

e，則根據(jù)二叉樹的定義有： n=n0+n1+n2

e=2n2+n1=n–1

因此，有： 2n2+n1=n0+n1+n2–1 n2=n0-1，n0=n2+1二叉樹的性質(zhì)性質(zhì)5：

n個結(jié)點可以組成多少種不同構(gòu)的二叉樹？二叉樹的性質(zhì)具有3個結(jié)點的不同二叉樹的棵數(shù)二叉樹的性質(zhì)性質(zhì)6：具有n

(n

1)個結(jié)點的完全二叉樹的高度為

log2n＋1完全二叉樹二叉樹的性質(zhì)性質(zhì)7：如果完全二叉樹各層次結(jié)點從1開始編號：1,2,3,…,n，則有以下關(guān)系：

①僅當(dāng)i=1時，結(jié)點i為根結(jié)點

②當(dāng)i>1時，結(jié)點i的父結(jié)點為

i/2 ③結(jié)點i的左兒子結(jié)點為2i ④結(jié)點i的右兒子結(jié)點為2i+1 ⑤若2×i>n，則結(jié)點i無左兒子

⑥若2×i＋1>n，則結(jié)點i無右兒子12348567910AHIJDEFGBCKL1211二叉樹的存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)——順序存儲結(jié)構(gòu)將二叉樹的所有結(jié)點，按照一定的次序，順序存儲到一片連續(xù)的存儲單元中。將結(jié)點編號與數(shù)組下標(biāo)進行對應(yīng)然后將二叉樹中結(jié)點存儲的數(shù)據(jù)元素存儲在一維數(shù)組對應(yīng)的位置中12348567910AHIJDEFGBCKL1211完全二叉樹的結(jié)點編號二叉樹的存儲結(jié)構(gòu)——順序存儲結(jié)構(gòu)12348567910AHIJDEFGBCKL1211ABCDEFGHIJKL123456789101112ABCDEFGHIJKL聯(lián)系性質(zhì)7：如果完全二叉樹各層次結(jié)點從1開始編號：1,2,3,…,n，則有以下關(guān)系：

①僅當(dāng)i=1時，結(jié)點i為根結(jié)點

②當(dāng)i>1時，結(jié)點i的父結(jié)點為

i/2 ③結(jié)點i的左兒子結(jié)點為2i ④結(jié)點i的右兒子結(jié)點為2i+1 ⑤若2×i>n，則結(jié)點i無左兒子

⑥若2×i＋1>n，則結(jié)點i無右兒子二叉樹的存儲結(jié)構(gòu)——順序存儲結(jié)構(gòu)12348567910AHIJDEFGBCKL1211在順序存儲中如何體現(xiàn)樹中結(jié)點間的父子關(guān)系？ABCDEFGHIJKL123456789101112ABCDEFGHIJKL二叉樹的存儲結(jié)構(gòu)——順序存儲結(jié)構(gòu)AFDEBCG123485679101211123456789101112ABCD

?E

?F

?

?

?G二叉樹的存儲結(jié)構(gòu)——順序存儲結(jié)構(gòu)二叉樹順序存儲結(jié)構(gòu)的缺點：由于必須按完全二叉樹的形式來存儲樹中的結(jié)點。將造成存儲空間的浪費（如圖）。在最壞情況下，一個只有是k個結(jié)點的右單枝樹卻需要2k-1個結(jié)點的存儲空間。13715311371531二叉樹的存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯Y(jié)構(gòu)dataleftChilddatarightChildleftChildrightChild結(jié)點結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯Y(jié)構(gòu)

ABCDFErootABCDFEroot二叉樹二叉鏈表二叉樹的存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯Y(jié)構(gòu)若二叉樹含有n個結(jié)點，則它的二叉鏈表中必含有2n個指針域，其中必有n+1個是空的鏈域?？諛洌簉oot==NULL

ABCDFEroot二叉樹的存儲結(jié)構(gòu)二叉樹結(jié)點及二叉樹的定義typedefstructNode{ DataTypedata; structNode*LChild；

structNode*RChild;}Bitnode,