數(shù)據(jù)結(jié)構(gòu)與算法設計（第二版）課件 6章 樹與二叉樹

第六章樹與二叉樹西安科技大學計算機學院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設計

族譜就是一個家族所有人員構(gòu)成的大名單，是一個用血緣聯(lián)系起來的系統(tǒng)。通過繪制家譜樹，記錄家族成員的相互關系。

家譜樹，是一種描繪家庭關系的樹狀結(jié)構(gòu)圖，樹中的每個成員可以清楚的知道自己的家族起源、家族關系以及其他成員的基礎信息。

通過家譜，可使子孫后輩知悉祖先的淵源、人口、遷徙、分布、名人傳略、故事傳說、先賢史跡等等。通過家譜，可激勵子孫后輩傳承家族美德，發(fā)揚優(yōu)良傳統(tǒng)，賡續(xù)家族源流。

要記得自己來自于哪里？根在哪里？愛父母、愛自己的家，熱愛我們的大家-中國，我們擁有一個強大的國家，無論走到哪里，我們的根永遠在中國。引例

家譜族譜系統(tǒng)把每一個成員都視為系統(tǒng)的一個要素，他們按照“祖—父—子—孫”的關系構(gòu)成了樹狀結(jié)構(gòu)。引例

家譜族譜系統(tǒng)引例

組織架構(gòu)在樹中，我們把數(shù)據(jù)元素稱之為結(jié)點數(shù)據(jù)元素的關系層次分明，A第一層、BCD在的二層、EFGHIJ在第三層、KLM在第四層。樹及二叉樹--基本概念T3第一層第二層第三層第四層根結(jié)點結(jié)點A為樹T的根結(jié)點，除根結(jié)點A之外的其余結(jié)點分為三個不相交的集合：T1T2抽象透過現(xiàn)象看本質(zhì)類似于線性表，我們把樹定義為一個二元組：

Tree=（D,R）

其中：D是具有相同特性的數(shù)據(jù)元素的集合；R是關系集合。

如果D=NULL,稱這棵樹為空樹；

如果D只包含一個數(shù)據(jù)元素，則R為空集；樹及二叉樹--基本概念否則：關系描述R定義為：(1)在D中存在唯一的一個特殊的元素稱為樹的根結(jié)點root，根結(jié)點root沒有前驅(qū)結(jié)點。(2)若D-{root}！=NULL，D-{root}=D1∪D2∪…∪Dm，D1∩D2∩…∩Dm=∮

對于任意一個Di,ti∈Di,<root,ti>∈R，root就有m個直接后繼。(3)對應集合D1，D2，…，Dm，有R1,R2,…，Rm個關系，其中每一組二元組Ti=（Di,Ri）又是一棵滿足上述定義的樹。樹T1，T2，…，Tm稱為這個根結(jié)點root的子樹。透過現(xiàn)象看本質(zhì)森林:是零棵或多棵樹組成的集合。樹也可定義為：

n(n≥0)個結(jié)點的有限集，

若n=0，則為空樹；

否則，樹由一個根結(jié)點和m(m≥0)棵樹組成的森林構(gòu)成。

