第六章樹與二叉樹教案-二叉樹的類型定義-存儲結(jié)構(gòu)-遍歷-哈夫曼樹與哈夫曼編碼

第六章樹和二叉樹教案二叉樹的類型定義存儲結(jié)構(gòu)遍歷哈夫曼樹與哈夫曼編碼2樹是常用的數(shù)據(jù)結(jié)構(gòu)家族各種組織結(jié)構(gòu)操作系統(tǒng)中的文件管理編譯原理中的源程序語法結(jié)構(gòu)信息系統(tǒng)管理。。。。6.1樹的類型定義6.2二叉樹的類型定義6.2.3

二叉樹的存儲結(jié)構(gòu)6.3二叉樹的遍歷6.3.2線索二叉樹6.4樹和森林的表示方法6.4.3樹和森林的遍歷6.6哈夫曼樹與哈夫曼編碼6.1樹的類型定義5樹(tree)是n(n>=0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)。當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,……Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：①非空樹中至少有一個結(jié)點——根②樹中各子樹是互不相交的集合樹的定義ABCDEFGHIJKL6A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹空樹

n=0n=1n>1DABCEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:樹的圖示表示法樹的廣義表表示法8樹的表示法主要有5種圖形表示法嵌套集合表示法廣義表表示法凹入表示法左孩子－右兄弟表示法9ABDCHIJMFEGKL樹的嵌套集合表示法DABCEFGHIJMKL11樹的其它表示方式凹入表示嵌套集合廣義表DABCEFGHIJMKL樹的凹入表示法ABEKLFCGDHMIJ樹的抽象數(shù)據(jù)類型定義數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

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

基本操作：查找類

插入類刪除類

Root(T)//求樹的根結(jié)點

查找類：Value(T,cur_e)//求cur_e結(jié)點的元素值

Parent(T,cur_e)//求cur_e結(jié)點的雙親結(jié)點LeftChild(T,cur_e)//求cur_e結(jié)點的最左孩子RightSibling(T,cur_e)//求cur_e結(jié)點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給cur_e結(jié)點賦值InsertChild(&T,&p,i,c)//插入c為T中P所指結(jié)點的第i棵子樹

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹基本術(shù)語結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)（子樹的個數(shù)）樹中所有結(jié)點的度的最大值度為零的結(jié)點

度大于零的結(jié)點（包含根和中間節(jié)點）DHIJM組織結(jié)構(gòu)樹教師學(xué)生其他人員99級2000級2001級2002級……山東理工大學(xué)計算機系電子系自控系……葉子根子樹趙老根趙躍進趙小康趙改革趙開放趙解放趙抗美趙衛(wèi)兵趙永紅家譜樹(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1，根的孩子為第二層，如果某節(jié)點在第L層,則其子樹的根在L+1層。樹中葉子結(jié)點所在的最大層次24路徑：孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟結(jié)點祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成根結(jié)點的層次為1，根的孩子為第二層，第l層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次25(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點28~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結(jié)點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)

其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點（非線性結(jié)構(gòu)）分隔符30一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且子樹之間互不相交。

樹的存儲結(jié)構(gòu)

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？特點：——仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

樹的邏輯結(jié)構(gòu)31討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？復(fù)原困難討論2：樹的順序存儲方案應(yīng)該怎樣制定？可用多重鏈表：一個前趨指針，n個后繼指針。

細節(jié)問題：

樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？

即應(yīng)該設(shè)計成“等長”還是“不等長”？

缺點：

等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹(二叉樹)。可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存。重大缺陷：解決思路：32樹的運算要明確：1.普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)。2.二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對樹結(jié)點能夠“遍歷”的基礎(chǔ)上！遍歷——指每個結(jié)點都被訪問且僅訪問一次，不遺漏不重復(fù)本章重點：二叉樹的表示和實現(xiàn)6.2

二叉樹的類型定義346.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。1. 二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹的運算（6.3節(jié)）35二叉樹的抽象數(shù)據(jù)類型定義ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:D是具有相同特性的數(shù)據(jù)元素的集合。若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明

②Dl∩Dr=Φ//關(guān)于子樹不相交的說明

