第7章 樹形結(jié)構(gòu)

第七章樹和二叉樹7.1-2 樹和二叉樹的概念與性質(zhì)7.3 二叉樹的存儲結(jié)構(gòu)7.4 二叉樹的操作算法7.6-7 線索二叉樹的操作算法樹、森林與二叉樹的轉(zhuǎn)換7.8 樹的應(yīng)用---Huffman編碼決策分析小王是一家著名高爾夫俱樂部的經(jīng)理。但是他被雇員數(shù)量問題搞得心情十分不好。某些天好像所有人都來玩高爾夫，以至于所有員工都忙的團團轉(zhuǎn)還是應(yīng)付不過來，而有些天不知道什么原因卻一個人也不來，俱樂部為雇員數(shù)量浪費了不少資金。小王的目的是通過下周天氣預(yù)報尋找什么時候人們會打高爾夫，以適時調(diào)整雇員數(shù)量。因此首先他必須了解人們決定是否打球的原因。在2周時間內(nèi)我們得到以下記錄:

天氣狀況（sun）有晴，云和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風(fēng)。當(dāng)然還有顧客是不是在這些日子光顧俱樂部。最終他得到了14行5列的數(shù)據(jù)表格：樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹結(jié)構(gòu)第一個數(shù)據(jù)元素根結(jié)點（只有一個）無前驅(qū)無雙親最后一個數(shù)據(jù)元素葉子結(jié)點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點一個前驅(qū),一個后繼一個雙親,多個孩子一對一一對多樹的邏輯結(jié)構(gòu)7.1樹的基本概念

7.1.1樹的定義

7.1.3樹的基本術(shù)語7.1.2樹的表示7.1.1樹的定義：核心關(guān)系：層次關(guān)系。

樹：n（n≥0）個結(jié)點的有限集合。當(dāng)n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴

有且僅有一個特定的稱為根的結(jié)點；⑵

當(dāng)n＞1時，除根結(jié)點之外的其余結(jié)點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。1.1通俗定義樹形表示法廣義表表示法a(b(e,f,g),c(h),d(i,j))樹是n(n>0)個結(jié)點的有限集，在任意一棵樹中：1有且只有一個特定的根(root)結(jié)點；2當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限子集T1,T2...Tm，每個子集是一棵樹，稱為子樹。判斷以下是否為樹型結(jié)構(gòu)7.1.3樹的基本術(shù)語

1.樹的結(jié)點：包含一個數(shù)據(jù)元素和指向其子樹的所有分支。

2.結(jié)點的度：一個結(jié)點擁有的子樹的個數(shù)。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非終端結(jié)點,又叫分支結(jié)點。度為零的結(jié)點稱為終端結(jié)點或葉結(jié)點。4.樹的度：樹中所有結(jié)點的度的最大值max(D(I))。含義：樹中最大分支數(shù)為樹的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

樹形表示法

樹的度：3結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第k+1層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC樹的基本術(shù)語 5.CBDEFKLHJA71234568910層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。樹的基本術(shù)語有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹

樹的基本術(shù)語 6.ACBGFEDACBGFEDCBDEFKLHJ森林：m(m≥0)棵互不相交的樹的集合。

樹的基本術(shù)語 7.A路徑：如果樹的結(jié)點序列n1,n2,…,nk有如下關(guān)系：則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。CGBDEFKLHMIJA樹的基本術(shù)語 8.祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先，而y稱為x的子孫。CGBDEFKLHMIJA樹的基本術(shù)語 9.

總結(jié)基本術(shù)語的理解：結(jié)點的度：一個結(jié)點含有的子樹的個數(shù)稱為該結(jié)點的度；如結(jié)點D含有3個子樹，則結(jié)點D的度為3，而結(jié)點C的度為1，結(jié)點K的度為0。葉結(jié)點或終端結(jié)點：度為零的結(jié)點稱為葉結(jié)點；如結(jié)點F的度為0，則為葉子結(jié)點。非終端結(jié)點或分支結(jié)點：度不為零的結(jié)點；

雙親結(jié)點（父結(jié)點）：含有孩子的結(jié)點稱為其孩子的雙親結(jié)點；例如，結(jié)點B是E,F的雙親結(jié)點（父結(jié)點）。孩子結(jié)點：一個結(jié)點子樹的根結(jié)點稱為該結(jié)點的孩子結(jié)點；例如，結(jié)點B的孩子結(jié)點有E,F兩個。兄弟結(jié)點：具有相同雙親結(jié)點的結(jié)點互稱為兄弟結(jié)點；如E,F互為兄弟結(jié)點。CGBDEFKLHMIJA