森林中的每棵樹都是根的子樹。樹及二叉樹--基本概念具有下面兩個特點：(1)樹的根結(jié)點沒有前驅(qū)結(jié)點，除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點。(2)樹中所有結(jié)點可以有零個或多個后繼結(jié)點。樹及二叉樹--基本概念1）關于結(jié)點的概念根結(jié)點B、C、D是A的兒子結(jié)點A是B、C、D的雙親結(jié)點B、C、D互為兄弟B有兩個兒子EFF是葉子結(jié)點度不為零的結(jié)點稱為分支結(jié)點F和G之間是堂兄弟關系結(jié)點A的度就是三擁有子樹的個數(shù)就是該結(jié)點的度。樹中各個結(jié)點度的最大值稱為這棵樹的度度為0的結(jié)點稱為葉結(jié)點度不為0的結(jié)點稱為分支結(jié)點，或者稱為非終端結(jié)點，A,B,C,DE,H是分支結(jié)點2）結(jié)點的層數(shù)及樹的深度樹及二叉樹--基本概念結(jié)點在樹中的層數(shù)約定為：樹的根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它的雙親結(jié)點的層數(shù)加1。若某個結(jié)點的層次為k，則其孩子結(jié)點的層次為k+1。樹中葉結(jié)點的最大層次數(shù)定義為樹的深度。如果一棵樹的一串結(jié)點n1,n2,…,nk，如果結(jié)點ni是ni+1的雙親結(jié)點(1≤i＜k)，就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。在樹中，如果有一條路徑從結(jié)點M到結(jié)點N，那么M就稱為N的祖先，而N稱為M的子孫。樹分：有序樹和無序樹。如果一棵樹中結(jié)點的各子樹從左到右是有次序的，這棵樹就是有序樹；反之，則稱為無序樹。結(jié)點的層數(shù)及樹的深度結(jié)點在樹中的層數(shù)約定為：樹的根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它的雙親結(jié)點的層數(shù)加1。樹中葉結(jié)點的最大層次數(shù)定義為樹的深度。如果一棵樹的一串結(jié)點n1,n2,…,nk，如果結(jié)點ni是ni+1的雙親結(jié)點(1≤i＜k)，就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。在樹中，如果有一條路徑從結(jié)點M到結(jié)點N，那么M就稱為N的祖先，而N稱為M的子孫。K

B

C

D

E

F

G

H

I

J

A

L

M

第一層第二層第三層第四層A、B、E是K、L、F的祖先A、C是G的祖先，反之，稱以A為根的樹中所有結(jié)點是A的子孫樹及二叉樹--基本概念樹分：有序樹和無序樹。如果一棵樹中結(jié)點的各子樹從左到右是有次序的，這棵樹就是有序樹；反之，則稱為無序樹。樹及二叉樹--基本概念6-2二叉樹基本概念二叉樹是另一種樹形結(jié)構(gòu)，可以簡單理解二叉樹就是每個結(jié)點最多有兩棵子樹的有序樹。圖中的二叉樹含有10個結(jié)點，DACBGEFHIJ其中A是根，左子樹TL由{C，B，G}構(gòu)成，右子樹TR由{D，E，F(xiàn)，H，J，I}構(gòu)成；左子樹TL中，C是根結(jié)點，TL的左子樹為空，TL的右子樹由{B，G}構(gòu)成；右子樹TR中，D是根結(jié)點，TR的左子樹由{E，H}構(gòu)成，TR的右子樹由{F，J，I}構(gòu)成，以此類推。二叉樹的特點每個結(jié)點最多有兩棵子樹，且互不相交；左子樹和右子樹是有順序的，次序不能顛倒。因此二叉樹具有五種基本形態(tài)：左子樹右子樹左子樹右子樹(a)(b)(c)(d)(e)滿二叉樹和完全二叉樹滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱做滿二叉樹。123456789101112131415(a)一顆滿二叉樹1234567891011(b)一顆非滿二叉樹滿二叉樹的三個特點123456789101112131415葉子只能出現(xiàn)在最下一層。非葉子結(jié)點的度一定是2。在同樣深度的二叉樹中，滿二叉樹的結(jié)點個數(shù)最多，葉子最多。

從滿二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進行編號(1，2，…，n)。

圖中的滿二叉樹的編號是(1到15)。

完全二叉樹：一棵深度為k，有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為i(1≤i≤n)的結(jié)點與深度為k的滿二叉樹中，編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。12345678910滿二叉樹一定是完全二叉樹，但是完全二叉樹不一定是滿二叉樹。

一棵深度為4的完全二叉樹。深度為4的擁有結(jié)點最多的完全二叉樹123456789101112131415深度為4的擁有結(jié)點最少的完全二叉樹（a）12345678（b）完全二叉樹特點：葉子結(jié)點只能出現(xiàn)在最下兩層。最下層的葉子一定集中在左部連續(xù)位置。倒數(shù)第二層若有葉子結(jié)點，一定都在右部連續(xù)位置。如果結(jié)點度為1，則該結(jié)點只有左孩子，即不存在只有右孩子的情況。同樣結(jié)點數(shù)的二叉樹，完全二叉樹的深度最小。性質(zhì)1：一棵非空二叉樹的第i層上最多有2i-1個結(jié)點(i≥1)。通過數(shù)學歸納法論證，可以很容易得出第i層上至多有2i-1個結(jié)點。二叉樹--五條性質(zhì)20?=?122-1?=?223-1?=?424-1?=?820?=?1

