第五章樹(shù)與二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)電子教案主講：楊同峰1第五章樹(shù)與二叉樹(shù)樹(shù)和森林的概念二叉樹(shù)二叉樹(shù)遍歷二叉樹(shù)的計(jì)數(shù)樹(shù)與森林堆Huffman樹(shù)2有根樹(shù)： 一棵有根樹(shù)T，簡(jiǎn)稱為樹(shù)，它是n(n≥0)

個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，T稱為空樹(shù)；否則，T

是非空樹(shù)，記作

樹(shù)和森林的概念3

r是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m(m

0)個(gè)互不相交的有限集合T1,T2,…,Tm，每個(gè)集合又是一棵樹(shù)，并且稱之為根的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。4樹(shù)的基本術(shù)語(yǔ)子女：若結(jié)點(diǎn)的子樹(shù)非空，結(jié)點(diǎn)子樹(shù)的根即為該結(jié)點(diǎn)的子女。雙親：若結(jié)點(diǎn)有子女，該結(jié)點(diǎn)是子女的雙親。1層2層4層3層depth=4DACBIJHGFEMLKheight=45兄弟：同一結(jié)點(diǎn)的子女互稱為兄弟。度：結(jié)點(diǎn)的子女個(gè)數(shù)即為該結(jié)點(diǎn)的度；樹(shù)中各個(gè)結(jié)點(diǎn)的度的最大值稱為樹(shù)的度。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)即為分支結(jié)點(diǎn)，亦稱為非終端結(jié)點(diǎn)。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，亦稱為終端結(jié)點(diǎn)。祖先：某結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的各個(gè)結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。子孫：某結(jié)點(diǎn)的所有下屬結(jié)點(diǎn)，都是該結(jié)點(diǎn)的子孫。6結(jié)點(diǎn)的層次：規(guī)定根結(jié)點(diǎn)在第一層，其子女結(jié)點(diǎn)的層次等于它的層次加一。以下類推。深度：結(jié)點(diǎn)的深度即為結(jié)點(diǎn)的層次；離根最遠(yuǎn)結(jié)點(diǎn)的層次即為樹(shù)的深度。1層2層4層3層depth=4DACBIJHGFEMLKheight=47有序樹(shù)：樹(shù)中結(jié)點(diǎn)的各棵子樹(shù)T0,T1,…是有次序的，即為有序樹(shù)。無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各棵子樹(shù)之間的次序是不重要的，可以互相交換位置。森林：森林是m（m≥0）棵樹(shù)的集合。

8二叉樹(shù)的五種不同形態(tài)LLRR二叉樹(shù)(BinaryTree)二叉樹(shù)的定義

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。9二叉樹(shù)的性質(zhì)性質(zhì)1

若二叉樹(shù)結(jié)點(diǎn)的層次從1開(kāi)始,則在二叉樹(shù)的第i層最多有

2i-1

個(gè)結(jié)點(diǎn)。(i≥1)

[證明用數(shù)學(xué)歸納法]性質(zhì)2

深度為k

的二叉樹(shù)最少有k

個(gè)結(jié)點(diǎn)，最多有2k-1個(gè)結(jié)點(diǎn)。(k≥1)

因?yàn)槊恳粚幼钌僖?個(gè)結(jié)點(diǎn)，因此，最少結(jié)點(diǎn)數(shù)為k。最多結(jié)點(diǎn)個(gè)數(shù)借助性質(zhì)1：用求等比級(jí)數(shù)前k項(xiàng)和的公式

20+21+22+…+2k-1=2k-110性質(zhì)3

對(duì)任何一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)有n0個(gè),度為2的非葉結(jié)點(diǎn)有n2個(gè),則有

n0＝n2＋1

若設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)數(shù)為n， 總邊數(shù)為e，則根據(jù)二叉樹(shù)的定義，

n=n0+n1+n2

e

=2n2+n1=n-1

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

n2=n0-1n0=n2+111定義1

滿二叉樹(shù)(FullBinaryTree)

定義2