36基本操作P：20個}ADTBinaryTree37二叉樹是n(n0)個結(jié)點的有限集,它或為空樹(n=0),或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。特點①每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)②二叉樹的子樹有左、右之分，且其次序不能顛倒二叉樹根結(jié)點左子樹右子樹

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。(樹的度最大為2)ABCDEFGHK根結(jié)點左子樹右子樹二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹40A只有根結(jié)點的二叉樹

空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空五種基本形態(tài)問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？

有5種

二叉樹的主要基本操作：查找類插入類刪除類Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());查找類

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入類ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);刪除類二叉樹

的重要特性二叉樹的性質(zhì)

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

層上至多有2i-1個結(jié)點。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；當(dāng)j=i-1時,命題成立最多有2i-2

個節(jié)點二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-2

2=2i-1

。性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1

。（等比數(shù)列求和）

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點（0度節(jié)點）、n2個度為

2

的結(jié)點，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。49證明：∵

二叉樹中全部結(jié)點數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點數(shù)＋2度結(jié)點數(shù))又∵二叉樹中全部結(jié)點數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點)

（除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）而

總分支數(shù)B=n1+2n2(1度結(jié)點必有1個直接后繼，2度結(jié)點必有2個)三式聯(lián)立可得：

n0+n1+n2=

n1+2n2+1,即n0=n2+1物理意義：葉子數(shù)＝2度結(jié)點數(shù)＋1性質(zhì)3:

對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。（編號的規(guī)則為，由上到下，從左到右。）123456789101112131415abcdefghij51完全二叉樹定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。特點：（1）葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。（2）對任一結(jié)點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1。12345678910111234567891210111231145891213671014151231145891267101234567123456

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為

log2n

+1。證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1-1

<n≤2k-1

或2k-1

≤n<2k

即

k-1≤log2n<k

因為k只能是整數(shù)，因此，k=log2n

+154一棵含有n個結(jié)點的二叉樹，可能達到的最大深度和最小深度各是多少？問題：答：最大n,

最小[log2n]+1

1234512345性質(zhì)5：若對含n

個結(jié)點的完全二叉樹從上到下且從左至右進行1

至

n

的編號，則對完全二叉樹中任意一個編號為

i

的結(jié)點：

(1)若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為

i/2

的結(jié)點為其雙親結(jié)點；

(2)若2i>n，則該結(jié)點無左孩子，

否則，編號為2i

的結(jié)點為其左孩子結(jié)點；

(3)若2i+1>n，則該結(jié)點無右孩子結(jié)點，

否則，編號為2i+1

的結(jié)點為其右孩子結(jié)點。56性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1≤i≤n)，有：

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

(2)如果2i>n，則結(jié)點i無左孩子；如果2i≤n，則其左孩子是2i。

(3)如果2i+1>n，則結(jié)點i無右孩子；如果2i+1≤n，則其右孩子是2i+1。123456789121011572.深度為Ｋ的二叉樹的結(jié)點總數(shù)，最多為

個。

Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k1.樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度DCC3.深度為9的二叉樹中至少有

個結(jié)點。

Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－1練習(xí)：6.2.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表?9abcde0000fg12345678910111、順序存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素。特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹abcdefg1234567891011二叉樹的存儲結(jié)構(gòu)123456789101112345678910111234567891011#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//1號單元存儲根結(jié)點SqBiTreebt;一、二叉樹的順序存儲表示61#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;二叉樹的順序存儲表示顯然，這種存儲表示方法只適合于完全二叉樹，對于一般的二叉樹將造成存儲空間的很大浪費。因此二叉樹的常用存儲結(jié)構(gòu)是鏈表。思考：一個深度為k且只有k個結(jié)點的右單支樹需要的數(shù)組存儲空間為多少？例如:ABCDEF

ABD0C0E000000F

12345678910111213142511437一般樹按完全二叉的方式存儲非常浪費空間！深度為K的單支樹，需要2k-1個空間（k=20,1M的空間）63二叉樹的遍歷二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表3．線索鏈表ADEBCF