性質(zhì)2：一棵深度為k的二叉樹中，最多具有2k-1個結(jié)點。

證明：深度為k的二叉樹，其結(jié)點總數(shù)的最大值是將二叉樹每層上結(jié)點的最大值相加。

二叉樹--五條性質(zhì)

性質(zhì)3：對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為n0，度數(shù)為2的結(jié)點數(shù)為n2，則有n0?=?n2?+?1。證明：設n為二叉樹的結(jié)點總數(shù)，n1為二叉樹中度為1的結(jié)點數(shù)，那么就有n?=?n0?+?n1?+?n2(6-1)設B為二叉樹中的分支數(shù)，那么有B?=?n?-?1(6-2)

B?=?n1?+?2n2(6-3)綜合式(6-1)、(6-2)、(6-3)可以得到：可以得到：n0?=?n2?+?1

二叉樹--五條性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為。根據(jù)性質(zhì)2，深度為k的二叉樹最多的節(jié)點數(shù)目為2k?-?1個結(jié)點擁有最多的結(jié)點數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-1-1+1=8個結(jié)點。擁有最少的結(jié)點數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-?1=15個結(jié)點。所以當一棵完全二叉樹的深度為k、結(jié)點個數(shù)為n時，

2k-1?-?1＜n≤2k?-?1變換后得到：2k-1?≤n＜2k，對不等式取對數(shù)，有k-1≤lb?n＜k由于k是整數(shù)，所以有k?=二叉樹--五條性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為。根據(jù)性質(zhì)2，深度為k的二叉樹最多的節(jié)點數(shù)目為2k?-?1個結(jié)點擁有最多的結(jié)點數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-1-1+1=8個結(jié)點。擁有最少的結(jié)點數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-?1=15個結(jié)點。所以當一棵完全二叉樹的深度為k、結(jié)點個數(shù)為n時，

2k-1?-?1＜n≤2k?-?1變換后得到：2k-1?≤n＜2k，對不等式取對數(shù)，有k-1≤lb?n＜k由于k是整數(shù)，所以有k?=二叉樹--五條性質(zhì)性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點，(1)如果i?>?1，序號為i的結(jié)點的雙親結(jié)點的序號為i整除2；

如果i?=?1，序號為i的結(jié)點是根結(jié)點。(2)如果2i≤n，序號為i的結(jié)點有左孩子，左孩子結(jié)點的序號為2i；

如果2i＞n，序號為i的結(jié)點無左孩子。(3)如果2i+1≤n，序號為i的結(jié)點的右孩子結(jié)點的序號為2i+1；

如果2i+1＞n，序號為i的結(jié)點無右孩子。二叉樹--五條性質(zhì)對于(1)，

i?=?1時就是根結(jié)點。i＞1時，比如結(jié)點7，它的雙親是7/2?=?3；結(jié)點9，它的雙親是9/2?=?4。對于(2)，

結(jié)點6，因為2?×?6?=?12超過了結(jié)點個數(shù)10，

所以結(jié)點6沒有左孩子，它是葉子結(jié)點；

結(jié)點5，因為2?×?5?=?10沒有超過結(jié)點個數(shù)10，

所有它有左孩子，左孩子結(jié)點為10。對于(3)，

結(jié)點5，2?×?5?+?1?=?11超過了結(jié)點個數(shù)10，

所以結(jié)點5沒有右孩子；結(jié)點3，2?×?3?+?1?=?7沒有超過結(jié)點個數(shù)10，所以結(jié)點3有右孩子，右孩子是結(jié)點7。二叉樹--五條性質(zhì)復習樹樹：有序樹和無序樹。如果一棵樹中結(jié)點的各子樹從左到右是有次序的，這棵樹就是有序樹；反之，則稱為無序樹。二叉樹的特點每個結(jié)點最多有兩棵子樹，且互不相交；左子樹和右子樹是有順序的，次序不能顛倒。因此二叉樹具有五種基本形態(tài)：左子樹右子樹左子樹右子樹(a)(b)(c)(d)(e)去粗取精、去偽存真、由表及里，準確地揭示出事物的本質(zhì)和規(guī)律。滿二叉樹完全二叉樹

