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

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

7.1.1樹的定義

7.1.3樹的基本術語7.1.2樹的表示7.1.1樹的定義：核心關系：層次關系。

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

有且僅有一個特定的稱為根的結點；⑵

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

1.樹的結點：包含一個數據元素和指向其子樹的所有分支。

2.結點的度：一個結點擁有的子樹的個數。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹形表示法

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

A

C

G

B

D

I

JEFH

MKL

樹形表示法

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

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

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

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

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

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

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

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

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

7.2二叉樹概念和性質

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

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

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

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

性質1非空二叉樹上第i層上至多有2i-1個結點,這里應有i≥1。

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

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

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

性質3非空二叉樹上葉結點數等于度為2的結點數加1。有如下關系：n0=n2+1

證明：設二叉樹上葉結點數為n0,單分支結點數為n1,雙分支結點數為n2,則總結點數n=n0+n1+n2。在一棵二叉樹中,度為i(i=0,1,2)的結點，有i個孩子。孩子數=n1+2n2。由于二叉樹中除根結點以外,每個結點都是另一個結點的孩子,因此二叉樹中有：孩子數=總結點數-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)一棵二叉樹中雙分支結點有15個，單分支結點30個，則葉子結點有（）。(2)若一棵滿二叉樹有2047個結點，則該二叉樹中葉結點的個數為

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

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

12

3

4

1

2

3

4

5

6

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

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

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結點數最多結點數

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

2k-1≤n＜2k性質4

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

對不等式取對數，有：

k-1≤log2n＜k即：

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

i/2；結點i的左孩子為2i；結點i的右孩子為2i＋1。

在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。完全二叉樹的基本性質

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

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

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

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

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

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

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

結點3存在是結點1的右孩子。第三條成立2）假設對所有的結點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不同層結論：得證(1)若i=1時，結點i是樹根；否則（i>1）,結點i的雙親為

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

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

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

⑶層次調整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。

森林轉換為二叉樹

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

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

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

7.2.3樹、森林與二叉樹的轉換FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調整IHGBCDAFE樹、森林與二叉樹的轉換例題:將下面的深林轉化為二叉樹ACDBEFGJIH7.3二叉樹存儲結構

7.3.1二叉樹的順序存儲結構

7.3.2二叉樹的鏈式存儲結構7.3.1二叉樹的順序存儲結構用一組地址連續(xù)的存儲單元，以層序的順序存放二叉樹的數據元素，結點的相對位置蘊含著結點的關系。【注意】邏輯關系蘊含在這里：結點的相對位置蘊含著結點的關系。ABCDEFGHIJK123456789101112131415順序存儲結構一般二叉樹的順序存儲沒有左右孩子的地方填0

A

B

C

D

E

FG

一般二叉樹

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

1

2

K

1

K

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

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

A

B

C

D

E

FG

一般二叉樹

在二叉樹的鏈接存儲中,結點的結構如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

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

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

在三叉鏈表的存儲中,結點的結構如下:

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

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

指向結點的雙親。lchilddataparentrchild二叉樹及其鏈式存儲結構

A

B

C

E

F

D

G

(a)

∧A∧BCD∧∧F∧∧E∧∧G∧性質6：含有n個結點的二叉鏈表中，有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)遞歸及非遞歸算法二叉樹的遍歷操作

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

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

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

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

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

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

7.5二叉樹的邏輯結構層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

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

7.5二叉樹的邏輯結構

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在二叉樹的鏈接存儲中,結點的結構如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

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

(a)

(b)

A

B

C

E

F

D

A

B

C

∧

D∧

∧

E∧

∧

F∧

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

A

B

C

E

F

D

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

/*訪問根結點*/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)訪問根結點D；(3)中序遍歷右子樹R。中序序列：DBEACF/*中序遍歷的遞歸算法*/voidInOrder(BTNode*b){if(b!=NULL){/*訪問根結點*/

InOrder(b->lchild);

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

InOrder(b->rchild);}}

A

B

C

E

F

D

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

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