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

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

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

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

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

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

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

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

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

Tree=（D,R）

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

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

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

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

n(n≥0)個(gè)結(jié)點(diǎn)的有限集，

若n=0，則為空樹；

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

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

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

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

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

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

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

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

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

性質(zhì)3：對于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有n0?=?n2?+?1。證明：設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)，那么就有n?=?n0?+?n1?+?n2(6-1)設(shè)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個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為。根據(jù)性質(zhì)2，深度為k的二叉樹最多的節(jié)點(diǎn)數(shù)目為2k?-?1個(gè)結(jié)點(diǎn)擁有最多的結(jié)點(diǎn)數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-1-1+1=8個(gè)結(jié)點(diǎn)。擁有最少的結(jié)點(diǎn)數(shù)目，深度為4的完全二叉樹形態(tài)，共有24-?1=15個(gè)結(jié)點(diǎn)。所以當(dāng)一棵完全二叉樹的深度為k、結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，

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

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

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

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

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

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

結(jié)點(diǎn)6，因?yàn)??×?6?=?12超過了結(jié)點(diǎn)個(gè)數(shù)10，

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

結(jié)點(diǎn)5，因?yàn)??×?5?=?10沒有超過結(jié)點(diǎn)個(gè)數(shù)10，

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

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

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

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

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

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

鏈?zhǔn)酱鎯Y(jié)構(gòu)可以嗎？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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