數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)：第6章 樹

樹和二叉樹1、樹和森林的概念（樹的定義、樹的術(shù)語(yǔ)、性質(zhì)及運(yùn)算）；2、二叉樹的定義、性質(zhì)及運(yùn)算；3、二叉樹的存儲(chǔ)結(jié)構(gòu)（順序、鏈?zhǔn)奖硎荆?、遍歷二叉樹5、樹的存儲(chǔ)結(jié)構(gòu)；樹、森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林6、哈夫曼樹、哈夫曼編碼。教學(xué)內(nèi)容樹型結(jié)構(gòu)（非線性結(jié)構(gòu)）結(jié)點(diǎn)之間有分支具有層次關(guān)系例自然界：樹人類社會(huì)家譜行政組織機(jī)構(gòu)計(jì)算機(jī)領(lǐng)域編譯：用樹表示源程序的語(yǔ)法結(jié)構(gòu)數(shù)據(jù)庫(kù)系統(tǒng)：用樹組織信息算法分析：用樹描述執(zhí)行過(guò)程國(guó)務(wù)院山東省北京市西藏自治區(qū)…濟(jì)南市青島市威海市…歷下區(qū)市中區(qū)…商河縣6.1樹的定義和基本術(shù)語(yǔ)定義：

樹

(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集。若n=0，稱為空樹；若n>0，則它滿足如下兩個(gè)條件：

(1)有且僅有一個(gè)特定的稱為根

(Root)的結(jié)點(diǎn)；

(2)其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集T1,T2,

T3,…,Tm，其中每一個(gè)集合本身又是一棵樹，并稱為根的子樹

(SubTree)。顯然，樹的定義是一個(gè)遞歸的定義。樹的邏輯結(jié)構(gòu)：樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn)但至多只能有一個(gè)直接前趨結(jié)點(diǎn)。T3T2T1基本術(shù)語(yǔ)：結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。度

=0葉子

終端結(jié)點(diǎn)

度≠0分支結(jié)點(diǎn)

非終端結(jié)點(diǎn)

根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)

樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。雙親孩子兄弟結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)。第1層第2層第3層第4層堂兄弟雙親在同一層的結(jié)點(diǎn)樹的深度：樹中結(jié)點(diǎn)的最大層次。有序樹：樹中結(jié)點(diǎn)的各子樹從左至右有次序（最左邊的為第一個(gè)孩子）。無(wú)序樹：樹中結(jié)點(diǎn)的各子樹無(wú)次序。結(jié)點(diǎn)：數(shù)據(jù)元素+指向子樹的分支根結(jié)點(diǎn)：非空樹中無(wú)前驅(qū)結(jié)點(diǎn)的結(jié)點(diǎn)森林：是m(m≥0)棵互不相交的樹的集合。一棵樹可以看成是一個(gè)特殊的森林。把根結(jié)點(diǎn)刪除樹就變成了森林。給森林中的各子樹加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹。樹森林一定是不一定是EFGHIABCDJKLM樹的邏輯結(jié)構(gòu)描述一棵樹的邏輯結(jié)構(gòu)可以用二元組描述為：

Tree=(root,F)數(shù)據(jù)元素根結(jié)點(diǎn)包含m(m≥0)棵樹的森林F=(T1,T2,…,Tm)Ti=(ri

,Fi

)Ti

稱做根root

的第i

棵子樹。當(dāng)m≠0時(shí)，在樹根和其子樹森林之間存在下列關(guān)系：

