數(shù)據(jù)結(jié)構(gòu)-基于C++語言（微課版） 課件 1-3 二叉樹的邏輯模型

滿二叉樹；完全二叉樹；本節(jié)目錄：本節(jié)內(nèi)容：二叉樹的基本性質(zhì)樹與二叉樹的邏輯模型二叉樹中結(jié)點(diǎn)個(gè)數(shù)與層次的關(guān)系；樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)1：二叉樹的第i層上至多有2i-1(i≥1)個(gè)結(jié)點(diǎn)。ABDDBACEBADCFC第2層個(gè)數(shù)：2、1、2第3層個(gè)數(shù)：1、2、3第1層個(gè)數(shù)：1、1、1深度為3的二叉樹樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)1：二叉樹的第i層上至多有2i-1(i≥1)個(gè)結(jié)點(diǎn)。ACBEFFGDFFDFDFD11層次個(gè)數(shù)2

23

44

8第5層上最多幾個(gè)結(jié)點(diǎn)？5

16樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)1：二叉樹的第i層上至多有2i-1(i≥1)個(gè)結(jié)點(diǎn)。ACBEFFGDFFDFDFDEBADGCF第4層8個(gè)結(jié)點(diǎn)樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)2：二叉樹的第i層上至多有2i-1(i≥1)個(gè)結(jié)點(diǎn)。證明：當(dāng)i=1時(shí)：只有一個(gè)根結(jié)點(diǎn)2i-1

=20=1，命題成立。

假設(shè)對i>1時(shí)，處在第i-1層上至多有2(i-1)-1個(gè)結(jié)點(diǎn)。歸納知第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度最大為2，故在第i層上最大結(jié)點(diǎn)數(shù)為第i-1層上最大結(jié)點(diǎn)數(shù)的2倍。即2×2i-2＝2i-1

ACBEFFGDFFDFDFD樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)2：深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)(h>=1)。ACBEFFGDFFDFDFD11深度總數(shù)2

33

74

15深度5，最多幾個(gè)結(jié)點(diǎn)？5

31樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)2：深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)(h>=1)。ACBEFFGDFFDFDFD證明：設(shè)第i層的結(jié)點(diǎn)數(shù)為xi，那么由性質(zhì)1可以知道，第i層至少有一個(gè)結(jié)點(diǎn)，最多有2i-1結(jié)點(diǎn)，即1≤xi≤2i-1，深度為h的二叉樹的結(jié)點(diǎn)數(shù)為M，則有：M=20+20+…+2i-1=2h-1樹與二叉樹的邏輯模型滿二叉樹：深度為h且含有2h-1個(gè)結(jié)點(diǎn)的二叉樹。

結(jié)點(diǎn)編號是自上至下、自左至右。特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值，葉子結(jié)點(diǎn)均在最底一層。152384796101112131415樹與二叉樹的邏輯模型完全二叉樹：一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按與滿二叉樹相同的編號方式對結(jié)點(diǎn)進(jìn)行編號，若樹中n個(gè)結(jié)點(diǎn)和滿二叉樹1～n編號完全一致。152384796101112樹與二叉樹的邏輯模型非完全二叉樹1523847961011小結(jié)：理解特殊二叉樹特點(diǎn)；特殊二叉樹判定條件；本節(jié)內(nèi)容：二叉樹的基本性質(zhì)樹與二叉樹的邏輯模型根區(qū)分一般、特殊二叉樹。152384796深度與個(gè)數(shù)的關(guān)系；不同度的結(jié)點(diǎn)間個(gè)數(shù)關(guān)系。本節(jié)目錄：本節(jié)內(nèi)容：二叉樹的基本性質(zhì)樹與二叉樹的邏輯模型樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)3：n個(gè)結(jié)點(diǎn)的完全二叉樹深度為：[㏒2n]+1。設(shè)完全二叉樹的深度為h，則二叉樹結(jié)點(diǎn)個(gè)數(shù)多有：？最少有：？樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)3：n個(gè)結(jié)點(diǎn)的完全二叉樹深度為：[㏒2n]+1。設(shè)完全二叉樹的深度為h，則根據(jù)性質(zhì)2及完全二叉樹的定義有：2h-1≦n≦2h-1或2h-1≦n<2h

取對數(shù)得：h-1<㏒2n<h因?yàn)閔是整數(shù)?！鄅=㏒2n+115238479610樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)4：在任意二叉樹中，若有n0個(gè)葉子結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則必有：n0=n2+1。DBACEBADCF樹與二叉樹的邏輯模型二叉樹性質(zhì):性質(zhì)4：在任意二叉樹中，若有n0個(gè)葉子結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則必有：n0=n2+1。DBACEBADCF證明：設(shè)n1為度為1的結(jié)點(diǎn)，則結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2；又分支總數(shù)為：b=n1+2n2；

分支總數(shù)：b=n-1；所以:n0=n2+1。性質(zhì)5：若對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(深度為

㏒2n

+1)的結(jié)點(diǎn)按層（從第1層到第

㏒2n

+1層)序自左至右進(jìn)行編號,父