第06章-樹(shù)與二叉樹(shù)A

第1章緒論第2章線性表第3章棧和隊(duì)列

第4章串第5章數(shù)組和廣義表第6章

樹(shù)和二叉樹(shù)

第7章圖第9章查找第10章排序目錄1

教

學(xué)

內(nèi)

容1、樹(shù)的基本概念2、二叉樹(shù)的定義、性質(zhì)及運(yùn)算；3、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)4、遍歷二叉樹(shù)5、線索二叉樹(shù)6、樹(shù)、森林、森林與二叉樹(shù)的轉(zhuǎn)換7、哈夫曼樹(shù)、哈夫曼編碼2樹(shù)型結(jié)構(gòu)（非線性結(jié)構(gòu)）結(jié)點(diǎn)之間有分支具有層次關(guān)系生活中的哪些實(shí)例是樹(shù)型結(jié)構(gòu)呢？例自然界:樹(shù)人類社會(huì)家譜院系組織機(jī)構(gòu)36.1樹(shù)的基本概念

樹(shù)的定義

樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集。若n=0，稱為空樹(shù)；若n>0，則它滿足如下兩個(gè)條件：有且僅有一個(gè)稱之為根(Root)的結(jié)點(diǎn)。當(dāng)n>1，除根以外的其它結(jié)點(diǎn)分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每個(gè)集合又是一棵符合本定義的樹(shù)，并且稱為根的子樹(shù)。4ACGBDEFKLHMIJ例如A只有根結(jié)點(diǎn)的樹(shù)有13個(gè)結(jié)點(diǎn)的樹(shù)A是根；其余數(shù)據(jù)元素分成三個(gè)互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹(shù)，且本身也是一棵樹(shù)。根結(jié)點(diǎn)T15T2T3R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>,<H,M>}ACGBDEFKLHMIJ6線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)存在唯一的沒(méi)有前驅(qū)的“首元素”存在唯一的沒(méi)有前驅(qū)的“根結(jié)點(diǎn)”存在唯一的沒(méi)有后繼的“尾元素”存在多個(gè)沒(méi)有后繼的“葉子”其余元素均存在唯一的“前驅(qū)元素”和唯一的“后繼元素”其余結(jié)點(diǎn)均存在唯一的“前驅(qū)（雙親）結(jié)點(diǎn)”和多個(gè)“后繼（孩子）結(jié)點(diǎn)”樹(shù)結(jié)構(gòu)和線性結(jié)構(gòu)作如下對(duì)照：7樹(shù)的基本術(shù)語(yǔ)1層2層4層3層height=4ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度葉子結(jié)點(diǎn)分支結(jié)點(diǎn)兒子結(jié)點(diǎn)父親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)樹(shù)的度結(jié)點(diǎn)的層次樹(shù)的深度森林89樹(shù)的基本術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹(shù)的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)ABCGEIDHFJMLK

根葉子森林有序樹(shù)無(wú)序樹(shù)——即根結(jié)點(diǎn)(沒(méi)有前驅(qū))——即終端結(jié)點(diǎn)(沒(méi)有后繼)——指m棵不相交的樹(shù)的集合(例如刪除A后的子樹(shù)個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹(shù)可互換位置?！礃?shù)的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹(shù)數(shù)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹(shù)的度樹(shù)的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問(wèn)：右上圖中的結(jié)點(diǎn)數(shù)＝；樹(shù)的度＝；樹(shù)的深度＝1334（有幾個(gè)直接后繼就是幾度，亦稱“次數(shù)”）10ABCDEFGHIJKLM結(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為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先1112樹(shù)的性質(zhì)：性質(zhì)1：樹(shù)中的節(jié)點(diǎn)數(shù)n等于所有節(jié)點(diǎn)的度數(shù)加1（在一顆樹(shù)中，度之和=分支數(shù)，而分支數(shù)=n-1）性質(zhì)2：度為m的樹(shù)中第i層上至多有mi-1個(gè)節(jié)點(diǎn)(i≥1)性質(zhì)3：高度為h的度為m的樹(shù)至多有個(gè)節(jié)點(diǎn)。性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的度為m的樹(shù)的最小高度為

。13練習(xí)題：題目：一顆度為4的樹(shù)中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)度為1的節(jié)點(diǎn)，則該樹(shù)的葉子節(jié)點(diǎn)為