RF={<root,ri

>|i=1,2,…,m,m>0}RF={<A,B

>,<A,C

>,<A,D

>}Tree=(A,F)F=(T1,T2,T3)T1=(B,F1)T2=(C,F2)T3=(D,F3)……r1F1={<B,E

>,<B,F

>}r2F2={<C,G

>}r3F3={<D,H

>,<D,I

>,<D,J

>}……EFGHIABCDJKLM樹的抽象數(shù)據(jù)類型定義：ADTTree{

數(shù)據(jù)對(duì)象

D：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系

R：（略）

基本操作P：

{結(jié)構(gòu)初始化}

InitTree(&T)；

操作結(jié)果：構(gòu)造空樹T。

CreateTree(&T,definition)；

初始條件：

definition給出樹T的定義。

操作結(jié)果：按definition構(gòu)造樹T。

{銷毀結(jié)構(gòu)}

DestroyTree(&T)；

初始條件：樹T存在。操作結(jié)果：銷毀樹T。

{引用型操作}

TreeEmpty(T)

初始條件：樹T存在。

操作結(jié)果：若T為空樹，則返回TURE，否則FALSE。

TreeDepth(T)

初始條件：樹T存在。

操作結(jié)果：返回T的深度。Root(T)

初始條件：樹T存在。操作結(jié)果：返回T的根。Value(T,cur_e)；

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回cur_e的值。

Assign(T,cur_e,value)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。

Parent(T,cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。

LeftChild(T,cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。RightSibling(T,cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。TraverseTree(T,Visit())；

初始條件：樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的函數(shù)。

操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)

Visit()一次且至多一次。一旦Visit()

失敗，則操作失敗。{加工型操作}ClearTree(&T)；

初始條件：樹T存在。

操作結(jié)果：將樹T清為空樹。InsertChild(&T,&p,i,c)；

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p

所指結(jié)點(diǎn)的度+1，非空樹c與T不相交。

操作結(jié)果：插入c為T中p指結(jié)點(diǎn)的第i棵子樹。

DeleteChild(&T,&p,i)；

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，

1≤i≤p所指結(jié)點(diǎn)的度。

操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹。}ADTTree樹的表示形式

1．樹形表示法

A空樹AB僅含有根結(jié)點(diǎn)的樹2．嵌套集合（文氏）表示法ABEFKLDHIMJCGEFGHIABCDJKLM3．凹入表示法ABEKLFCGDHMIJ▲4．廣義表表示法EFGHIABCDJKLM(A(B(E(K,L),F),C(G),D(H(M),I,J)))6.2二叉樹二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡(jiǎn)單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。6.2.1二叉樹的定義二叉樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。定義特點(diǎn)1、每個(gè)結(jié)點(diǎn)最多有倆孩子(二叉樹中不存在度大于2的結(jié)點(diǎn))。2、子樹有左右之分，其次序不能顛倒。3、二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說(shuō)明它是左子樹，還是右子樹。樹當(dāng)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，就無(wú)須區(qū)分它是左還是右的次序。（也就是二叉樹每個(gè)結(jié)點(diǎn)位置或者說(shuō)次序都是固定的，可以是空，但是不可以說(shuō)它沒(méi)有位置，而樹的結(jié)點(diǎn)位置是相對(duì)于別的結(jié)點(diǎn)來(lái)說(shuō)的，沒(méi)有別的結(jié)點(diǎn)時(shí)，它就無(wú)所謂左右了），因此二者是不同的。這是二叉樹與樹的最主要的差別。二叉樹不是樹的特殊情況，它們是兩個(gè)概念。注AB具有兩個(gè)結(jié)點(diǎn)的樹只有一種狀態(tài)ABAB具有兩個(gè)結(jié)點(diǎn)的二叉樹有兩種狀態(tài)

二叉樹的5種基本形態(tài)

(a)空二叉樹(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹

(e)根和左右子樹注：雖然二叉樹與樹概念不同，但有關(guān)樹的基本術(shù)語(yǔ)對(duì)二叉樹都適用。二叉樹的抽象數(shù)據(jù)類型定義：

ADTBinaryTree{

數(shù)據(jù)對(duì)象

D：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系

R：（略）

基本操作

P：

{結(jié)構(gòu)初始化}

InitBiTree(&T);

操作結(jié)果：構(gòu)造空二叉樹T。

CreateBiTree(&T,definition);

初始條件：definition給出二叉樹T的定義。

操作結(jié)果：按definition構(gòu)造二叉樹T。

{銷毀結(jié)構(gòu)}

DestroyBiTree(&T);

初始條件：二叉樹T存在。

操作結(jié)果：銷毀二叉樹

T。

{引用型操作}

BiTreeEmpty(T);

初始條件：二叉樹T存在。

操作結(jié)果：若T為空二叉樹，則返回TRUE，否則返回

FALSE。

BiTreeDepth(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。

Root(T);

初始條件：二叉樹T存在。

操作結(jié)果：返回T的根。

Value(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的值。

Parent(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。

LeftChild(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左孩子。若e無(wú)左孩子則返回“空”。

RightChild(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的右孩子。若e無(wú)右孩子則返回“空”。

LeftSibling(T,e);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左兄弟。若e是其雙親的左孩子或無(wú)左兄弟，則返回“空”。

RightSibling(T,e);

初始條件：二叉樹T存在，e是T的結(jié)點(diǎn)。

操作結(jié)果：返回e的右兄弟。若e是其雙親的右孩子或無(wú)右兄弟，則返回“空”。

PreOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：先序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

InOrderTraverse(T,vsit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：中序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。

PostOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：后序遍歷

T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

LevelOrderTraverse(T,visit());

初始條件：二叉樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：按層次遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

{加工型操作}

ClearBiTree(&T);

初始條件：二叉樹T存在。

操作結(jié)果：將二叉樹T清為空樹。

Assign(&T,&e,value);

初始條件：二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)e賦值為value。

InsertChild(&T,p,LR,c);

初始條件：二叉樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR

為0或1，非空二叉樹c與T不相交且右子樹為空。

操作結(jié)果：根據(jù)LR為0或1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹。p所指結(jié)點(diǎn)原有左或右子樹成為c的右子樹。

DeleteChild(&T,p,LR);

初始條件：二叉樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，LR

為0或1。

操作結(jié)果：根據(jù)LR為0或1，刪除T中p所指結(jié)點(diǎn)的左或右子樹。}ADTBinaryTree

6.2.2二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i

層上至多有2

i-1個(gè)結(jié)點(diǎn)(i≥1)。證：采用歸納法證明此性質(zhì)。歸納基：當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2

i-1=20=1，命題成立。歸納假設(shè)：設(shè)對(duì)所有的j(1≤j<i)，命題成立，即第j

層上至多有2j-1

個(gè)結(jié)點(diǎn)。那么可以證明j＝i

時(shí)命題也成立。歸納證明：由歸納假設(shè)可知，第i–1層上至多有2

i-2個(gè)結(jié)點(diǎn)。由于二叉樹每個(gè)結(jié)點(diǎn)的度最大為2，故在第i

層上最大結(jié)點(diǎn)數(shù)為第i–1層上最大結(jié)點(diǎn)數(shù)的2倍，即：

2×2

i–2＝2

i–1。證畢。性質(zhì)2：深度為k

的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)（k≥1)。證：由性質(zhì)1可知，深度為k

的二叉樹的最大結(jié)點(diǎn)數(shù)為：證畢。性質(zhì)3：對(duì)任何一棵二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證：設(shè)n1

為二叉樹T

中度為1的結(jié)點(diǎn)數(shù)。因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)均≤2，所以其結(jié)點(diǎn)總數(shù)為：

n=n0+n1+n2再看二叉樹中的分支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)B

為分支總數(shù)，則有：

n=B＋1由于這些分支都是由度為1和2的結(jié)點(diǎn)射出的，所以有：

B=n1+2n2

于是有：n=B+1＝n1+2n2+1

所以有：n0+n1+n2=n1+2n2+1

即：n0=n2+1證畢。滿二叉樹(Fullbinarytree)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大。葉子全部在最底層。編號(hào)規(guī)則：從根結(jié)點(diǎn)開始，自上而下，自左而右。一棵深度為k

且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。2453671完全二叉樹(Completebinarytree)深度為k

的具有n

個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k

的滿二叉樹中編號(hào)為1~n

的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。特點(diǎn)：葉子只可能分布在層次最大的兩層上。

對(duì)任一結(jié)點(diǎn)，如果其右子樹的最大層次為l，則其左子樹的最大層次必為l

或l+1。滿二叉樹完全二叉樹是定一不一定是

245361完全二叉樹245361非完全二叉樹完全二叉樹的性質(zhì)性質(zhì)4：具有n

個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。證：假設(shè)此二叉樹的深度為k，則根據(jù)性質(zhì)2及完全二叉樹的定義得到：2k-1–1<n≤2k–1

或2k-1≤n<2k

取對(duì)數(shù)得：k–1≤log2n<k

因?yàn)閗

是整數(shù)，所以有：

k＝log2n+1▲性質(zhì)5：如果對(duì)一棵有n

個(gè)結(jié)點(diǎn)的完全二叉樹(深度為log2n+1)

的結(jié)點(diǎn)按層序編號(hào)(從第1層到第log2n+1層，每層從左到右)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)，有：

(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)i/2。

(2)如果2i>n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。

(3)如果2i+1>n，則結(jié)點(diǎn)i

無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i+1。證：(1)可以從(2)和(3)推出，所以先證明(2)和(3)。

對(duì)于i＝1，由完全二叉樹的定義，其左孩子是結(jié)點(diǎn)2=2i，若2=2i>n=1，即不存在結(jié)點(diǎn)2，此時(shí)，結(jié)點(diǎn)i

無(wú)左孩子。(2)得證。i1結(jié)點(diǎn)i

的右孩子也只能是結(jié)點(diǎn)3=2i+1，若

3=2i+1>n，即不存在結(jié)點(diǎn)

3，此時(shí)結(jié)點(diǎn)i

無(wú)右孩子。

(3)得證。2i22i+132i2

(1)設(shè)第j(1≤j≤log2n)層的第一個(gè)結(jié)點(diǎn)的編號(hào)為i(由二叉樹的定義和性質(zhì)2知i=2

j–1)，則其左孩子必為第j+1層的第一個(gè)結(jié)點(diǎn)，其編號(hào)為2

j＝2×2

j–1＝2i。

1

…第j

層

…23

對(duì)于

i>1，可分為兩種情況：第j–1層第j+1層

i2

j-12i=2j

…2i+12

j-1-1=2j-1

如果2i>n，則無(wú)左孩子。(2)得證。其右孩子必定為第j+1層的第二個(gè)結(jié)點(diǎn)，編號(hào)為2i+1。若2i+1>n，則無(wú)右孩子。(3)得證。

(2)設(shè)第j(1≤j≤log2n)層的某個(gè)結(jié)點(diǎn)的編號(hào)為i(2

j–1≤i<2

j–1)，且2i+1<n，其左孩子為2i，右孩子為2i+1。

2i…1…第j

層

…2i第j–1層第j+1層2

j-1-1i2

j-1…2i+12

j-1……i+12i2i+22i+3若它有左孩子，則其編號(hào)必定為：2i+2=2(i+1)，(2)得證。若它有右孩子，則其編號(hào)必定為：2i+3=2(i+1)+1。(3)得證。

則編號(hào)為i+1的結(jié)點(diǎn)是編號(hào)為i

的結(jié)點(diǎn)的右兄弟或堂兄弟。下面證明(1)。當(dāng)i=1時(shí)：此結(jié)點(diǎn)就是根，因此無(wú)雙親。當(dāng)i>1時(shí)：如果i

為左孩子，且i

的雙親為p，則有i=2p，

p=i/2=i/2，即i/2

是i

的雙親；i

為偶數(shù)i

為奇數(shù)如果i為右孩子，且i

的雙親為p，則有i＝2p+1，

p=

(i-1)/2=i/2–1/2=i/2，即i/2

是i

的雙親。證畢。6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)結(jié)構(gòu)

完全二叉樹：用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)結(jié)點(diǎn)元素，即將編號(hào)為i