完全二叉樹(shù)(CompleteBinaryTree)─若設(shè)二叉樹(shù)的深度為k，則共有k層。除第k層外，其它各層(1～k-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。12理想平衡二叉樹(shù)13性質(zhì)4

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

設(shè)完全二叉樹(shù)的深度為k，則有

2k-1-1<n

≤2k-1

變形2k-1<n+1≤2k

取對(duì)數(shù)

k-1<log2(n+1)≤k

有

log2(n+1)=k上面k-1層結(jié)點(diǎn)數(shù)包括第k層的最大結(jié)點(diǎn)數(shù)23-124-114性質(zhì)5

如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1,2,…,n，則有以下關(guān)系：

若i=1,則i無(wú)雙親若i>1,則i的雙親為i／2若2*i<=n,則i的左子女為

2*i， 若2*i+1<=n,則i的右子女為2*i+1若i為奇數(shù),且i!=1,

則其左兄弟為i-1若

i為偶數(shù),且i!=n,

則其右兄弟為i+11234856791015完全二叉樹(shù)一般二叉樹(shù)的順序表示的順序表示二叉樹(shù)的順序表示1123456789

10

1412346789

12

14248910567312376489125101113161371531極端情形:只有右單支的二叉樹(shù)137153117二叉樹(shù)結(jié)點(diǎn)定義：每個(gè)結(jié)點(diǎn)有3個(gè)數(shù)據(jù)成員，data域存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)，leftChild和rightChild分別存放指向左子女和右子女的指針。leftChilddatarightChilddataleftChildrightChild二叉鏈表二叉樹(shù)的鏈表表示（二叉鏈表）18leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表二叉樹(shù)的鏈表表示（三叉鏈表）每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親的指針parent，使得查找雙親也很方便。19二叉樹(shù)鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉樹(shù)二叉鏈表三叉鏈表20二叉樹(shù)遍歷二叉樹(shù)的遍歷就是按某種次序訪問(wèn)樹(shù)中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。設(shè)訪問(wèn)根結(jié)點(diǎn)記作

V

遍歷根的左子樹(shù)記作

L

遍歷根的右子樹(shù)記作

R則可能的遍歷次序有

前序VLR

鏡像VRL

中序

LVR

鏡像RVL

后序LRV

鏡像RLV21中序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù)(L)；訪問(wèn)根結(jié)點(diǎn)(V)；中序遍歷右子樹(shù)(R)。遍歷結(jié)果

a+b*c

-

d

-

e/f中序遍歷(InorderTraversal)--/+*abcdef22前序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)(V)；前序遍歷左子樹(shù)(L)；前序遍歷右子樹(shù)(R)。遍歷結(jié)果

-+a*b

-

cd/ef前序遍歷(PreorderTraversal)--/+*abcdef23后序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則后序遍歷左子樹(shù)(L)；后序遍歷右子樹(shù)(R)；訪問(wèn)根結(jié)點(diǎn)(V)。遍歷結(jié)果

abcd

-*+ef/-后序遍歷(PostorderTraversal)--/+*abcdef24由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)。例,前序序列{ABHFDECKG}

和中序序列{HBDFAEKCG

},構(gòu)造二叉樹(shù)過(guò)程如下：HBDFEKCGAEKCGABHDF25前序序列{ABHFDECKG}，和中序序列{HBDFAEKCG

}KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG26樹(shù)的存儲(chǔ)表示樹(shù)與森林27子女-兄弟表示也稱為樹(shù)的二叉樹(shù)表示。結(jié)點(diǎn)構(gòu)造為：firstChild

指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無(wú)序樹(shù)時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。nextSibling

指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在存儲(chǔ)時(shí)總是有順序的。若想找某結(jié)點(diǎn)的所有子女，可先找firstChild,再反復(fù)用nextSibling

沿鏈掃描。

datafirstChildnextSibling28樹(shù)的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE29樹(shù)的遍歷深度優(yōu)先遍歷先根次序遍歷后根次序遍歷廣度優(yōu)先遍歷30樹(shù)的先根次序遍歷當(dāng)樹(shù)非空時(shí)訪問(wèn)根結(jié)點(diǎn)依次先根遍歷根的各棵子樹(shù)31樹(shù)的后根次序遍歷當(dāng)樹(shù)非空時(shí)依次后根遍歷根的各棵子樹(shù)訪問(wèn)根結(jié)點(diǎn)32樹(shù)的廣度優(yōu)先（層次次序）遍歷分層次進(jìn)行33森林廣度優(yōu)先遍歷（層次序遍歷）若森林F