總結(jié)基本術(shù)語的理解：樹的度：一棵樹中，最大的結(jié)點的度稱為樹的度；結(jié)點的層次：從根開始定義起，根為第一層，根的孩子為第二層；

樹的高度或深度：樹中結(jié)點的最大層次；堂兄弟：雙親在同一層的結(jié)點互為堂兄弟；

結(jié)點的祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點；子孫：以某結(jié)點為根的子樹中任一結(jié)點都稱為該結(jié)點的子孫。森林：由m（m>=0）棵互不相交的樹的集合稱為森林；CGBDEFKLHMIJA1.有一棵樹如圖所示，回答下面的問題（1）這棵樹的葉子結(jié)點是___________。（2）結(jié)點k3的度是______________（3）這棵樹的度是_____________（4）這棵樹的深度是____________（5）結(jié)點k3的孩子結(jié)點是___________（6）這棵樹的根結(jié)點是___________（7）結(jié)點k3的雙親結(jié)點是____________樹的表示方法（廣義表法）二叉樹的定義

二叉樹是n（n≥0）個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。二叉樹的邏輯結(jié)構(gòu)問題轉(zhuǎn)化：將樹轉(zhuǎn)換為二叉樹，從而利用二叉樹解決樹的有關(guān)問題。研究二叉樹的意義？設(shè)有八枚硬幣，分別表示為a、b、c、d、e、f、g、h，其中有且僅有一枚硬幣是假幣，并且假幣的重量與真幣的重量不同，可能輕，也可能重?，F(xiàn)要求以天平為工具，用最少的比較次數(shù)挑選出假幣，并同時確定這枚假幣的重量比其它真幣是輕還是重。把硬幣分成三組，從八枚硬幣中任取六枚a、b、c、d、e、f，在天平兩端各放三枚進行比較。假設(shè)a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出現(xiàn)如圖所示的三種比較結(jié)

7.2二叉樹概念和性質(zhì)

7.2.1二叉樹概念7.2.2二叉樹性質(zhì)7.2.3二叉樹存儲結(jié)構(gòu)7.2.1二叉樹概念二叉樹也稱為二次樹或二分樹，它是結(jié)點數(shù)為0或當(dāng)節(jié)點數(shù)不為0時每個結(jié)點最多只有左右兩棵子樹的樹。特點是：（1）每個結(jié)點最多只有兩棵樹，既不存在度大于2的結(jié)點。（2）子樹有左右之分，不能顛倒。思考：二叉樹和度為2的樹一樣嗎有什么區(qū)別？結(jié)點的孩子數(shù)結(jié)點孩子的有序性二叉樹的特點：⑴每個結(jié)點最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

7.2.1二叉樹的邏輯結(jié)構(gòu)注意：二叉樹和樹是兩種樹結(jié)構(gòu)。ABCDEFGABAB二叉樹的基本形態(tài)Ф空二叉樹只有一個根結(jié)點左子樹根結(jié)點只有左子樹右子樹根結(jié)點只有右子樹左子樹右子樹根結(jié)點同時有左右子樹二叉樹的邏輯結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)具有3個結(jié)點的樹和具有3個結(jié)點的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。特殊的二叉樹斜樹1.所有結(jié)點都只有左子樹的二叉樹稱為左斜樹；2.所有結(jié)點都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個結(jié)點；2.斜樹的結(jié)點個數(shù)與其深度相同。

二叉樹的邏輯結(jié)構(gòu)---斜樹的特點：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點。CDEFGHIJKLMNO1112131415特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---滿二叉樹?不是滿二叉樹，雖然所有分支結(jié)點都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點個數(shù)最多A1523467BCDEFGLM89特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---完全二叉樹對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i（1≤i≤n）的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---在滿二叉樹中，從最后一個結(jié)點開始，連續(xù)去掉任意個結(jié)點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點10與滿二叉樹中的結(jié)點10不是同一個結(jié)點特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---1.葉子結(jié)點只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結(jié)點，只可能有一個，且該結(jié)點只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點CDEFGHIJ特殊的二叉樹二叉樹的邏輯結(jié)構(gòu)---總結(jié)二叉樹的概念二叉樹的五種形態(tài)斜二叉樹滿二叉樹完全二叉樹7.2.2二叉樹性質(zhì)（5個）

性質(zhì)1非空二叉樹上第i層上至多有2i-1個結(jié)點,這里應(yīng)有i≥1。