的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i–1的分量中。123456123450

6一般二叉樹：將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。

這種順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹245361完全二叉樹245361非完全二叉樹123456最壞情況：深度為k

的且只有k

個(gè)結(jié)點(diǎn)的右單支樹需要長(zhǎng)度為2k-1的一維數(shù)組。

1

0

20003表示方式：

#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)

typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//

0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)

SqBiTree

bt;231右單支樹00002、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)方式二叉樹結(jié)點(diǎn)的特點(diǎn)lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)datarchild

lchild

data

parentlchildrchildAB

CD

E

F

G^^^^^^^^AB

CD^^^^^二叉鏈表在n

個(gè)結(jié)點(diǎn)的二叉鏈表中，有

n+1個(gè)空指針域。ABCDEFGABCDtypedef

struct

BiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

struct

BiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;C語(yǔ)言的類型描述如下：

ABCDEF

G^^^^^^^^^三叉鏈表ABCDEFG▲parentdatalchild

rchild

lchilddataparentrchild

結(jié)點(diǎn)結(jié)構(gòu)6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹（重點(diǎn)，是進(jìn)行其他運(yùn)算的基礎(chǔ)）遍歷概念順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。

“訪問(wèn)”的含義很廣，可以是對(duì)結(jié)點(diǎn)作各種處理，如：輸出結(jié)點(diǎn)的信息、修改結(jié)點(diǎn)的數(shù)據(jù)值等，但要求這種訪問(wèn)不破壞原來(lái)的數(shù)據(jù)結(jié)構(gòu)。遍歷方法依次遍歷二叉樹中的三個(gè)組成部分，便是遍歷了整個(gè)二叉樹假設(shè)：L：遍歷左子樹