為空，返回； 否則依次遍歷各棵樹(shù)的 根結(jié)點(diǎn)；依次遍歷各棵樹(shù)根 結(jié)點(diǎn)的所有子女；依次遍歷這些子女 結(jié)點(diǎn)的子女結(jié)點(diǎn)；34完全二叉樹(shù)順序表示

Ki≤K2i+1&&

Ki≤K2i+2完全二叉樹(shù)順序表示Ki≥K2i+1&&

Ki≥K2i+2090987877878454565653131532323531717堆的定義35堆的元素下標(biāo)計(jì)算由于堆存儲(chǔ)在下標(biāo)從0開(kāi)始計(jì)數(shù)的一維數(shù)組中，因此在堆中給定下標(biāo)為i

的結(jié)點(diǎn)時(shí)如果

i=0，結(jié)點(diǎn)i

是根結(jié)點(diǎn)，無(wú)雙親；否則結(jié)點(diǎn)i

的父結(jié)點(diǎn)為結(jié)點(diǎn)(i-1)/2)；如果2i+1＞n-1，則結(jié)點(diǎn)i

無(wú)左子女；否則結(jié)點(diǎn)i

的左子女為結(jié)點(diǎn)2i+1；如果2i+2＞n-1，則結(jié)點(diǎn)i無(wú)右子女；否則結(jié)點(diǎn)i的右子女為結(jié)點(diǎn)

2i+2。36最小堆調(diào)整算法首先找到最后一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，設(shè)其為k依次對(duì)i=k，i=k-1，….，i=0進(jìn)行shiftdown下滑調(diào)整算法，操作范圍包括所有隸屬于i結(jié)點(diǎn)的子孫結(jié)點(diǎn)下滑時(shí)依據(jù)子女結(jié)點(diǎn)的關(guān)鍵碼值確定方向（沿關(guān)鍵碼值小的一側(cè)子女結(jié)點(diǎn)下滑）37自下向上逐步調(diào)整為最小堆currentPos=i=3currentPos=i=25353171778780923456587i0923456587i將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆38currentPos=i=15353171778780923456587i0923456587i39currentPos=i=05353171778780923456587i0923456587i09405353171778780923456587i0923456587i1741

每次插入都加在堆的最后，再自下向上執(zhí)行調(diào)整，使之重新形成堆。最小堆的插入42在堆中插入新元素1153171778780923456587i0923456587j1153j1123i最小堆的向上調(diào)整（shiftup）從下向上和父結(jié)點(diǎn)比較435317117878094565870923456587j115323i2317ji44Huffman樹(shù)路徑長(zhǎng)度(PathLength)

路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的分支構(gòu)成兩結(jié)點(diǎn)間的路徑兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度PL

是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)451122334455667788PL=0+1+1+2+2+2+2+3=13PL=0+1+1+2+2+3+3+4=1646帶權(quán)路徑長(zhǎng)度

(WeightedPathLength,WPL)在很多應(yīng)用問(wèn)題中為樹(shù)的葉結(jié)點(diǎn)賦予一個(gè)權(quán)值，用于表示出現(xiàn)頻度、概率值等。因此，在問(wèn)題處理中把葉結(jié)點(diǎn)定義得不同于非葉結(jié)點(diǎn)，把葉結(jié)點(diǎn)看成“外結(jié)點(diǎn)”，非葉結(jié)點(diǎn)看成“內(nèi)結(jié)點(diǎn)”。這樣的二叉樹(shù)稱為擴(kuò)充二叉樹(shù)。47若一棵擴(kuò)充二叉樹(shù)有n個(gè)外結(jié)點(diǎn)，第i個(gè)外結(jié)點(diǎn)的權(quán)值為wi，它到根的路徑長(zhǎng)度為li，則該外結(jié)點(diǎn)到根的帶權(quán)路徑長(zhǎng)度為wi*li。擴(kuò)充二叉樹(shù)的帶權(quán)路徑長(zhǎng)度定義為樹(shù)的各外結(jié)點(diǎn)到根的帶權(quán)路徑長(zhǎng)度之和。對(duì)于同樣一組權(quán)值，如果放在外結(jié)點(diǎn)上，組織方式不同，帶權(quán)路徑長(zhǎng)度也不同。48具有不同帶權(quán)路徑長(zhǎng)度的擴(kuò)充二叉樹(shù)WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=4