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

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

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

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

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

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

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

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

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

Tree=（D,R）

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

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

如果D只包含一個數(shù)據(jù)元素，則R為空集；樹及二叉樹--基本概念否則：關系描述R定義為：(1)在D中存在唯一的一個特殊的元素稱為樹的根結點root，根結點root沒有前驅結點。(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稱為這個根結點root的子樹。透過現(xiàn)象看本質森林:是零棵或多棵樹組成的集合。樹也可定義為：

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

若n=0，則為空樹；

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

森林中的每棵樹都是根的子樹。樹及二叉樹--基本概念具有下面兩個特點：(1)樹的根結點沒有前驅結點，除根結點之外的所有結點有且只有一個前驅結點。(2)樹中所有結點可以有零個或多個后繼結點。樹及二叉樹--基本概念1）關于結點的概念根結點B、C、D是A的兒子結點A是B、C、D的雙親結點B、C、D互為兄弟B有兩個兒子EFF是葉子結點度不為零的結點稱為分支結點F和G之間是堂兄弟關系結點A的度就是三擁有子樹的個數(shù)就是該結點的度。樹中各個結點度的最大值稱為這棵樹的度度為0的結點稱為葉結點度不為0的結點稱為分支結點，或者稱為非終端結點，A,B,C,DE,H是分支結點2）結點的層數(shù)及樹的深度樹及二叉樹--基本概念結點在樹中的層數(shù)約定為：樹的根結點的層數(shù)為1，其余結點的層數(shù)等于它的雙親結點的層數(shù)加1。若某個結點的層次為k，則其孩子結點的層次為k+1。樹中葉結點的最大層次數(shù)定義為樹的深度。如果一棵樹的一串結點n1,n2,…,nk，如果結點ni是ni+1的雙親結點(1≤i＜k)，就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。在樹中，如果有一條路徑從結點M到結點N，那么M就稱為N的祖先，而N稱為M的子孫。樹分：有序樹和無序樹。如果一棵樹中結點的各子樹從左到右是有次序的，這棵樹就是有序樹；反之，則稱為無序樹。結點的層數(shù)及樹的深度結點在樹中的層數(shù)約定為：樹的根結點的層數(shù)為1，其余結點的層數(shù)等于它的雙親結點的層數(shù)加1。樹中葉結點的最大層次數(shù)定義為樹的深度。如果一棵樹的一串結點n1,n2,…,nk，如果結點ni是ni+1的雙親結點(1≤i＜k)，就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。在樹中，如果有一條路徑從結點M到結點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為根的樹中所有結點是A的子孫樹及二叉樹--基本概念樹分：有序樹和無序樹。如果一棵樹中結點的各子樹從左到右是有次序的，這棵樹就是有序樹；反之，則稱為無序樹。樹及二叉樹--基本概念6-2二叉樹基本概念二叉樹是另一種樹形結構，可以簡單理解二叉樹就是每個結點最多有兩棵子樹的有序樹。圖中的二叉樹含有10個結點，DACBGEFHIJ其中A是根，左子樹TL由{C，B，G}構成，右子樹TR由{D，E，F(xiàn)，H，J，I}構成；左子樹TL中，C是根結點，TL的左子樹為空，TL的右子樹由{B，G}構成；右子樹TR中，D是根結點，TR的左子樹由{E，H}構成，TR的右子樹由{F，J，I}構成，以此類推。二叉樹的特點每個結點最多有兩棵子樹，且互不相交；左子樹和右子樹是有順序的，次序不能顛倒。因此二叉樹具有五種基本形態(tài)：左子樹右子樹左子樹右子樹(a)(b)(c)(d)(e)滿二叉樹和完全二叉樹滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱做滿二叉樹。123456789101112131415(a)一顆滿二叉樹1234567891011(b)一顆非滿二叉樹滿二叉樹的三個特點123456789101112131415葉子只能出現(xiàn)在最下一層。非葉子結點的度一定是2。在同樣深度的二叉樹中，滿二叉樹的結點個數(shù)最多，葉子最多。

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

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

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

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

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

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

二叉樹--五條性質

性質3：對于一棵非空的二叉樹，如果葉子結點數(shù)為n0，度數(shù)為2的結點數(shù)為n2，則有n0?=?n2?+?1。證明：設n為二叉樹的結點總數(shù)，n1為二叉樹中度為1的結點數(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

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

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

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

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

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

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

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

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

所以結點6沒有左孩子，它是葉子結點；

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

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

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

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

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

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

用順序存儲結構可以存儲二叉樹嗎？

鏈式存儲結構可以嗎？

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

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

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

123456789101112完全二叉樹二叉樹的順序存儲結構

二叉樹--順序存儲結構ALKJIHGFEDCB132451211109876二叉樹的順序存儲表示可描述為：

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

二叉樹--順序存儲結構AFEDCBG

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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