D：訪問(wèn)根結(jié)點(diǎn)

R：遍歷右子樹則遍歷整個(gè)二叉樹方案共有：遍歷目的得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。根結(jié)點(diǎn)

左子樹右子樹DLR、LDR、LRD、DRL、RDL、RLD六種。若規(guī)定先左后右，則只有前三種情況：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。根結(jié)點(diǎn)

左子樹右子樹

先序遍歷二叉樹的操作定義：

若二叉樹為空，則空操作；否則

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。先序遍歷的順序?yàn)椋篈BC先序遍歷的順序?yàn)椋篈BELDHMIJA

B

C

A

B

D

E

LH

M

I

J

中序遍歷二叉樹的操作定義：

若二叉樹為空，則空操作；否則

(1)中序遍歷左子樹；

(2)訪問(wèn)根結(jié)點(diǎn)；

(3)中序遍歷右子樹。中序遍歷的順序?yàn)椋築AC中序遍歷的順序?yàn)椋篍LBAMHIDJA

B

C

A

B

D

E

LH

M

I

J

后序遍歷二叉樹的操作定義：

若二叉樹為空，則空操作；否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問(wèn)根結(jié)點(diǎn)。后序遍歷的順序?yàn)椋築CA后序遍歷的順序?yàn)椋篖EBMIHJDA