性質(zhì)1非空二叉樹上第i層上至多有2i-1個結(jié)點,這里應(yīng)有i≥1。證明：用歸納法（1）當(dāng)i=120有一個根結(jié)點成立（2）假設(shè)對所有的j(1<=j<i)上述性質(zhì)成立。即第j層上至多有2j-1個結(jié)點成立（3）要證明j=i時，命題也成立由歸納假設(shè)：第j=i-1層上至多有2i-2

個結(jié)點，又由于二叉樹上每個結(jié)點的度最大為2，所以第i層上結(jié)點總數(shù)最大為第i-1層上最大結(jié)點數(shù)的2倍，即2×2i-2=2i-1

性質(zhì)2高度為h的二叉樹至多有2h-1個結(jié)點(h≥1)。證明：深度為h的二叉樹的最大結(jié)點數(shù)是二叉樹中每層結(jié)點的最大數(shù)之和，即=20+21+22+……+2h-1=2h-1(等比級數(shù)求和)

性質(zhì)3非空二叉樹上葉結(jié)點數(shù)等于度為2的結(jié)點數(shù)加1。有如下關(guān)系：n0=n2+1

證明：設(shè)二叉樹上葉結(jié)點數(shù)為n0,單分支結(jié)點數(shù)為n1,雙分支結(jié)點數(shù)為n2,則總結(jié)點數(shù)n=n0+n1+n2。在一棵二叉樹中,度為i(i=0,1,2)的結(jié)點，有i個孩子。孩子數(shù)=n1+2n2。由于二叉樹中除根結(jié)點以外,每個結(jié)點都是另一個結(jié)點的孩子,因此二叉樹中有：孩子數(shù)=總結(jié)點數(shù)-1=n-1。由上述三個等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉樹

(1)一棵二叉樹中雙分支結(jié)點有15個，單分支結(jié)點30個，則葉子結(jié)點有（）。(2)若一棵滿二叉樹有2047個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)為

A)512 B)1024 C)2048 D)4096(3)若一棵度為7的樹具有n1=8,n2=7,n3=6,n4=5,n5=4,n6=3,n7=2,則該樹一共有（）個葉結(jié)點[提示：此不是二叉樹，用性質(zhì)3的證明方法來推導(dǎo)]

在一棵二叉樹中,如果所有分支結(jié)點都有左孩子結(jié)點和右孩子結(jié)點,并且葉結(jié)點都集中在二叉樹的最下一層,這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫M二叉樹的結(jié)點進行連續(xù)編號,約定編號從樹根為1開始,按照層數(shù)從小到大、同一層從左到右的次序進行。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編號。每一層上結(jié)點樹都達到最大度為1的結(jié)點n1=0完全二叉樹:若二叉樹中度小于2的結(jié)點只能出現(xiàn)在最大層或次大層,并且最下面一層的葉結(jié)點都依次排列在該層最左邊的位置上,則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二叉樹中每個結(jié)點進行連續(xù)編號,編號的方法同滿二叉樹相同。

12

3

4

1

2

3

4

5

6

判斷是否為：完全二叉樹？（1）LH1=2RH1=1LH2=0RH2=10-1=-1不滿足（2）葉結(jié)點只能出現(xiàn)在最大層或次大層從左邊開始結(jié)論：不是（1）LH1=3RH1=1LH1-RH1=2不滿足（2）葉結(jié)點只能出現(xiàn)在最大層或次大層且從從左邊開始結(jié)論：不是

性質(zhì)4具有n個(n＞0)結(jié)點的完全二叉樹的高（深）度為log2n+1。證明：設(shè)深度為H余下的性質(zhì)是針對完全二叉樹的：證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點數(shù)最多結(jié)點數(shù)

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4

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

對不等式取對數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則結(jié)點i的雙親結(jié)點為

i/2；結(jié)點i的左孩子為2i；結(jié)點i的右孩子為2i＋1。

在完全二叉樹中，結(jié)點的層序編號反映了結(jié)點之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì)

性質(zhì)5對n個結(jié)點的完全二叉樹中編號為i的結(jié)點(1≤i≤n,n≥1,n為結(jié)點數(shù))有：

(1)若i=1時，結(jié)點i是樹根；否則（i>1）,結(jié)點i的雙親為

i/2.(2)若2i>n時。結(jié)點i無左孩子，是葉結(jié)點；否則結(jié)點i的左孩子為結(jié)點2i。

(3)若2i+1>n時。結(jié)點i無右孩子；否則結(jié)點i的左孩子為結(jié)點2i+1。余下的性質(zhì)是針對完全二叉樹的（很重要）：先證明（2）（3）用歸納法

