第10講 樹和二叉樹的定義

主講人：陳紅麗第6章樹和二叉樹1本章內(nèi)容本章是重點章，二叉樹又是本章的重點內(nèi)容，我們要熟悉樹的定義和相關(guān)術(shù)語，熟悉二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷，樹的存儲結(jié)構(gòu)、遍歷，樹、森林與二叉樹的轉(zhuǎn)換，根據(jù)遍歷序列畫二叉樹，哈夫曼樹及哈夫曼編碼等內(nèi)容。算法的重點是二叉樹的遍歷及其有關(guān)應(yīng)用。2第10講樹和二叉樹的定義

主講人：陳紅麗3對比線性結(jié)構(gòu)和樹型結(jié)構(gòu)的結(jié)構(gòu)特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

(無前驅(qū))最后一個數(shù)據(jù)元素

(無后繼)多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)（雙親）多個后繼（孩子）)4樹的定義樹是n（n≥0）個結(jié)點的有限集合，在任一棵非空樹中：

(1)有且僅有一個稱為根(root)的結(jié)點。

(2)其余結(jié)點可分為m個互不相交的集

合，而且其中的每一個集合本身又是

一棵樹，稱為根的子樹。ABCDEFGHIJMKL注意：樹的定義具有

遞歸性，即樹

的定義中還有

樹。5樹的抽象數(shù)據(jù)類型的定義（自己看！）ADTTree{

數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系：

若D為空集，則稱為空樹；

若D中僅含一個數(shù)據(jù)元素，則關(guān)系R為空集；

否則R={H}，

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)當(dāng)n>1時，其余數(shù)據(jù)元素可分為m(m>0)個互不相交的(非空)有限集T1,T2,…,Tm,其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹，每一棵子樹的根xi都是根root的后繼，即<root,xi>∈H,i=1,2,…,m。

基本操作：}ADTTree6結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支擁有子樹的個數(shù)樹中所有結(jié)點的度的最大值度為0的結(jié)點度大于零的結(jié)點DHIJM樹的基本術(shù)語7(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟結(jié)點祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：由從根到該結(jié)點所經(jīng)分支和結(jié)點元素構(gòu)成ABCDEFGHIJMKL規(guī)定根結(jié)點為第1層，其它所有結(jié)點的層都是其父結(jié)點的層號加1樹中葉子結(jié)點所在的最大層次空樹深度為0非空樹深度等于子樹深度的最大值加1。8任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合。m=0：空集；m=1：樹

ArootBCDEFGHIJMKLF有序樹、無序樹：左右結(jié)點是否等價9ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先10樹的邏輯結(jié)構(gòu)

(特點)：一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且子樹之間互不相交。樹的存儲結(jié)構(gòu)

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？

——仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒有實用價值）。討論2：樹的順序存儲方案應(yīng)該怎樣制定？11討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可用多重鏈表：一個前驅(qū)指針，n個后繼指針。細(xì)節(jié)問題：樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？

即應(yīng)該設(shè)計成“等長”還是“不等長”？缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）解決思路：先研究最簡單、最有規(guī)律的樹狀結(jié)構(gòu)，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。二叉樹12二叉樹定義或為空樹，或是由一個根結(jié)點和兩棵互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。特性二叉樹中每個結(jié)點最多有兩棵子樹，即二叉樹每個結(jié)點的度小于等于2子樹有左右之分，不能顛倒——有序樹二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念二叉樹與度為2的樹相同嗎？為什么？？ABCDEFGHK根結(jié)點左子樹右子樹13ADTBinaryTree{

數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系：

若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dl∩Dr=Φ//關(guān)于子樹不相交的說明③……//關(guān)于二元關(guān)系的說明

④……

//關(guān)于左子樹和右子樹的說明

基本操作：}ADTBinaryTree

二叉樹的抽象數(shù)據(jù)類型的定義（自己看）14二叉樹的基本形態(tài)根左子樹根根右子樹根右子樹左子樹(a)空二叉樹

(b)只有根結(jié)點的二叉樹

(c)左右子樹都非空的二叉樹

(e)左子樹為空的二叉樹

(d)右子樹為空的二叉樹15問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？并畫出不同形態(tài)的二叉樹。

答：有5種16二叉樹的性質(zhì)（3+2）討論1：第i層的結(jié)點數(shù)至多是多少？

（利用二叉樹的特性可輕松求出）

性質(zhì)1:

在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）。性質(zhì)2:

深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。2i-1個問題：第i層上至少有

個結(jié)點？1討論2：深度為k的二叉樹，至多有多少個結(jié)點？

（利用二叉樹的特性可輕松求出）2k-1問題：深度為k時至少有

個結(jié)點？k17討論3：二叉樹的葉子數(shù)n0和度為2的結(jié)點數(shù)n2之間有

關(guān)系嗎？性質(zhì)3:

對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，

則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹中全部結(jié)點數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點數(shù)＋2度結(jié)點數(shù))又∵二叉樹中全部結(jié)點數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點)

（除根結(jié)點外，每個結(jié)點必有且僅有一個直接前趨，即一個分支進入）而總分支數(shù)B=n1+2n2(1度結(jié)點必有1個直接后繼，2度結(jié)點必有2個)三式聯(lián)立可得：

n0+n1+n2=

n1+2n2+1,即n0=n2+1實際意義：葉子數(shù)＝2度結(jié)點數(shù)＋1ABCGEIDHFJ18在一棵度為3的樹中，若有2個度為3的結(jié)點，有1個度為2的結(jié)點，則有

個度為0的結(jié)點。

A．4B．5

C．6

D．7C19兩類特殊的二叉樹滿二叉樹完全二叉樹深度為k且有2k-1個結(jié)點（特點：每層都“充滿”了結(jié)點）深度為k，前k-1層是滿二叉樹，第k層的結(jié)點從左至右依次排列。123114589121367101415123114589126710結(jié)點層序編號：從根結(jié)點起自上而下逐層（層內(nèi)自左至右）對二叉樹的結(jié)點進行連續(xù)編號。20性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為()。假設(shè)該完全二叉樹的深度為k，則根據(jù)完全二叉樹的定義和性質(zhì)2有：

2k-1≤n＜2k

所以有：k－1≤log2n＜k

又因為k是整數(shù)，所以，k＝log2n＋1log2n＋1深度為K的完全二叉樹結(jié)點數(shù)是（）2k-1-1<n≤

2k-121性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點

i(1≤i≤n)，有：1、如果i=1，則結(jié)點

i是二叉樹的根，無雙親；如果

i>1，則其雙親是（）結(jié)點2、如果

2i>n，則結(jié)點

i無左孩子，為葉結(jié)點；否則其左孩子是結(jié)點（）。3、如果

2i+1>n，則結(jié)點

i無右孩子；否則其右孩子是結(jié)點（）。i/22i2i+122習(xí)題：設(shè)一棵完全二叉樹具有1000個結(jié)點，則它有

個葉子結(jié)點，有

個度為2的結(jié)點，有

個結(jié)點只有非空左子樹，有

個結(jié)點只有非空右子樹。10解：1）由于完全二叉樹中最多只能出現(xiàn)右孩子為空的1個結(jié)點，所以度為1的結(jié)點有0個或1個2）由于二叉樹中