A

B

C

A

B

D

E

LH

M

I

J

--/+×abcdef例：請(qǐng)寫出下圖所示二叉樹的先序、中序和后序遍歷順序。遍歷結(jié)果：先序：-+a×b

-

cd/ef

中序：a+b×c

-

d

-

e/f后序：abcd

-×+ef/-表達(dá)式的前綴表示（波蘭式）表達(dá)式的中綴表示

表達(dá)式的后綴表示（逆波蘭式）先序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)：StatusPreOrderTraverse(BitreeT,Visit){//最簡(jiǎn)單的Visit函數(shù)是：

//StatusPrintElement(TElemTypee)//{Printf(e);//實(shí)用時(shí)加上格式串。

//returnOK;}

//調(diào)用實(shí)例：PreOrderTraverse(T,PrintElement);

if(T){if(Visit(Tdata))if(PreOrderTraverse(Tlchild,Visit))if(PreOrderTraverse(Trchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)AB

CD

E

F

G^^^^^^^^T中序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)：StatusInOrderTraverse(BitreeT,Visit){if(T){if(InOrderTraverse(Tlchild,Visit))if(Visit(Tdata))if(InOrderTraverse(Trchild,Visit))returnOK;returnERROR;}elsereturnOK;}//InOrderTraverse

AB

CD

E

F

G^^^^^^^^T后序遍歷二叉樹基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)：StatusPostOrderTraverse(BitreeT,Visit){if(T){if(PostOrderTraverse(Tlchild,Visit))if(PostOrderTraverse(Trchild,Visit))if(Visit(Tdata))

returnOK;returnERROR;}elsereturnOK;}//PostOrderTraverse

AB

CD

E

F

G^^^^^^^^T以中序遍歷為例來(lái)說(shuō)明中序遍歷二叉樹的遞歸過(guò)程第一次經(jīng)過(guò)第二次經(jīng)過(guò)第三次經(jīng)過(guò)Ф

BDФ

Ф

ABCED▲中序遍歷二叉樹基本操作的非遞歸算法在二叉鏈表上的實(shí)現(xiàn)：StatusInOrderTraverse(BiTreeT,Visit){InitStack(S);Push(S,T);//根指針進(jìn)棧

while(!StackEmpty(S){while(GetTop(S,p)&&p)Push(S,plchild);//向左走到盡頭。

Pop(S,p);//空指針退棧

if(!StackEmpty(S){//訪問(wèn)結(jié)點(diǎn)，向右一步

Pop(S,p);if(!Visit(pdata))returnERROR;Push(S,prchild);}//if}//whilereturnOK;}//InOrderTraverse－＋

a

^^×

b

^^－

c

^^

d

^^／

e

^^

f

^^－－／＋×abcdefTpppa+

b×

c－

d－

e／

f中序遍歷二叉樹基本操作的非遞歸算法在二叉鏈表上的實(shí)現(xiàn)：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){push(S,p);p=plchild;}//根指針進(jìn)棧，遍歷左子樹。

else{//根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹。

Pop(S,p);if(!Visit(pdata))returnERROR;p=prchild;}//else}//whilereturnOK;}//InOrderTraverse－＋

a

×

b

－

c

d

／

e

f

－－／＋×abcdefT二叉樹其它操作算法舉例統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)實(shí)現(xiàn)這個(gè)操作只要對(duì)二叉樹“遍歷”一遍，并在遍歷過(guò)程中對(duì)“葉子結(jié)點(diǎn)計(jì)數(shù)”即可。顯然這個(gè)遍歷的次序可以隨意，只是為了在遍歷的同時(shí)進(jìn)行計(jì)數(shù)，需要在算法的參數(shù)中設(shè)一個(gè)“計(jì)數(shù)器”。voidCountLeaf(BiTreeT,int&count)

{//先序遍歷二叉樹，以count返回二叉樹中葉子結(jié)點(diǎn)的數(shù)目

if(T){

if((!TLchild)&&(!TRchild))//無(wú)左、右子樹

count++;

//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(TLchild,count);

CountLeaf(TRchild,count);

}//if

}//CountLeaf

問(wèn)題：能否將count設(shè)成函數(shù)中的局部變量，然后以count的值作為函數(shù)值返回？答案：不能！

原因：算法需要在遞歸執(zhí)行的過(guò)程中對(duì)葉子“累加計(jì)數(shù)”。求二叉樹的深度（先序）二叉樹的深度=葉子結(jié)點(diǎn)所在層次的最大值。voidBiTreeDepth(BiTreeT,intlevel,int&depth)

{//level為T所指結(jié)點(diǎn)所在層次，其初值為1，

//depth為當(dāng)前求得的最大層次，其初值為0。

if(T){

if(level>depth)depth=level;

BiTreeDepth(TLchild,level+1,depth);

BiTreeDepth(TRchild,level+1,depth);

}//if

}//BiTreeDepth^^^^^^^BCDEGFT求二叉樹的深度（后序）二叉樹的深度=MAX（左子樹深度，右子樹深度）+1。voidBiTreeDepth(BiTreeT)

{if(!T)depth=0;else{

depthleft=BiTreeDepth(TLchild);

depthright=BiTreeDepth(TRchild);depth=max(depthleft,depthright)+1;

}returndepth;

}//BiTreeDepth

^^^^^^^BCDEGFT^建立二叉樹的存儲(chǔ)結(jié)構(gòu)——二叉鏈表（先序）StatusCreateBiTree(BiTree&T){

scanf(&ch);

if(ch==‘’)T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

Tdata=ch;//生成根結(jié)點(diǎn)

CreateBiTree(Tlchild);//構(gòu)造左子樹

CreateBiTree(Trchild);//

構(gòu)造右子樹

}

returnOK;

}//CreateBiTree

^^^^^^^DABEFGC

對(duì)右圖所示二叉樹，按下列順序讀入字符：

ABCDEGFABCDEGF▲ABCDEGFT6.3.2線索二叉樹遍歷結(jié)果：先序：-+a×b

-

cd/ef

中序：a+b×c

-

d

-

e/f后序：abcd

-×+ef/-問(wèn)題1：為什么要研究線索二叉樹？

非線性結(jié)構(gòu)線性結(jié)構(gòu)轉(zhuǎn)化問(wèn)題2：如何保存結(jié)果以避免重復(fù)遍歷？辦法：

1、另辟存儲(chǔ)空間存放遍歷結(jié)果。

需要付出額外的存儲(chǔ)花銷。

--/+×abcdef遍歷結(jié)果：先序：-+a×b

-

cd/ef

中序：a+b×c

-

d

-

e/f后序：abcd

-×+ef/-2、在原二叉鏈表的每個(gè)結(jié)點(diǎn)上增加兩個(gè)指針域。－＋

a

×

b－

c

d／

e

f000000001111001111111101線索化：對(duì)二叉樹按某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò)程。二叉樹線索化的目的：利用線索化后的二叉樹中的線索就可以直接找到某些結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)。