(2)若2i>n時。結(jié)點i無左孩子，是葉結(jié)點；否則結(jié)點i的左孩子為結(jié)點2i。

(3)若2i+1>n時。結(jié)點i無右孩子；否則結(jié)點i的左孩子為結(jié)點2i+1。1）當(dāng)i=1時，如果2i=2>n無左孩子，否則2i=2<=n

結(jié)點2存在是結(jié)點1的左孩子。第二條成立當(dāng)i=1時，如果2i+1=3>n無右孩子，否則2i+1=3<=n

結(jié)點3存在是結(jié)點1的右孩子。第三條成立2）假設(shè)對所有的結(jié)點j(1<=j<=i)有：j的左孩子為2j(2j<=n),右孩子為2j+1(2j+1<=n)3)要證明j=i+1時等式成立i+1的左孩子為2（i+1） (2(i+1)<=n)i+1的右孩子為2（i+1）+1 (2(i+1)+1<=n)i2i2i+1

i+12i+22i+3…………i與i+1同層……

i2i2i+1……

i+12i+22i+3……i與i+1不同層結(jié)論：得證(1)若i=1時，結(jié)點i是樹根；否則（i>1）,結(jié)點i的雙親為

i/2.用歸納法自己證明第五條性質(zhì)非常重要，是二叉樹順序存儲的理論基礎(chǔ)7.2.3樹、森林與二叉樹的轉(zhuǎn)換1.兄弟加線.樹轉(zhuǎn)化為二叉樹ABCDEFG2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG1.兄弟加線.7.2.3樹、森林與二叉樹的轉(zhuǎn)換3.順時針轉(zhuǎn)動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG7.2.3樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系3.順時針轉(zhuǎn)動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF7.2.3樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對應(yīng)關(guān)系總結(jié)：樹轉(zhuǎn)換為二叉樹

⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其它孩子結(jié)點之間的連線。

⑶層次調(diào)整——以根結(jié)點為軸心，將樹順時針轉(zhuǎn)動一定的角度，使之層次分明。

森林轉(zhuǎn)換為二叉樹

⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。7.2.3樹、森林與二叉樹的轉(zhuǎn)換IHGBCDAFE二叉樹轉(zhuǎn)換為樹或森林

⑴加線——若某結(jié)點x是其雙親y的左孩子，則把結(jié)點x的右孩子、右孩子的右孩子、……，都與結(jié)點y用線連起來；⑵去線——刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)點的連線；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

7.2.3樹、森林與二叉樹的轉(zhuǎn)換FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調(diào)整IHGBCDAFE樹、森林與二叉樹的轉(zhuǎn)換例題:將下面的深林轉(zhuǎn)化為二叉樹ACDBEFGJIH7.3二叉樹存儲結(jié)構(gòu)

7.3.1二叉樹的順序存儲結(jié)構(gòu)

7.3.2二叉樹的鏈式存儲結(jié)構(gòu)7.3.1二叉樹的順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元，以層序的順序存放二叉樹的數(shù)據(jù)元素，結(jié)點的相對位置蘊含著結(jié)點的關(guān)系?！咀⒁狻窟壿嬯P(guān)系蘊含在這里：結(jié)點的相對位置蘊含著結(jié)點的關(guān)系。ABCDEFGHIJK123456789101112131415順序存儲結(jié)構(gòu)一般二叉樹的順序存儲沒有左右孩子的地方填0

A

B

C

D

E

FG

一般二叉樹

ABCDE0000FG0000123456789101112131415順序存儲結(jié)構(gòu)例：深度為K,只有K個結(jié)點的右單支樹的存放：分析:根據(jù)性質(zhì)2：二叉樹深度為K最多有2k-1個結(jié)點按順序存儲實際只使用K個存儲單元，浪費掉2k-1-K

1

2

K

1

K

結(jié)論：順序存儲只適合完全二叉樹，既不浪費空間，又能很快的確定結(jié)點存放的位置，以及結(jié)點的雙親和左右孩子。但是對于一般二叉樹可能造成存儲空間的浪費。7.3.2二叉樹的鏈式存儲結(jié)構(gòu)

常用的：二叉鏈表三叉鏈表線索鏈表

A

B

C

D

E

FG

一般二叉樹

在二叉樹的鏈接存儲中,結(jié)點的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲對應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲左孩子結(jié)點和右孩子結(jié)點(即左、右子樹的根結(jié)點)的存儲位置。lchilddatarchild二叉樹及其鏈式存儲結(jié)構(gòu)優(yōu)點：找孩子比較容易，找雙親很難

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