二叉樹的性質(zhì)性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。證明：用數(shù)學歸納法。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k≥1）性質(zhì)3:對任意一棵二叉樹T，若終端結(jié)點數(shù)為n0，而其度數(shù)為2的結(jié)點數(shù)為n2，則n0=n2+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為［log2n］+1。性質(zhì)5:對于具有n個結(jié)點的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點有：（1）如i=1，則i是根結(jié)點，無雙親；如i>1，則i的結(jié)點的雙親結(jié)點序號為［i/2］（2）如2i>n，則i的結(jié)點無左孩子；否則Lchild(i)=2i（3）如2i＋1>n，則i的結(jié)點無右孩子；否則Rchild(i)=2i+1事物的本質(zhì)和規(guī)律每一結(jié)點最多可有兩個后繼。AGFEDCB二叉樹的結(jié)構(gòu)是非線性的，根結(jié)點沒有前驅(qū)；除根之外任意一個結(jié)點只有唯一的一個前驅(qū)；6.2二叉樹的存儲結(jié)構(gòu)

本質(zhì)和規(guī)律提問：

用順序存儲結(jié)構(gòu)可以存儲二叉樹嗎？

鏈式存儲結(jié)構(gòu)可以嗎？

二叉樹--順序存儲結(jié)構(gòu)ALKJIHGFEDCB132451211109876對于具有n個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序存儲到一維數(shù)組中(下標從1開始)。依據(jù)二叉樹的性質(zhì)5，對于存儲位置為i的結(jié)點：如果i?=?1，則該結(jié)點是根結(jié)點；

如果i＞1，則其雙親結(jié)點的存儲位置為i/2；如果2i≤n，則其左孩子的存儲位置為2i；如果2i＞n，則無左孩子；

如果2i+1≤n，則其右孩子的存儲位置為2i+1；如果2i+1?>?n，則無右孩子。最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結(jié)點在二叉樹中的位置，以及結(jié)點之間的關系。ALKJIHGFEDCB

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

二叉樹--順序存儲結(jié)構(gòu)ALKJIHGFEDCB132451211109876二叉樹的順序存儲表示可描述為：

#defineMAXNODE /*二叉樹的最大結(jié)點數(shù)*/typedefdatatypeSqBiTree[MAXNODE];/*0號單元存放結(jié)點數(shù)目*/SqBiTreebt;對于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點順序存儲在一維數(shù)組中，則數(shù)組元素下標之間的關系不能反映二叉樹中結(jié)點之間的邏輯關系；只有增添一些并不存在的空結(jié)點，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲。

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

12345678910111213ABCVDEVVFVVVG注意:剛才添加的那些虛結(jié)點，在存儲中設置為空。VVVVVV

ABCDD一棵深度為k的右單支樹，只有k個結(jié)點，添加空結(jié)點使之成為深度為K的完全二叉樹，就需要分配2k-1個存儲單元。所以，二叉樹的順序存儲結(jié)構(gòu)僅適合于存儲完全二叉樹。

二叉樹--順序存儲結(jié)構(gòu)123456789101112131415ABCVDVVVVVVVVVVA最壞的情況:右單支樹尺有所短，寸有所長《楚辭·卜居》：“夫尺有所短，寸有所長，物有所不足，智有所不明，數(shù)有所不逮，神有所不通?！彪p向鏈表，每一個結(jié)點有兩個指針域，一個指向前驅(qū)，一個指向后繼。二叉樹的結(jié)構(gòu)是非線性的，根結(jié)點沒有前驅(qū)，除根之外任意一個結(jié)點只有唯一的一個前驅(qū)；每一結(jié)點最多可有兩個后繼。對于二叉樹中的結(jié)點，可以增加兩個指針域，一個指向左孩子，一個指向右孩子。

二叉樹—二叉鏈表存儲前驅(qū)指針后繼指針datapriornext左孩子指針右孩子指針datalchildrchild也可以再增加一個指針指向雙親對于任意的二叉樹來說，給每個結(jié)點設計一個存儲結(jié)點本身信息的域和兩個指針域分別指向該結(jié)點的左孩子、右孩子。lchilddatarchild