3、在原二叉鏈表的存儲(chǔ)空間內(nèi)反映遍歷結(jié)果。中序線索鏈表--/+×abcdef中序線索二叉樹thrt

二叉樹線索化的實(shí)質(zhì)：在遍歷過(guò)程中用線索取代空指針。

在線索樹（中序）中找結(jié)點(diǎn)后繼的方法：

1、若右鏈?zhǔn)蔷€索，則直接指示后繼；

2、若右鏈?zhǔn)侵羔?，則“右孩找左”。即：中序后繼右孩找左。在線索樹（中序）中找結(jié)點(diǎn)前驅(qū)的方法：

1、若左鏈?zhǔn)蔷€索，則直接指示前驅(qū)；

2、若左鏈?zhǔn)侵羔?，則“左孩找右”。即：中序前驅(qū)左孩找右。在線索樹上進(jìn)行遍歷的方法：

1、從序列中的第一個(gè)結(jié)點(diǎn)起，依次找后繼，直至后繼為空。

2、從序列中的最后一個(gè)結(jié)點(diǎn)起，依次找前驅(qū)，直至前驅(qū)為空。

線索二叉樹的存儲(chǔ)表示typedef

enum

PointerTag

{Link,Thread};

//Link==0：指針，Thread==1：線索

typedef