在三叉鏈表的存儲中,結(jié)點的結(jié)構(gòu)如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*parent,*rchild;}BTNode;

其中,data表示值域,用于存儲對應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲左孩子結(jié)點和右孩子結(jié)點(即左、右子樹的根結(jié)點)的存儲位置，parent

指向結(jié)點的雙親。lchilddataparentrchild二叉樹及其鏈式存儲結(jié)構(gòu)

A

B

C

E

F

D

G

(a)

∧A∧BCD∧∧F∧∧E∧∧G∧性質(zhì)6：含有n個結(jié)點的二叉鏈表中，有n+1個空鏈域證明：（1）n=n0+n1+n2（2）空鏈域=2n0+n1（3）no=n2+1

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

7.5二叉樹的遍歷7.5.1二叉樹遍歷的概念7.5.2二叉樹遍歷的實現(xiàn)遞歸及非遞歸算法二叉樹的遍歷操作

二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化7.5二叉樹的邏輯結(jié)構(gòu)抽象操作，可以是對結(jié)點進行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結(jié)點。

7.5.1二叉樹的邏輯結(jié)構(gòu)考慮二叉樹的組成：根結(jié)點D左子樹L右子樹R二叉樹前序遍歷若二叉樹為空，則空操作返回；否則：①訪問根結(jié)點；②前序遍歷根結(jié)點的左子樹；③前序遍歷根結(jié)點的右子樹。前序遍歷序列：ABDGCEFABCDEFG二叉樹的遍歷操作

7.5二叉樹的邏輯結(jié)構(gòu)中序遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結(jié)點的左子樹；②訪問根結(jié)點；③中序遍歷根結(jié)點的右子樹。

中序遍歷序列：DGBAECFABCDEFG二叉樹的遍歷操作

7.5二叉樹的邏輯結(jié)構(gòu)后序遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結(jié)點的左子樹；②后序遍歷根結(jié)點的右子樹。③訪問根結(jié)點；后序遍歷序列：GDBEFCAABCDEFG二叉樹的遍歷操作

7.5二叉樹的邏輯結(jié)構(gòu)層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。

層序遍歷序列：ABCDEFGABCDEFG二叉樹的遍歷操作

7.5二叉樹的邏輯結(jié)構(gòu)

A

B

C

D

E

H

I

J

K

F

G

1

2

3

4

5

6

7

8

9

10

11

先序序列：ABDHIEJKCFG中序序列：HDIBJEKAFCG后序序列：HIDJKEBFGCA先序序列：ABDEHJKLMNCFGI中序序列：DBJHLKMNEAFCGI后序序列：DJLMNKHEBFGICA在二叉樹的鏈接存儲中,結(jié)點的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲對應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲左孩子結(jié)點和右孩子結(jié)點(即左、右子樹的根結(jié)點)的存儲位置。lchilddatarchild二叉樹及其鏈式存儲結(jié)構(gòu)

(a)

(b)

A

B

C

E

F

D

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧1.先序遍歷DLR先序遍歷二叉樹的過程是：(1)訪問根結(jié)點D；(2)先序遍歷左子樹L；(3)先序遍歷右子樹R。先序序列：ABDECF/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);/*訪問根結(jié)點*/PreOrder(b->lchild);PreOrder(b->rchild);}}

A

B

C

E

F

D

lchilddatarchild/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);

/*訪問根結(jié)點*/PreOrder(b->lchild);PreOrder(b->rchild);}}PreOrder(&A)APreOrder(A->lchild=B);BPreOrder(B->lchild=D);DPreOrder(D->lchild=NULL);PreOrder(D->rchild=NULL);PreOrder(B->rchild=E);EPreOrder(E->lchild=NULL);PreOrder(E->rchild=NULL);PreOrder(A->rchild=C);CPreOrder(C->lchild=NULL);PreOrder(C->rchild=F);FPreOrder(F->lchild=NULL);PreOrder(F->rchild=NULL);

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧2.中序遍歷LDR中序遍歷二叉樹的過程是：(1)中序遍歷左子樹L；(2)訪問根結(jié)點D；(3)中序遍歷右子樹R。中序序列：DBEACF/*中序遍歷的遞歸算法*/voidInOrder(BTNode*b){if(b!=NULL){/*訪問根結(jié)點*/

InOrder(b->lchild);

printf("%c",b->data);

InOrder(b->rchild);}}

A

B

C

E

F

D

3.后序遍歷后序遍歷二叉樹的過程是：(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問根結(jié)點。后序序列：DEBFCA

voidPostOrder(BTNode*b)/*后序遍歷遞歸算法*/{if(b!=NULL)