二叉樹—二叉鏈表存儲二叉鏈表結(jié)點的結(jié)構(gòu)可以定義為一個結(jié)構(gòu)體：typedefstructNode{datatypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;當左孩子或右孩子不存在時，相應指針域值為空(用符號∧或NULL表示)。結(jié)點的數(shù)據(jù)信息指向左孩子的指針指向右孩子的指針對于一棵二叉樹的二叉鏈表，設一頭指針指向根結(jié)點就可以了。這棵二叉樹，用二叉鏈表存儲，設頭指針bt指向根結(jié)點。AGFEDCBVEFCGBDVVVVVAVV頭指針bt

二叉樹—二叉鏈表存儲如果一個二叉樹含有n個結(jié)點，那么它的二叉鏈表中必含有2n個指針域，其中必有n+1個空的鏈域。AGFEDCBVEFCGBDVVVVVAVV頭指針bt

二叉樹—二叉鏈表存儲二叉樹中除根結(jié)點之外，每個結(jié)點都有一個雙親，所以，含有n個結(jié)點的二叉樹其分支數(shù)目B?=?n-1，即非空的鏈域有n-1個，故空鏈域有2n-(n-1)?=?n+1個。為了便于找到雙親結(jié)點，可增加一個parent域，parent域指向該結(jié)點的父結(jié)點，

就形成了三叉鏈表。頭指針btAGVVVEVCBVDFVVVV

二叉樹--三叉鏈表存儲三叉鏈表中每個結(jié)點由四個域組成，具體結(jié)構(gòu)為：其中，data、lchild以及rchild三個域的意義與二叉鏈表一樣；

parent域是指向該結(jié)點雙親結(jié)點的指針。這種存儲結(jié)構(gòu)既便于查找孩子結(jié)點，又便于查找雙親結(jié)點；但是，相對于二叉鏈表存儲結(jié)構(gòu)而言，它增加了空間開銷。lchilddatarchildparent

二叉樹--三叉鏈表存儲盡管在二叉鏈表中無法由結(jié)點直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對于一般情況的二叉樹，甚至比順序存儲結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹存儲方式。不同的存儲結(jié)構(gòu)實現(xiàn)二叉樹的操作也不同。如要找某個結(jié)點的父結(jié)點，在三叉鏈表中很容易實現(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找。在具體應用中，需要根據(jù)二叉樹的形態(tài)和需要進行的操作來決定二叉樹的存儲結(jié)構(gòu)。

二叉樹--存儲結(jié)構(gòu)尺有所短，寸有所長《楚辭·卜居》：“夫尺有所短，寸有所長，物有所不足，智有所不明，數(shù)有所不逮，神有所不通?！?.3二叉樹的遍歷二叉樹的遍歷：是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。通過一次完整的遍歷，可把二叉樹中結(jié)點信息由非線性排列變?yōu)槟撤N意義上的線性序列，這就給程序的實現(xiàn)帶來了好處。一棵不空的二叉樹由根結(jié)點D、左子樹L和右子樹R三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹了。DLR如果限定先左后右，那么就有三種遍歷順序：

①先訪問根結(jié)點D；再遍歷左子樹L；最后遍歷右子樹R；LRD如果限定先左后右，那么就有三種遍歷順序：

①先訪問根結(jié)點D；再遍歷左子樹L；最后遍歷右子樹R；

②先遍歷左子樹L；再訪問根結(jié)點D；最后遍歷右子樹R；LRD如果限定先左后右，那么就有三種遍歷順序：

①先訪問根結(jié)點D；再遍歷左子樹L；最后遍歷右子樹R；

②先遍歷左子樹L；再訪問根結(jié)點D；最后遍歷右子樹R；

③先遍歷左子樹L；再遍歷右子樹R；最后訪問根結(jié)點D。LR在這三種順序中，只是訪問根結(jié)點D的位置不同D如果限定先左后右，那么就有三種遍歷順序：

①先訪問根結(jié)點D；再遍歷左子樹L；最后遍歷右子樹R；

②先遍歷左子樹L；再訪問根結(jié)點D；最后遍歷右子樹R；

③先遍歷左子樹L；再遍歷右子樹R；最后訪問根結(jié)點D。LR在這三種順序中，只是訪問根結(jié)點D的位置不同D先序遍歷中序遍歷后序遍歷這三種遍歷算法顯然是遞歸的，根結(jié)點只有一個，所以訪問根結(jié)點，就可以直接對根結(jié)點進行相應的操作了。比如輸出根結(jié)點；左子樹、右子樹要么為空，要么依然是一棵二叉樹，所以左子樹、右子樹的遍歷就是遞歸的了。通過一次完整的遍歷，可使二叉樹中結(jié)點信息由非線性排列變?yōu)槟撤N意義上的線性序列。也就是說，遍歷操作使非線性結(jié)構(gòu)線性化。二叉樹--先序遍歷1、二叉樹--先序遍歷(DLR)算法的步驟：(0)如果二叉樹為空，遍歷結(jié)束；否則，(1)訪問根結(jié)點；(2)先序遍歷根結(jié)點的左子樹；(3)先序遍歷根結(jié)點的右子樹。1voidPreOrder(BiTreebt)2{3if(bt==NULL)4return;5printf(“%c”,bt->data);6PreOrder(bt->lchild);7PreOrder(bt->rchild);8}先序遍歷二叉樹bt遞歸調(diào)用的結(jié)束條件輸出bt的data遞歸調(diào)用先序遍歷函數(shù)遍歷bt的左子樹遞歸調(diào)用先序遍歷函數(shù)遍歷bt的右子樹二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}bt輸出序列Abt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列AbtBbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABbtDbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);