struct

BiThrNode{

TElemTypedata;

struct

BiThrNode*lchild,*rchild;//左右指針

PointerTag

LTag,RTag;//左右標(biāo)志

}BiThrNode,*BiThrTree;線索鏈表的遍歷算法（中序找后繼法）：StatusInOrderTraverse_Thr(BiThrTreeT,Visit){p=T－>lchild;

while(p!=T)

{while(p－>LTag==0)p=p－>lchild;

if(!Visit(p－>data))returnERROR;

while(p－>

RTag==1&&p－>

rchild!=T)

{p=p－>

rchild;Visit(p－>data);}

p=p－>

rchild;}

returnOK;

}//InOrderTraverse_Thr

－＋

a

×

b－

c

d／

e

f000000001111001111111101T

按中序建立線索鏈表（按中序線索化二叉樹）

1、若結(jié)點(diǎn)沒(méi)有左子樹，則令其左指針指向它的“前驅(qū)”并將左指針類型標(biāo)志改為“1”；

2、若結(jié)點(diǎn)沒(méi)有右子樹，則令其右指針指向它的“后繼”并將右指針類型標(biāo)志改為“1”；

3、為了獲取“前驅(qū)”的信息，需要在遍歷過(guò)程中添加一個(gè)指針

pre，令其始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)。若指針p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)，則pre指向它的前驅(qū)。－＋

a

×

b－

c

d／

e

fT

StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建頭結(jié)點(diǎn)

Thrt

－>rchild=Thrt;//右指針回指

if(!T)Thrt

－>lchild=Thrt;//若二叉樹空，則左指針回指

else{Thrt

－>lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進(jìn)行中序線索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一個(gè)結(jié)點(diǎn)線索化

Thrt

－>rchild=pre;}

returnOK;

}//InOrderThreadingvoidInThreading(BiThrTreep){

if(p){InThreading(p－>lchild);//左子樹線索化

if(!p－>

lchild){p－>

LTag=1;p－>

lchild=pre;}

if(!pre－>

rchild){pre－>

RTag=1;pre－>

rchild=p;}pre=p;//保持pre指向p的前驅(qū)

InThreading(p－>

rchild);}

//右子樹線索化

}

}//InThreading

－＋

a

×

b－

c

d／

e

f111111111111T

0Thrt

pre

▲StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建頭結(jié)點(diǎn)