root1.二叉鏈表ABCDEFlchilddatarchild結(jié)點結(jié)構(gòu):typedefstruct

BiTNode

{//結(jié)點結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:ABCDEFG在n個結(jié)點的二叉鏈表中，有n+1個空指針域ABCDEFG^^^^^^^^（1）二叉鏈表typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode，*Bitree;ADEBCF

root

2．三叉鏈表parent

lchilddatarchild結(jié)點結(jié)構(gòu):

typedefstruct

TriTNode

{//結(jié)點結(jié)構(gòu)

structTriTNode

*parent;//雙親指針

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:（2）三叉鏈表typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode

,*Bitree;lchilddata

parentrchildABCDEFG

A

B

C

D

E

F

G^^^^^^^^^71

順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點的信息等?！氨闅v”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。

而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。

遍歷的用途：它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。6.3二叉樹的遍歷

順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。一、問題的提出（尋找某個節(jié)點）“訪問”的含義可以很廣，如：輸出結(jié)點的信息或判定節(jié)點滿足某些條件等。

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，

每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。

對“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：78先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹。中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹。后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點。按層次遍歷：從上到下、從左到右訪問各結(jié)點。二叉樹的遍歷ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法：ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B84-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：用二叉樹表示算術(shù)表達式-+a*b-cd/ef前綴表達式a+b*c-d-e/f中綴表達式abcd-*+ef/-后綴表達式-+/a*efb-cd三、算法的遞歸描述voidPreOrderTraverse(BiTreeT,void(*visit)(TElemType&e)){//T為樹根的指針

if(T){

visit(T->data);//訪問結(jié)點

PreOrderTraverse(T->lchild,visit);//遍歷左子樹

PreOrderTraverse(T->rchild,visit);//遍歷右子樹

}}ADB

T

ABDvoidInOrderTraverse(BiTreeT,void(*visit)(TElemType&e)){//中序遍歷二叉樹，T為樹根的指針

if(T){

InOrderTraverse(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問結(jié)點

InOrderTraverse(T->rchild,visit);//遍歷右子樹

}}ADB

T

BADvoidPostOrderTraverse(BiTreeT,void(*visit)(TElemType&e)){//后序遍歷二叉樹，T為樹根的指針

if(T){

PostOrderTraverse(T->lchild,visit);//遍歷左子樹

PostOrderTraverse(T->rchild,visit);//遍歷右子樹

visit(T->data);//訪問結(jié)點

}}ADB

T

BDA

可以這樣理解：無論先序、中序、后序遍歷二叉樹，遍歷時的搜索路線是相同的：從根節(jié)點出發(fā)，逆時針沿二叉樹外緣移動對每個節(jié)點均途徑三次。先序遍歷：第一次經(jīng)過節(jié)點時訪問。中序遍歷：第二次經(jīng)過節(jié)點時訪問。后序遍歷：第三次經(jīng)過節(jié)點時訪問。ABΦΦΦ123先序：AB中序：AB后序：BA123∧

a∧

+

*

//\d

/\

-root∧e∧∧

b∧∧

c∧-+*abc/de

a+

*

b

-c

d

/

e

+

/

e

d*-

a

b

cLDR:a*b-c+d/e

LRD:abc-*de/+DLR:+*a-bc/de中序遍歷二叉樹的非遞歸算法1StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);Push(S,T);//根指針進棧While(!StadkEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到盡頭

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

if(!StackEmpty(S)){//訪問結(jié)點,向右一步

Pop(S,p);if(!visit(p->data))returnERROR;Push(S,p->rchild);}//endif}//endwhilereturnOK;}//InOrderTraverse中序遍歷二叉樹的非遞歸算法2StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;While(p||!StadkEmpty(S)){

if(p){Push(S,p);p=p->lchild;)}//根指針進棧，遍歷左子樹

else{//根指針退棧，訪問根結(jié)點，遍歷右子樹

Pop(S,p);if(!visit(p->data))returnERROR;p=p->rchild);}//endif}//endwhilereturnOK;}//InOrderTraversevoidPreOrder(BiTreeT){ if(T){ printf("%s",T->data); PreOrder(T->lchild); PreOrder(T->rchild); }}先序遍歷程序：voidInOrder(BiTreeT){ if(T){ InOrder(T->lchild); printf("%s",T->data); InOrder(T->rchild); }}中序遍歷程序：voidPostOrder(BiTreeT){ if(T){ PostOrder(T->lchild); printf("%s",T->data); PostOrder(T->rchild); }}后序遍歷程序：四、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示AB