6PreOrder(bt->rchild);7}輸出序列ABDbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDbtGbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);

7}輸出序列ABDGbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);

7}輸出序列ABDGbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGbtCbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCbtEbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEbtFbtNULL二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEFbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEFbtbtNULL二叉樹--先序遍歷二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEFbtNULLbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEFbtbt二叉樹--先序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}輸出序列ABDGCEFbtbt2.

中序遍歷(LDR)中序遍歷的遞歸過程為：(0)若二叉樹為空，遍歷結(jié)束；否則，(1)中序遍歷根結(jié)點的左子樹；(2)訪問根結(jié)點；(3)中序遍歷根結(jié)點的右子樹。二叉樹--中序遍歷1voidInOrder(BiTreebt)2{3if(bt==NULL)4return; 5InOrder(bt->lchild); 6printf(“%c”,bt->data); 7InOrder(bt->rchild); 8}中序遍歷二叉樹bt遞歸調(diào)用的結(jié)束條件中序遞歸遍歷bt的左子樹訪問結(jié)點的數(shù)據(jù)域中序遞歸遍歷bt的右子樹二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btNULLbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列Dbtbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtNULLbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtNULLbtG二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);

7}輸出序列DbtbtG二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);

7}輸出序列DbtbtG二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtBbtNULLG二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DBbtNULLbtG二叉樹--中序遍歷二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DBbtbtGABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DBbtAbtG二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtbtGBA二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGBAbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGBAbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGBAEbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGBAEbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DbtGBAEbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAEbtCbt二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECbtbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECbtbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECbtFbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECbtFbtNULL二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECbtFbt二叉樹--中序遍歷二叉樹--中序遍歷ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}輸出序列DGBAECFbtbt3.后序遍歷(LRD)后序遍歷的遞歸過程為：(0)若二叉樹為空，遍歷結(jié)束；否則，(1)后序遍歷根結(jié)點的左子樹，(2)后序遍歷根結(jié)點的右子樹，(3)訪問根結(jié)點。二叉樹--后序遍歷1voidPostOrder(BiTreebt)2{3if(bt==NULL)4 return; 5PostOrder(bt->lchild);6PostOrder(bt->rchild);7printf(“%c”,bt->data);8}后序遍歷二叉樹bt遞歸調(diào)用的結(jié)束條件后序遞歸遍歷bt的左子樹后序遞歸遍歷bt的右子樹訪問結(jié)點的數(shù)據(jù)域二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}bt輸出序列Gbt二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}輸出序列GbtDbt二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}輸出序列GDbtbtNULL二叉樹--后序遍歷ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}輸出序列GDbtbtNULL二叉樹--后序遍歷