Thrt

－>rchild=Thrt;//右指針回指

if(!T)Thrt

－>lchild=Thrt;//若二叉樹空，則左指針回指

else{Thrt

－>lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進(jìn)行中序線索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一個(gè)結(jié)點(diǎn)線索化

Thrt

－>rchild=pre;}

returnOK;

}//InOrderThreading－＋

a

×

b－

c

d／

e

f1111111111111T

0Thrt

pre

作業(yè)：6.15~6.17選擇題1.在線索化二叉樹中，t所指結(jié)點(diǎn)沒(méi)有左子樹的充要條件是（）（A）t->lchild=NULL（B）t->ltag=1（C）t->ltag=1且t->lchild=NULL（D）以上都不對(duì)二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索，這種說(shuō)法（）（A）正確（B）錯(cuò)誤實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息。雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的位置。6.4樹和森林6.4.1樹的存儲(chǔ)結(jié)構(gòu)

1雙親表示法

parent0R-11A02B03C04D15E1F3G6H6K6數(shù)組下標(biāo)特點(diǎn)：找雙親容易，找孩子難。r=0n=10RBACDEFHGKdatatypedef

struct

PTNode{

TElemTypedata;

intparent;//雙親位置域

}PTNode;#defineMAX_TREE_SIZE100C語(yǔ)言的類型描述:

dataparent結(jié)點(diǎn)結(jié)構(gòu):typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹結(jié)構(gòu)：0R-11A02B03C04D15E1F3G6H6K6dataparent數(shù)組下標(biāo)r=0n=10lchild

data

rchildlchilddataparent

rchild

datachild1child2……childd

datachild1child2……childd

parent二叉樹的結(jié)點(diǎn)結(jié)構(gòu)data

parentlchildrchilddata

parentchild1

childd

……2孩子表示法（樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）

1)多重鏈表d

叉鏈表AB^^^C^^^D^E^^^F^^^

結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度

d。ABCDEFdatachild1child2……childd

d+1叉鏈表多重鏈表在有n

個(gè)結(jié)點(diǎn)、度為

d

的樹的d

叉鏈表中，有

n×(d－1)＋1個(gè)空鏈域。

datachild1child2……childd

parent

A3B0C0D2E0F0節(jié)約存儲(chǔ)空間但操作不方便ABCDEFdatadegreechild1child2……childd

datadegreechild1child2……childd

parent

結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)不相等，

為該結(jié)點(diǎn)的度degree。A3^B0C0D2E0F0孩子鏈表：把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成是一個(gè)線性表，用單鏈表存儲(chǔ)，則n

個(gè)結(jié)點(diǎn)有n

個(gè)孩子鏈表（葉子的孩子鏈表為空表）。而n

個(gè)頭指針又組成一個(gè)線性表，用順序表（含

n

個(gè)元素的結(jié)構(gòu)數(shù)組）存儲(chǔ)。

0A1B^2C3D^4R5E^FG^H^K^datafirstchild

數(shù)組下標(biāo)r=4n=10

3

5^

6^

0

1

2^

7

8

9^4440-102666特點(diǎn)：找孩子容易，找雙親難。帶雙親的孩子鏈表RBACDEFHGK孩子鏈表typedef

struct

CTNode{

intchild;

struct

CTNode*next;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)：childnextC語(yǔ)言的類型描述：

typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子鏈表頭指針}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)：

datafirstchild

typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置}CTree;樹結(jié)構(gòu)：RBACDEFHGK3孩子兄弟表示法（二叉樹表示法，二叉鏈表表示法）實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)

R^

A^

D^

B^

E^

C^

F^^

G^

H^

K^孩子兄弟鏈表的結(jié)構(gòu)形式與二叉鏈表完全相同，但存儲(chǔ)結(jié)點(diǎn)中指針的含義不同：二叉鏈表中結(jié)點(diǎn)的左右指針?lè)謩e指向該結(jié)點(diǎn)的左右孩子；而孩子兄弟鏈表結(jié)點(diǎn)的左右指針?lè)謩e指向它的“長(zhǎng)子”和“大弟”。注這種解釋上的不同正是樹與二叉樹相互轉(zhuǎn)化的內(nèi)在基礎(chǔ)typedef

s