C

D空樹只含一個根結(jié)點的二叉樹A以字符串“A”表示以字符串表示Status

CreateBiTree(BiTree*T)

{//按前序次序輸入節(jié)點信息

scanf(&ch);

if(ch=='')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//生成根結(jié)點

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}

returnOK;}//CreateBiTree,無頭節(jié)點AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^對于一個一般的二叉樹，僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹。如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？

由二叉樹的先序和中序序列建樹

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3.2

線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？一、何謂線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點的一個線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”ABCDE^D^

C^^B

^E^A

如何保存這種在遍歷過程中得到的信息？最簡單的方法是在每個結(jié)點上增加二個指針域：fwd和bkwd用來指示此結(jié)點在遍歷中的前驅(qū)和后繼結(jié)點。在n個結(jié)點的二叉樹中，有n+1個空鏈域。（空鏈域的個數(shù)=結(jié)點數(shù)*2–分支個數(shù)）

n結(jié)點二叉樹的空鏈域=2*n-(n-1)=n+1我們可以利用這n+1個空鏈域來存儲線索使結(jié)點的存儲密度大大降低對線索鏈表中結(jié)點的約定：

在二叉鏈表的結(jié)點中增加兩個標(biāo)志域，并作如下規(guī)定：若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“Link（指針）”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“Thread（線索）”

。若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“Link（指針）”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“Thread（線索）”。

如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。線索鏈表的結(jié)點定義：

LchildLtagDataRtagRchild

0lchild域指示結(jié)點的左孩子

1rchild域指示結(jié)點的前驅(qū)Ltag=

0lchild域指示結(jié)點的右孩子

1rchild域指示結(jié)點的后繼Rtag=以這種結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表。其中指向結(jié)點前驅(qū)和后繼的指針，叫做線索。加上線索的二叉樹稱之為線索二叉樹。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。typedefstruct

BiThrNod{

TElemTypedata;

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

PointerTagLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

#defineLink0//指針

#defineThread1//線索

typedef

enumPointerTag{

Link,Thread

};

定義枚舉類型：Enum枚舉變量名{枚舉變量的值}二、線索鏈表的遍歷算法:由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。ABCD中序遍歷二叉線索樹：BCAD0A01B0thrt0

11C11D1例如：（對于利用空指針域的結(jié)構(gòu)）

//中序線索化鏈表的遍歷算法

※中序遍歷的第一個結(jié)點？

※在中序線索化鏈表中結(jié)點的后繼？左子樹上處于“最左下”（沒有左子樹）的結(jié)點。若無右子樹，則為后繼線索所指結(jié)點；否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點。statusInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee)){

p=T->lchild;//p指向根結(jié)點

while(p!=T){//空樹或遍歷結(jié)束時，p==T

while(p->LTag==Link)p=p->lchild;//第一個結(jié)點

if(!visit(p->data))returnERROR;

while(p->RTag==Thread&&p->rchild!=T){//訪問后繼結(jié)點

p=p->rchild;Visit(p->data);}//whilep=p->rchild;//p進至其右子樹根

}//while

returnOK

；}//InOrderTraverse_Thr

在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點的前驅(qū)。三、如何建立線索鏈表？StatusInOrderThreading(BiThrTreeThrt,BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點

returnOK;}//InOrderThreading

……if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//處理最后一個結(jié)點

pre->RTag=Thread;

Thrt->rchild=pre;}void

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;

//保持pre指向p的前驅(qū)

InThreading(p->rchild);//右子樹線索化

}//if}//InThreading

6.4樹和森林的表示方法6.4.1樹的存儲結(jié)構(gòu)一、雙親表示法(順序存儲)二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5根的位置：r=0總結(jié)點數(shù)：n=7dataparent一、雙親表示法:

typedefstructPTNode{TElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點結(jié)構(gòu):C語言的類型描述:typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

}PTree;樹結(jié)構(gòu):ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

2dataparent特點：求父親容易求孩子難如何求孩子？需要遍歷整個數(shù)組，找出父親域等于其數(shù)組下標(biāo)的所有結(jié)點。二、孩子表示法:1、多重鏈表：（1）以結(jié)點的度作為孩子鏈域

datadegreechild1child2…childd（2）以樹的度作為孩子鏈域

datachild1child2…childd缺點:結(jié)點不同構(gòu),給操作帶來麻煩

缺點:結(jié)點同構(gòu),但空鏈域較多ABCDEFG0

A1

B2

C3

D4

E5

F6

Gr=0n=7datafirstchild123456-1000224找孩子容易找父親難parent2、孩子鏈表：typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點結(jié)構(gòu):

childnextC語言的類型描述:

typedefstruct{TElemTypedata;

ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;表頭結(jié)點結(jié)構(gòu)

datafirstchildintparent;

dataparentfirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點數(shù)和根結(jié)點的位置

}CTree;樹結(jié)構(gòu):ABCDEFGABCEDFGrootABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法typedefstructCSNode{TElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結(jié)點結(jié)構(gòu):

firstchilddatanextsibling6.4.2樹和二叉樹的轉(zhuǎn)換將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個結(jié)點，除了其左孩子外，去除與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHI要求

掌握將一棵樹轉(zhuǎn)化為二叉樹方法將轉(zhuǎn)化二叉樹還原為一棵樹方法ABCDEFGHIJKLABCDEFKLGHIJABCDEFGHIJKL

森林和二叉樹的對應(yīng)關(guān)系設(shè)森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹

B=(LBT,Node(root),RBT);。。。T1T2T3T4TnT1T11T12T1m。。。T1T11T12T1m。。。T2T3Tn。。。森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點用線相連以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJ由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ；否則，由ROOT(T1)

對應(yīng)得到Node(root)；由(t11,t12,…,t1m)

對應(yīng)得到LBT；由(T2,T3,…,Tn)

對應(yīng)得到RBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

對應(yīng)得到ROOT(T1

)；由LBT

對應(yīng)得到(t11,t12,…，t1m)；由RBT

對應(yīng)得到(T2,T3,…,Tn)。

由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。

應(yīng)當(dāng)注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟。6.4.3樹和森林的遍歷一、樹的遍歷二、森林的遍歷三、樹的遍歷的應(yīng)用樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。

若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。ABCDEFG

HIJK

先根遍歷時頂點的訪問次序：ABEFCDGHIJK

后根遍歷時頂點的訪問次序：EFBCIJKHGDA

層次遍歷時頂點的訪問次序：ABCDEFGHIJK

BCDEFGHIJK1．森林中第一棵樹的根結(jié)點；2．森林中第一棵樹的子樹森林；3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：1.先序遍歷森林的遍歷

若森林不空，則訪問森林中第一棵樹的根結(jié)點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行先根遍歷。２．中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點；中序遍歷森林中(除第一棵樹之外)其

余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。

樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷小結(jié)樹和森林的遍歷樹的遍歷遍歷——按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列常用方法先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，……第n層的結(jié)點ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：A

BEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

樹的先序遍歷二法相同；2.

樹的后序遍歷相當(dāng)于對應(yīng)二叉樹的中序遍歷；3.

樹沒有中序遍歷，因為子樹無左右之分。結(jié)論：討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？森林：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。結(jié)論：當(dāng)以二叉鏈表做樹的存儲結(jié)構(gòu)時，樹的先根序列和后根序列可借用二叉樹的先序遍歷和后序遍歷的算法實現(xiàn)之；對于森林也一樣。6.6

赫夫曼樹及其應(yīng)用

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

赫夫曼編碼

一、最優(yōu)樹的定義樹的路徑長度定義為：

樹中每個結(jié)點的路徑長度之和。

結(jié)點的路徑長度定義為：

從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。路徑：從一個結(jié)點到另一個結(jié)點之間的若干個分支；路徑長度：路徑上的分支數(shù)目稱為路徑長度；結(jié)點的權(quán)：根據(jù)應(yīng)用的需要可以給樹的結(jié)點賦某種意義的實數(shù)稱權(quán)值；樹的帶權(quán)路徑長度=樹中所有葉子結(jié)點的帶權(quán)路徑之和；通常記作

nWPL=

wk

Lk

k=1赫夫曼樹：假設(shè)有n個權(quán)值(w1,

w2,…,wn)，構(gòu)造有n個葉子結(jié)點的嚴格二叉樹，每個葉子結(jié)點有一個wi

作為它的權(quán)值。則帶權(quán)路徑長度最小的嚴格二叉樹稱為最優(yōu)二叉樹（赫夫曼樹）。22475499WPL(T)=72+52+23+43+92=60WPL(T)=72+91+53+24+44=625724579WPL(T)=92+72+52+23+43=60如何構(gòu)造赫夫曼樹？

根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點，其左、右子樹為空樹；二、構(gòu)造最優(yōu)樹（赫夫曼樹）(1)(赫夫曼算法)

在F中選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；(2)

從F中刪去這兩棵樹，同時加入剛生成的新樹；

重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。(3)(4)演示9例如:已知權(quán)值W={5,6,2,9,7}5627257697671392576713925716671329WPL=6*2+7*2+9*2+5*3+2*3=12+14+18+15+6=659257163、哈夫曼樹構(gòu)造程序一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點采用順序存儲結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組存儲結(jié)點信息結(jié)點類型定義為：typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;

voidHuffman(HuffmanTree&HT,int*w,intn){inti,j,k,m,s1,s2;HuffmanTreep;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};for(;i<=m;++i,++p)*p={0,0,0,0};//初始化HT數(shù)組for(i=n+1;i<=m;++i)//建赫夫曼樹

{Select(HT,i-1,s1,s2);//在HT[1..i-1]選擇parent為-1且weight最小的兩個結(jié)點,其序號分別為s1,s2HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;}

}//Huffman構(gòu)造赫夫曼樹81321312567例：{2，5，1，7，6}26005700160078006800373189621395421078123456789WeightparentlchildrchildHuffman樹應(yīng)用

_最佳判定樹等級分數(shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70

a<80a<60CYNBYNDYNEYNA80

a<9060

a<70EADBCa<80a<70a<60a<90EYNDYNCYNBYNA172對應(yīng)的哈夫曼編碼：Huffman碼的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)

=1.44+0.92+0.25=2.61

3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

二進制等長碼的WPL＝10717116235282119403260100bcadegfha0010b10c00000d0001e01f00001g11h0011在進行數(shù)據(jù)通訊時，涉及數(shù)據(jù)編碼問題。所謂數(shù)據(jù)編碼就是數(shù)據(jù)與二進制字符串的轉(zhuǎn)換。例如：郵局發(fā)電報：

例要傳輸?shù)脑臑锳BACCDA

等長編碼

A：00

B：01

C：10

D：11發(fā)送方：ABACCDA

轉(zhuǎn)換成00010010101100接收方：00010010101100

還原為

ABACCDA三、赫夫曼編碼不等長編碼A：0B：00C：1D：01發(fā)送方：將ABACCDA

轉(zhuǎn)換成

000011010接收方：000011010

轉(zhuǎn)換成AAAACCDABBCCDAA的編碼是B的前綴原文電文（二進制字符串）原文發(fā)送方接收方

指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。如ABCD四個字符的使用率由高到低，編碼為A---0B---10C---110D---111因此，若設(shè)計長短不等的編碼，則必須是任何一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱做前綴編碼。

如何編制前綴碼呢？？例如：（ABCD）字符使用頻度作為權(quán)值：（3，1，2，1）構(gòu)造哈夫曼樹。將該哈夫曼樹所有左分支標(biāo)記0，所有右分支標(biāo)記1；

利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。A：0B：110C：10D：1113721

124000111ABCDHuffman編碼：數(shù)據(jù)通信用的二進制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列例