數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο笳Z言描述-殷人昆-第五章

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

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

是非空樹，記作

樹和森林的概念3

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

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

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

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

若二叉樹結(jié)點的層次從1開始,則在二叉樹的第i層最多有

2i-1

個結(jié)點。(i≥1)

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

深度為k

的二叉樹最少有k

個結(jié)點，最多有2k-1個結(jié)點。(k≥1)

因為每一層最少要有1個結(jié)點，因此，最少結(jié)點數(shù)為k。最多結(jié)點個數(shù)借助性質(zhì)1：用求等比級數(shù)前k項和的公式

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

對任何一棵二叉樹，如果其葉結(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-1n0=n2+111定義1

滿二叉樹(FullBinaryTree)

定義2

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

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

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

2k-1-1<n

≤2k-1

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

取對數(shù)

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

有

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

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

若i=1,則i無雙親若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完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的順序表示1123456789

10

1412346789

12

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

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

R則可能的遍歷次序有

前序VLR

鏡像VRL

中序

LVR

鏡像RVL

后序LRV

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

a+b*c

-

d

-

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

-+a*b

-

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

abcd

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

和中序序列{HBDFAEKCG

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

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

指向該結(jié)點的第一個子女結(jié)點。無序樹時，可任意指定一個結(jié)點為第一個子女。nextSibling

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

沿鏈掃描。

datafirstChildnextSibling28樹的子女-

兄弟表示

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

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

Ki≤K2i+1&&

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

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

的結(jié)點時如果

i=0，結(jié)點i

是根結(jié)點，無雙親；否則結(jié)點i

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

無左子女；否則結(jié)點i

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

2i+2。36最小堆調(diào)整算法首先找到最后一個結(jié)點的父結(jié)點，設(shè)其為k依次對i=k，i=k-1，….，i=0進行shiftdown下滑調(diào)整算法，操作范圍包括所有隸屬于i結(jié)點的子孫結(jié)點下滑時依據(jù)子女結(jié)點的關(guān)鍵碼值確定方向（沿關(guān)鍵碼值小的一側(cè)子女結(jié)點下滑）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é)點比較435317117878094565870923456587j115323i2317ji44Huffman樹路徑長度(PathLength)

路徑：從樹中一個結(jié)點到另一個結(jié)點的分支構(gòu)成兩結(jié)點間的路徑兩個結(jié)點之間的路徑長度PL

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

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