（）A.41 B.81 C.113 D.122解答：樹(shù)中只能有度為0,1,2,3,4的節(jié)點(diǎn)。所有節(jié)點(diǎn)和為n=n0+n1+n2+n3+n4。而度之和=n-1，并且度之和=1×n1+2×n2+3×n3+4×n4=1×10+2×1+3×10+4×20=122。則n=122+1=123n0=n-n1-n2-n3-n4=122-41=81。本題答案為（B）14求解樹(shù)的節(jié)點(diǎn)個(gè)數(shù)問(wèn)題：對(duì)于度為m的樹(shù)，在n,n0,n1,n2,…,nm中只有兩個(gè)參數(shù)未知時(shí)，一般可以求出這兩個(gè)值。求解過(guò)程如下：n=n0+n1+n2+…+nm度之和=n-1度之和=n1+2n2+…+mnm所以有n=n1+2n2+…+mnm+1=n0+n1+n2+…+nm例如：若一顆有n個(gè)節(jié)點(diǎn)的樹(shù)，其中所有分支節(jié)點(diǎn)的度均為k，求該樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)。顯然，m=k,n2=n3=…=nm-1=0,則n=n0+nk,度之和=n-1=knk,nk=(n-1)/k,所以

n0=n-nk=n–(n-1)/k.有序樹(shù)子樹(shù)之間存在確定的次序關(guān)系無(wú)序樹(shù)子樹(shù)之間不存在確定的次序關(guān)系家族樹(shù)就屬于有序樹(shù)。15森林是m(m≥0)棵互不相交的樹(shù)的集合root給森林中的各子樹(shù)加上一個(gè)父親結(jié)點(diǎn),森林就變成了樹(shù)。

T3T2T1ABEFKLDHMIJCGCG16

二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交叉的二叉樹(shù)組成。6.2二叉樹(shù)BDEGHCILFA根結(jié)點(diǎn)右子樹(shù)左子樹(shù)17為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。(a)空二叉樹(shù)(b)根和空的左右子樹(shù)(c)根和左子樹(shù)(d)根和右子樹(shù)(e)根和左右子樹(shù)

注：雖然二叉樹(shù)與樹(shù)概念不同，但有關(guān)樹(shù)的基本術(shù)語(yǔ)對(duì)二叉樹(shù)都適用。二叉樹(shù)的五種基本形態(tài)18由n個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹(shù)的形態(tài)總數(shù)為方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹(shù)轉(zhuǎn)二叉樹(shù)舉例：abeidfhgc兄弟相連長(zhǎng)兄為父孩子靠左特點(diǎn)是？根結(jié)點(diǎn)沒(méi)有右孩子！19討論：二叉樹(shù)怎樣還原為樹(shù)？abeidfhgc要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgic20

性質(zhì)1

在二叉樹(shù)的第i層上至多有2i－1個(gè)結(jié)點(diǎn)。(i1)證明：當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，2i-1=20=1。假設(shè)對(duì)所有j，i>j1，命題成立，即第j層上至多有2j-1

個(gè)結(jié)點(diǎn)。由歸納假設(shè)第i-1層上至多有2i－2個(gè)結(jié)點(diǎn)。二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度至多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2*2i－2=2i-1。二叉樹(shù)的重要特性21

性質(zhì)2

深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)，其中k1。

證明：由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為＝20+21+…+2k-1=2k-122

性質(zhì)3

對(duì)任何一棵二叉樹(shù)T,如果其葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0＝n2＋1。證明：n=n0+n1+n2

①

e=n–1=2n2+n1

②因此，2n2+n1=n0+n1+n2-1

n0=n2+1

23設(shè)e為樹(shù)的分支總數(shù)，則e=n-1。這些分支由度為1或2的節(jié)點(diǎn)射出，所以：滿二叉樹(shù)(FullBinaryTree)

定義1

:

一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。兩種特殊形態(tài)的二叉樹(shù)754389101113141512126特點(diǎn):每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大,葉子全部在最底層24非完全二叉樹(shù)完全二叉樹(shù)(CompleteBinaryTree)

若設(shè)二叉樹(shù)的深度為h，除第h層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大值，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)。完全二叉樹(shù)621543BACDEGF25

性質(zhì)4

具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2(n)＋1。

證明：設(shè)完全二叉樹(shù)的深度為h，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有2h-1-1<n2h

-1,即2h-1n<2h，取對(duì)數(shù)h－1log2n<h，又h是整數(shù)，因此有h=log2(n)

＋126性質(zhì)5

若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：621543245361哪個(gè)是完全二叉樹(shù)27(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，否則，編號(hào)為i/2的結(jié)點(diǎn)為其父親結(jié)點(diǎn)。(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子

結(jié)點(diǎn)。2829節(jié)點(diǎn)i和i+1在同一層上i+12i+22i+3i2i+12ii2i2i+1i+12i+3i/2

2i+2節(jié)點(diǎn)i和i+1不在同一層上二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹(shù)的順序存儲(chǔ)表示6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)30順序存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的數(shù)據(jù)元素。將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1的分量中

BACEDFGHIJKLMNO31BACEDFGHIJ123456710891練習(xí)32

ABDCEF

012345ABCDEF24163