樹(shù)的類(lèi)型定義課件

Tree&BinaryTree

Tree&BinaryTree

1樹(shù)的類(lèi)型定義n(n≥0)個(gè)元素的有限集合樹(shù)的類(lèi)型定義n(n≥0)個(gè)元素的有限集合2基本術(shù)語(yǔ)基本術(shù)語(yǔ)3結(jié)點(diǎn)結(jié)點(diǎn)的度樹(shù)的度葉子結(jié)點(diǎn)分支結(jié)點(diǎn)數(shù)據(jù)元素+若干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM結(jié)點(diǎn)結(jié)點(diǎn)的度樹(shù)的度葉子結(jié)點(diǎn)分支結(jié)點(diǎn)數(shù)據(jù)元素+若干指向子樹(shù)的分4(從根到結(jié)點(diǎn)的)路徑孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL(從根到結(jié)點(diǎn)的)路徑孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)由從根到該結(jié)點(diǎn)5結(jié)點(diǎn)的層次樹(shù)的深度ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)中葉子結(jié)點(diǎn)所在的最大層次結(jié)點(diǎn)的層次樹(shù)的深度ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次6任何一棵非空樹(shù)是一個(gè)二元組Tree=（root，F(xiàn)）其中root被稱為根結(jié)點(diǎn)F被稱為子樹(shù)森林森林是m（m≥0）棵互不相交的樹(shù)的集合ArootBCDEFGHIJMKLF任何一棵非空樹(shù)是一個(gè)二元組森林是m（m≥0）棵互ArootB7(１)有確定的根(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系有向樹(shù)有序樹(shù)子樹(shù)之間存在確定的次序關(guān)系無(wú)序樹(shù)子樹(shù)之間不存在確定的次序關(guān)系(１)有確定的根有向樹(shù)有序樹(shù)子樹(shù)之間存在確定的次序關(guān)系無(wú)序8結(jié)點(diǎn)(node)結(jié)點(diǎn)的度(degree)分支(branch)結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)子女(child)結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)兄弟(sibling)結(jié)點(diǎn)祖先(ancestor)結(jié)點(diǎn)子孫(descendant)結(jié)點(diǎn)結(jié)點(diǎn)所處層次(level)樹(shù)的高度(depth)樹(shù)的度(degree)結(jié)點(diǎn)(node)兄弟(sibling)結(jié)點(diǎn)9對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)10~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))

根結(jié)點(diǎn)(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~11樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)的抽象數(shù)據(jù)類(lèi)型定義12數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合131.若D為空集，則稱為空樹(shù)2.在D中存在唯一的稱為根的數(shù)據(jù)元素root3.當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)

數(shù)據(jù)關(guān)系R1.若D為空集，則稱為空樹(shù)數(shù)據(jù)關(guān)系R14基本操作查找類(lèi)插入類(lèi)刪除類(lèi)基本操作查找類(lèi)插入類(lèi)刪除類(lèi)15Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類(lèi)Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類(lèi)Value(16RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷RightSibling(T,cur_e)TreeEm17InitTree(&T)//初始化置空樹(shù)插入類(lèi)CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)InitTree(&T)//初始化置空樹(shù)插入類(lèi)Cr18ClearTree(&T)//將樹(shù)清空刪除類(lèi)DestroyTree(&T)//銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)ClearTree(&T)//將樹(shù)清空刪除類(lèi)Des19ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根ABCDEFGHIJMKLA(B(E,F(K,L)),20二叉樹(shù)的類(lèi)型定義二叉樹(shù)的類(lèi)型定義21二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交叉的二叉樹(shù)組成ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子22二叉樹(shù)的五種基本形態(tài)N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)二叉樹(shù)的五種基本形態(tài)N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)23二叉樹(shù)的主要基本操作查找類(lèi)插入類(lèi)刪除類(lèi)二叉樹(shù)的主要基本操作查找類(lèi)插入類(lèi)刪除24Root(T)Value(T,e)Parent(T,e)LeftChild(T,e)RightChild(T,e)LeftSibling(T,e)RightSibling(T,e)BiTreeEmpty(T)BiTreeDepth(T)Root(T)Value(T,e)P25PreOrderTraverse(T,Visit())InOrderTraverse(T,Visit())PostOrderTraverse(T,Visit())LevelOrderTraverse(T,Visit())PreOrderTraverse(T,Visit())26

InitBiTree(&T)Assign(T,&e,value)CreateBiTree(&T,definition)InsertChild(T,p,LR,c)InitBiTree(&T)27ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T,p,LR)ClearBiTree(&T)28完全二叉樹(shù)豐滿二叉樹(shù)排序二叉樹(shù)平衡二叉樹(shù)二叉樹(shù)的分類(lèi)完全二叉樹(shù)二叉樹(shù)的分類(lèi)29滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)123456789101112131415abcdefghij滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)完全二叉30二叉樹(shù)

的重要特性二叉樹(shù)

的重要特性31性質(zhì)1

在二叉樹(shù)的第i(i≥1)層上至多有2i-1個(gè)結(jié)點(diǎn)性質(zhì)132用歸納法證明歸納基礎(chǔ)歸納假設(shè)歸納證明i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

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

i，命題成立二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第i層的結(jié)點(diǎn)數(shù)

≤

2i-22=2i-1用歸納法證明i=1層時(shí)，只有一個(gè)根結(jié)點(diǎn)：假設(shè)對(duì)所有的33性質(zhì)2

深度為k（k≥1）的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)性質(zhì)234證明

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

20+21++2k-1=2k-1證明基于上一條性質(zhì)，深度為k的二35性質(zhì)3

對(duì)任何一棵二叉樹(shù)，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1性質(zhì)336證明設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹(shù)上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1證明設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)n=n0+n1+n237性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1性質(zhì)438證明設(shè)完全二叉樹(shù)的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k即k-1≤log2n<k因?yàn)閗只能是整數(shù)，因此，k=log2n+1證明設(shè)完全二叉樹(shù)的深度為k39性質(zhì)5若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：性質(zhì)5若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從40(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)

(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，41樹(shù)的存儲(chǔ)結(jié)構(gòu)一、廣義表表示法二、雙親表示法三、孩子表示法四、孩子兄弟表示法

樹(shù)的存儲(chǔ)結(jié)構(gòu)一、廣義表表示法42廣義表表示法樹(shù)的廣義表表示(結(jié)點(diǎn)的utype域沒(méi)有畫(huà)出)廣義表表示法樹(shù)的廣義表表示43ABCDEFG0A-11B02C03D04E25F26G5dataparent雙親表示法ABCDEFG0A-1datapare44ABCDEFG0A-11B02C03D04E25F26G4datafirstchild123456孩子鏈表表示法ABCDEFG0A-1datafirstch45ABCDEFGABCEDFGrootABCEDFG孩子兄弟表示法ABCDEFGAroot46孩子兄弟表示法

datafirstChildnextSibling孩子兄弟表示法datafirstChildnextSi47二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈一、二叉樹(shù)的順48完全二叉樹(shù)的一般二叉樹(shù)的數(shù)組表示數(shù)組表示順序存儲(chǔ)表示完全二叉樹(shù)的一般二叉樹(shù)的49ABCDEF

ABDCEF

0123456789101112131401326ABCDEFABDC50

單支樹(shù)由于一般二叉樹(shù)必須仿照完全二叉樹(shù)那樣存儲(chǔ)，可能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹(shù)就是一個(gè)極端情況單支樹(shù)由于一般二叉樹(shù)必須仿照完全二叉樹(shù)那樣存儲(chǔ)，可能會(huì)浪費(fèi)51ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表ADEBCFrootlchilddata52鏈表表示鏈表表示53樹(shù)的類(lèi)型定義課件54ADEBCFroot三叉鏈表parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)ADEBCFroot三叉鏈表parent55二叉鏈表的靜態(tài)結(jié)構(gòu)二叉鏈表的靜態(tài)結(jié)構(gòu)56森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)的類(lèi)型定義課件57森林轉(zhuǎn)化成二叉樹(shù)的規(guī)則樹(shù)的類(lèi)型定義課件58若F為空，即n=0，則對(duì)應(yīng)的二叉樹(shù)B為空二叉樹(shù)若F不空，則對(duì)應(yīng)二叉樹(shù)B的根root(B)是F中第一棵樹(shù)T1的根root(T1)，其左子樹(shù)為

B(T11,T12,…,T1m)，其中，T11,T12,…,

T1m是root(T1)的子樹(shù)；其右子樹(shù)為B(T2,T3,…,Tn)，其中，T2,T3,…,Tn是除T1外其它樹(shù)構(gòu)成的森林若F為空，即n=0，則59二叉樹(shù)轉(zhuǎn)換為森林的規(guī)則樹(shù)的類(lèi)型定義課件60如果B為空，則對(duì)應(yīng)的森林F也為空如果B非空，則

F中第一棵樹(shù)T1的根為root；T1的根的子樹(shù)森林(T11,T12,…,T1m)

是由

root的左子樹(shù)LB轉(zhuǎn)換而來(lái)，F(xiàn)

除了T1

之外其余的樹(shù)組成的森林(T2,T3,…,

Tn)是由root的右子樹(shù)RB轉(zhuǎn)換而成的森林如果B為空，則對(duì)應(yīng)的森林F也為空61森林與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換62二叉樹(shù)遍歷(BinaryTreeTraversal)樹(shù)的類(lèi)型定義課件63

順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次問(wèn)題的提出“訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等順著某一條搜索路徑巡訪二叉樹(shù)問(wèn)題的提出“訪問(wèn)64

“遍歷”是任何類(lèi)型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問(wèn)題“遍歷”是任何類(lèi)型均有的操作，65對(duì)“二叉樹(shù)”而言，可以有三條搜索路徑1．先上后下的按層次遍歷2．先左（子樹(shù)）后右（子樹(shù)）的遍歷3．先右（子樹(shù)）后左（子樹(shù)）的遍歷對(duì)“二叉樹(shù)”而言，可以有三條搜索路徑1．先上66設(shè)訪問(wèn)根結(jié)點(diǎn)記作V遍歷根的左子樹(shù)記作L遍歷根的右子樹(shù)記作R則可能的遍歷次序有前序VLR逆前序VRL中序LVR逆中序RVL后序LRV逆后序RLV層次遍歷設(shè)訪問(wèn)根結(jié)點(diǎn)記作67前序遍歷(PreorderTraversal)若二叉樹(shù)為空，則空操作否則訪問(wèn)根結(jié)點(diǎn)(V)前序遍歷左子樹(shù)(L)前序遍歷右子樹(shù)(R)遍歷結(jié)果-+

a

*

b-

cd

/ef前序遍歷(PreorderTraversal)若二叉樹(shù)為68若二叉樹(shù)為空，則空操作否則中序遍歷左子樹(shù)(L)訪問(wèn)根結(jié)點(diǎn)(V)中序遍歷右子樹(shù)(R)遍歷結(jié)果

a

+

b

*

c

-

d

-

e/

f中序遍歷(InorderTraversal)表達(dá)式語(yǔ)法樹(shù)若二叉樹(shù)為空，則空操作中序遍歷(InorderTrave69后序遍歷(PostorderTraversal)若二叉樹(shù)為空，則空操作否則后序遍歷左子樹(shù)(L)后序遍歷右子樹(shù)(R)訪問(wèn)根結(jié)點(diǎn)(V)遍歷結(jié)果abcd

-*+

ef

/

-后序遍歷(PostorderTraversal)若二叉樹(shù)70層次遍歷(LevelorderTraversal)從上到下，從左到右遍歷結(jié)果-＋／a*

efb-cd層次遍歷(LevelorderTraversal)71按給定的表達(dá)式建相應(yīng)二叉樹(shù)由前綴表達(dá)式建樹(shù)例如:-×+abc/de由中綴表達(dá)式建樹(shù)例如：(a+b)×c–d/e由后綴表達(dá)式建樹(shù)例如：ab+c×de/-按給定的表達(dá)式建相應(yīng)二叉樹(shù)由前綴表達(dá)式建樹(shù)由中綴表達(dá)式建樹(shù)72對(duì)應(yīng)前綴表達(dá)式-×+abc/de的二叉樹(shù)abcde-×+/特點(diǎn)：

操作數(shù)為葉子結(jié)點(diǎn)運(yùn)算符為分支結(jié)點(diǎn)對(duì)應(yīng)前綴表達(dá)式-×+abc/deabcde-×73對(duì)應(yīng)中綴表達(dá)式(a+b)×c-d/e的二叉樹(shù)abcde-×+/特點(diǎn)：

操作數(shù)為葉子結(jié)點(diǎn)運(yùn)算符為分支結(jié)點(diǎn)對(duì)應(yīng)中綴表達(dá)式(a+b)×c-d/eabcde74對(duì)應(yīng)后綴表達(dá)式ab+c×de/-的二叉樹(shù)abcde-×+/特點(diǎn)：

操作數(shù)為葉子結(jié)點(diǎn)運(yùn)算符為分支結(jié)點(diǎn)對(duì)應(yīng)后綴表達(dá)式ab+c×de/-abcde-×75a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉樹(shù)的關(guān)系ab+abc×+abc×+(a+b)×cabcde-×+/a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉76二叉樹(shù)的計(jì)數(shù)由二叉樹(shù)的前序序列和中序序列可以唯一地確定一棵二叉樹(shù)由二叉樹(shù)的后序序列和中序序列可以唯一地確定一棵二叉樹(shù)由二叉樹(shù)的前序序列和后序序列不可唯一地確定一棵二叉樹(shù)二叉樹(shù)的計(jì)數(shù)由二叉樹(shù)的前序序列和中序序列可以唯一地確定一77僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二叉樹(shù)，由二叉樹(shù)的先序和中序序列建樹(shù)

如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”，則會(huì)如何？

二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二78abcdefgcbdaegfaabbccddeeffggabcdefg^^^^^^^^先序序列中序序列abcdefgcbda79前序序列{ABHFDECKG}中序序列{HBDFAEKCG}前序序列{ABHFDECKG}80

如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹(shù)如果前序序列固定不變，給出不同的中序序列，可得到不同81問(wèn)題是有n個(gè)數(shù)據(jù)值，可能構(gòu)造多少種不同的二叉樹(shù)？我們可以固定前序排列，選擇所有可能的中序排列問(wèn)題是有n個(gè)數(shù)據(jù)值，可能構(gòu)造多少種不同的二叉樹(shù)？82有3個(gè)數(shù)據(jù){1,2,3}，可得5種不同的二叉樹(shù)。它們的前序排列均為123，中序序列可能是

123，132，213，231，321有3個(gè)數(shù)據(jù){1,2,3}，可得5種不同的二叉樹(shù)83有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹(shù)如下有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹(shù)如下84具有4個(gè)結(jié)點(diǎn)的不同二叉樹(shù)計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹(shù)的棵數(shù)Catalan函數(shù)具有4個(gè)結(jié)點(diǎn)的不同二叉樹(shù)計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹(shù)的棵數(shù)C85樹(shù)的遍歷深度優(yōu)先遍歷樹(shù)的先根次序遍歷樹(shù)的后根次序遍歷廣度優(yōu)先遍歷樹(shù)的層次次序遍歷樹(shù)的遍歷86

ABCDEFGHIJK先根遍歷ABEFCDGHIJK后根遍歷EFBCIJKHGDA層次遍歷：ABCDEFGHIJKA先根遍歷ABEF87

BCDEFGHIJK1．森林中第一棵樹(shù)的根結(jié)點(diǎn)2．森林中第一棵樹(shù)的子樹(shù)森林3．森林中其它樹(shù)構(gòu)成的森林森林由三部分構(gòu)成1．森林中第一棵樹(shù)的根結(jié)點(diǎn)2．森林中88森林的先根遍歷森林的二叉樹(shù)表示若森林F為空,返回否則:

訪問(wèn)F的第一棵樹(shù)的根結(jié)點(diǎn)

先根次序遍歷第一棵樹(shù)的子樹(shù)森林

先根次序遍歷其它樹(shù)組成的森林森林的先根遍歷森林的二叉樹(shù)表示若森林F為空,返回89森林的后根遍歷森林的二叉樹(shù)表示若森林F為空，返回否則:

后根次序遍歷第一棵樹(shù)的子樹(shù)森林

后根次序遍歷其它樹(shù)組成的森林

訪問(wèn)F的第一棵樹(shù)的根結(jié)點(diǎn) 森林的后根遍歷森林的二叉樹(shù)表示若森林F為空，返回90森林的層次遍歷森林的二叉樹(shù)表示若森林F為空，返回否則:

依次遍歷各棵樹(shù)的根結(jié)點(diǎn)

依次遍歷各棵樹(shù)根結(jié)點(diǎn)的所有子女

依次遍歷這些子女結(jié)點(diǎn)的子女結(jié)點(diǎn)森林的層次遍歷森林的二叉樹(shù)表示若森林F為空，返回91二叉樹(shù)的類(lèi)定義樹(shù)的類(lèi)型定義課件92template<classType>classBinTreeNode{private:

BinTreeNode<Type>*LChild,*RChild;Typedata;};template<classType>classBinaryTree{ private:BinTreeNode<Type>*root;};template<classType>93二叉樹(shù)前序遍歷遞歸算法template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*current){if(current!=NULL){cout<<current→data;

PreOrder(current→LChild);

PreOrder(current→RChild);}}二叉樹(shù)前序遍歷遞歸算法94二叉樹(shù)中序遍歷遞歸算法template<classType>voidBinaryTree<Type>::

InOrder(BinTreeNode<Type>*current){if(current!=NULL){InOrder(current→LChild);cout<<current→data;

InOrder(current→RChild);}}二叉樹(shù)中序遍歷遞歸算法95二叉樹(shù)后序遍歷遞歸算法template<classType>voidBinaryTree<Type>::

PostOrder(BinTreeNode<Type>*current){if(current!=NULL){

PostOrder(current→LChild);

PostOrder(current→RChild);cout<<current→data;}}二叉樹(shù)后序遍歷遞歸算法96二叉樹(shù)前序遍歷非遞歸算法樹(shù)的類(lèi)型定義課件97template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*p){do{while(p!=NULL){cout<<p→data;

Push

(s,p);p=p→LChild;}if(!Empty(s)){p=pop(s);p=p→RChild;}}while((!Empty(s))||(p!=NULL))

}template<classType>98二叉樹(shù)中序遍歷非遞歸算法樹(shù)的類(lèi)型定義課件99template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*p){do{while(p!=NULL){Push

(s,p);p=p→LChild;}if(!Empty(s)){p=pop(s);cout<<p→data;p=p→RChild;}}while((!Empty(s))||(p!=NULL))

}template<classType>100

應(yīng)用二叉樹(shù)遍歷的事例

應(yīng)用二叉樹(shù)遍歷的事例101計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的一種方法template<classType>intBinaryTree<Type>::Size(BinTreeNode<Type>*t){if(t==NULL)return0;elsereturn1+Size(t→LChild)+Size(t→RChild);}計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的一種方法template<class102計(jì)算二叉樹(shù)的高度template<classType>intBinaryTree<Type>::Depth(BinTreeNode<Type>*t){if(t==NULL)return0;elsereturn1+

Max(Depth(t→LChild),

Depth(t→RChild));}

計(jì)算二叉樹(shù)的高度template<classType>103

線索二叉樹(shù)

線索二叉樹(shù)104遍歷二叉樹(shù)的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列ABCDEFGHK先序序列

ABCDEFGHK中序序列

BDCAHGKFE后序序列

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

C^^B

E^指向該線性序列中的“前驅(qū)”和與其相應(yīng)的二叉樹(shù)，包含“線索”106對(duì)線索鏈表中結(jié)點(diǎn)的約定在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域LTag和RTag,并作如下規(guī)定:若該結(jié)點(diǎn)的左子樹(shù)不空，則LChild域的指針指向其左孩子，且左標(biāo)志LTag的值為0否則，LChild域的指針指向其“前驅(qū)”，且左標(biāo)志LTag的值為1對(duì)線索鏈表中結(jié)點(diǎn)的約定在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域若該結(jié)107若該結(jié)點(diǎn)的右子樹(shù)不空，則RChild域的指針指向其右孩子，且右標(biāo)志RTag的值為0否則，RChild域的指針指向其“后繼”，且右標(biāo)志RTag的值為1如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”若該結(jié)點(diǎn)的右子樹(shù)不空，如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈108LTag=0,LChild為指針,指向左孩子LTag=1,LChild為線索,指向前驅(qū)RTag=0,RChild為指針,指向右孩子RTag=1,RChild為線索,指向后繼LTag=0,LChild為指針,指向左孩子109猜一猜,是哪一種線索二叉樹(shù)猜一猜,是哪一種線索二叉樹(shù)110后序序列

DBECA前序序列

ABDCE后序序列前序序列111帶表頭結(jié)點(diǎn)的中序線索二叉樹(shù)帶表頭結(jié)點(diǎn)的中序線索二叉樹(shù)112

尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼尋找當(dāng)前結(jié)點(diǎn)113if(pRTag==1)if(pRChild!=T.root)

后繼為

pRChildelse無(wú)后繼else//pRTag==0if(pRChild!=T.root)

后繼為當(dāng)前結(jié)點(diǎn)右子樹(shù)的中序下的第一個(gè)結(jié)點(diǎn)else出錯(cuò)情況ABDECFHIKGJLif(pRTag==1)ABDECFHIKGJL114

尋找當(dāng)前結(jié)點(diǎn)在中序下的前趨尋找當(dāng)前結(jié)點(diǎn)115if(pLTag==1)if(pLChild!=T.root)

前驅(qū)為pLChildelse無(wú)前驅(qū)else//pLTag==0if(pLChild!=T.root)

前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹(shù)的中序下的最后一個(gè)結(jié)點(diǎn)else出錯(cuò)情況ABDECFHIKGJLif(pLTag==1)ABDECFHIKGJL116在前序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的后繼在前序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的后繼117在前序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的前趨在前序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的前趨118在后序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的后繼在后序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的后繼119在后序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的前趨在后序線索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的前趨120堆(Heap)template<classType>classMinPQ

{public:

Virtualvoid

Insert(constType&)=0;

VirtualType*RemoveMin(Type&)=0;}

最小優(yōu)先級(jí)隊(duì)列類(lèi)的定義優(yōu)先級(jí)隊(duì)列每次出隊(duì)列的是優(yōu)先權(quán)最高的元素堆(Heap)template<classType121堆的定義完全二叉樹(shù)的數(shù)組表示

Ki

K2i+1&&

Ki

K2i+2完全二叉樹(shù)的數(shù)組表示

Ki

K2i+1&&

Ki

K2i+2堆的定義完全二叉樹(shù)的數(shù)組表示完全二叉樹(shù)的數(shù)組表示122最小堆的類(lèi)定義template<classType>class

MinHeap

:publicMinPQ<Type>{

public:

MinHeap(int

maxSize)

const;

MinHeap(Type

arr[],int

n);~MinHeap(){

delete[]heap;}

const

MinHeap<Type>&

operator=(constMinHeap&R);

intInsert(constType

&x);

intRemoveMin(Type&x);

int

IsEmpty()const

{return

CurrentSize==0;

}

最小堆的類(lèi)定義123intIsFull()const{

return

CurrentSize==

MaxHeapSize;

}

void

MakeEmpty(){

CurrentSize=0;

}private:

enum

{

DefaultSize=10};

Type*heap;

int

CurrentSize;

int

MaxHeapSize;

voidFilterDown(inti,int

m);

void

FilterUp(inti);}

intIsFull()const124堆的建立template<classType>MinHeap<Type>::MinHeap(int

maxSize){//根據(jù)給定大小maxSize,建立堆對(duì)象

MaxHeapSize=DefaultSize<maxSize

?

maxSize

:

DefaultSize;

//確定堆大小

heap=new

Type[MaxHeapSize];//創(chuàng)建堆空間

CurrentSize=0;//初始化}template<classType>MinHeap<Type>::MinHeap(Type

arr[],int

n){//根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對(duì)象

堆的建立template<classType>MinH125MaxHeapSize=DefaultSize<n

?

n

:

DefaultSize;

heap=new

Type[MaxHeapSize];

heap=arr;

//數(shù)組傳送

CurrentSize=n;//當(dāng)前堆大小

intcurrentPos=(CurrentSize-2)/2;//最后非葉

while(currentPos>=0){

//從下到上逐步擴(kuò)大,形成堆

FilterDown(currentPos,CurrentSize);

//從currentPos開(kāi)始,到CurrentSize為止,調(diào)整

currentPos--;

}}MaxHeapSize=DefaultSize126自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆127樹(shù)的類(lèi)型定義課件128樹(shù)的類(lèi)型定義課件129樹(shù)的類(lèi)型定義課件130最小堆的向下調(diào)整算法template<classType>void

MinHeap<Type>::FilterDown(constint

start,constint

EndOfHeap){

int

i=start,

j=2*i+1;//j是i

的左子女Type

temp=heap[i];

while(j<=EndOfHeap){

if(j<EndOfHeap

&&

heap[j].key>

heap[j+1].key)j++; //兩子女中選小者

if(temp.key<=heap[j].key)break;

else{heap[i]=heap[j];i=j;j=2*j+1;}

}

heap[i]=temp; }最小堆的向下調(diào)整算法131堆的插入template<classType>int

MinHeap<Type>::Insert(constType&x){//在堆中插入新元素xif(CurrentSize==MaxHeapSize)//堆滿

{

cout<<"堆已滿"<<endl;

return0;

}

heap[CurrentSize]=x;//插在表尾

FilterUp(CurrentSize);//向上調(diào)整為堆

CurrentSize++;//堆元素增一

return1;}堆的插入template<classType>int132template<classType>void

MinHeap<Type>::FilterUp(intstart){//從start開(kāi)始,向上直到0,調(diào)整堆intj=start,

i=(j-1)/2;//i是j的雙親

Type

temp=heap[j];

while(j>0){

if(heap[i].key<=temp.key)break;

else{

heap[j]=heap[i];j=i;i=(i

-1)/2;}

}

heap[j]=temp;}template<classType>voidMin133最小堆的向上調(diào)整最小堆的向上調(diào)整134template<classType>int

MinHeap<Type>::RemoveMin(Type&x){

if(!CurrentSize){cout<<“堆已空

"<<endl;return0;}

x=heap[0];//最小元素出隊(duì)列

heap[0]=heap[CurrentSize-1];

CurrentSize--;

//用最小元素填補(bǔ)

FilterDown(0,CurrentSize-1);

//從0號(hào)位置開(kāi)始自頂向下調(diào)整為堆

return1;}template<classType>intMinH135

哈夫曼樹(shù)

(HuffmanTree)

與

哈夫曼編碼

哈夫曼樹(shù)

(HuffmanTree)

與

哈136設(shè)給出一段報(bào)文CASTCASTSATATATASA字符集合是{C,A,S,T}，各個(gè)字符出現(xiàn)的頻度(次數(shù))是W＝{2,7,4,5}

若給每個(gè)字符以等長(zhǎng)編碼A:00T:10C:01S:11則總編碼長(zhǎng)度為(2+7+4+5)*2=36設(shè)給出一段報(bào)文137若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度A:0T:10C:110S:111它的總編碼長(zhǎng)度為

7*1+5*2+(2+4)*3=35比等長(zhǎng)編碼的情形要短若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少138結(jié)點(diǎn)的路徑長(zhǎng)度

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目結(jié)點(diǎn)間路徑長(zhǎng)度(PathLength)連接兩結(jié)點(diǎn)的路徑上的分支數(shù)結(jié)點(diǎn)的路徑長(zhǎng)度結(jié)點(diǎn)間路徑長(zhǎng)度(PathLength)139樹(shù)的帶權(quán)路徑長(zhǎng)度(WeightedPathLength,WPL)樹(shù)的各葉結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長(zhǎng)度的乘積的和樹(shù)的路徑長(zhǎng)度樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度140

在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹(shù)中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹(shù)，稱為“最優(yōu)樹(shù)”,或“哈夫曼樹(shù)”

(HuffmanTree)

在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同141具有不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)哈夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近具有不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)哈夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=72143構(gòu)造哈夫曼樹(shù)(以二叉樹(shù)為例)(以二叉樹(shù)為例)144

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,

wn}，造n棵二叉樹(shù)的集合

F={T1,T2,…,Tn}，其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；(1)根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,145

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

從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)

重復(fù)(2)和(3)兩步，直至F中只含一棵樹(shù)為止(3)(4)從F中刪去這兩棵樹(shù)，同時(shí)加入重復(fù)(21479已知權(quán)值W={5,6,2,9,7}5627527697671395279已知權(quán)值W={5,6,2,9,7}562751486713952795271667132900001111000110110111671395279527166713290000111100149哈夫曼樹(shù)的構(gòu)造過(guò)程哈夫曼樹(shù)的構(gòu)造過(guò)程150哈夫曼樹(shù)的構(gòu)造過(guò)程哈夫曼樹(shù)的構(gòu)造過(guò)程151

任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴前綴編碼

利用哈夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短任何一個(gè)字符的編碼都不是同一前綴編碼152設(shè)給出一段報(bào)文CASTCASTSATATATASA字符集合是{C,A,S,T}，各個(gè)字符出現(xiàn)的頻度(次數(shù))是W＝{2,7,4,5}若給每個(gè)字符以等長(zhǎng)編碼A:00T:10C:01S:11則總編碼長(zhǎng)度為(2+7+4+5)*2=36設(shè)給出一段報(bào)文153以各字符出現(xiàn)概率{2,7,4,5}為各葉結(jié)點(diǎn)權(quán)值，建立哈夫曼樹(shù)，得哈夫曼編碼(不等長(zhǎng)編碼)A:0T:10C:110S:111總編碼長(zhǎng)度為7*1+5*2+(2+4)*3=35總編碼長(zhǎng)度正好等于哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL

以各字符出現(xiàn)概率{2,7,4,5}為各葉結(jié)點(diǎn)權(quán)值，建立哈夫曼154哈夫曼樹(shù)的應(yīng)用（1）判定樹(shù)在解決某些判定問(wèn)題時(shí)，利用哈夫曼樹(shù)可以得到最佳判定算法。例1將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績(jī)分布是均勻的，可用圖（a)二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。a<60

a<70

a<80

a<90

不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行31500次比較。哈夫曼樹(shù)的應(yīng)用（1）判定樹(shù)a<60a<70a<80155分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.1010000個(gè)學(xué)生成績(jī)轉(zhuǎn)換成五分制的判定A<60A<70A<80A<90不及格優(yōu)秀及格中等良好YNYYYNNN500*1+1500*2+4000*3+3000*4+1000*4=31500分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)156分?jǐn)?shù)0—5960—6970—7980—8990—99比例0.050.150.40.30.1070≤a<80

a<60

及格中等良好80≤a<90

60≤a<70

不及格優(yōu)秀YNYYYNNN(b)不及格Ya<90

a<80

a<70

a<60

優(yōu)秀中等及格良好YNNN(c)YYY學(xué)生成績(jī)分布不是均勻的情況：以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹(shù)，如（b)判斷樹(shù)所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹(shù)。輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。分?jǐn)?shù)0—5960—6970—7980—8990—99比例0.157A<60A<70A<80A<90不及格優(yōu)秀及格中等良好YNYYYNNN用此形式比較次數(shù)為：500*3+1500*3+4000*2+3000*2+1000*2=22000A<60A<70A<80A<90不及格優(yōu)秀及格中等良好YNY158146833442200001111T;ACS各字符編碼是T；ACS

000110110111上述電文編碼：11010111011101000011111000011000方法：（1）用{2，4，2，3，3}作為葉子結(jié)點(diǎn)的權(quán)值生成一棵哈夫曼樹(shù)，并將對(duì)應(yīng)權(quán)值wi的葉子結(jié)點(diǎn)注明對(duì)應(yīng)的字符；（2）約定左分支表示字符“0”，右分支表示字符‘1’（3）從葉子結(jié)點(diǎn)開(kāi)始，順著雙親反推上去，直到根結(jié)點(diǎn)，路徑上的‘0’或‘1’連接的序列就是結(jié)點(diǎn)對(duì)應(yīng)的字符的二進(jìn)制編碼的逆序。（2）哈夫曼編碼-----利用哈夫曼樹(shù)構(gòu)造通訊中電文編碼（前綴碼）例2：要傳輸?shù)碾娢氖莧CAS；CAT；SAT；AT}要傳輸?shù)淖址荄={C，A，S，T，；}每個(gè)字符出現(xiàn)的頻率是W={2，4，2，3，3}注意：編碼的總長(zhǎng)度恰好為哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)。146833442200001111T;ACS各字符編碼是1591.熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2.熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3.遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。1.熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。1604.理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹(shù)的線索化過(guò)程是基于對(duì)二叉樹(shù)進(jìn)行遍歷，而線索二叉樹(shù)上的線索又為相應(yīng)的遍歷提供了方便。4.理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的1615.熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。6.學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。7.了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。5.熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的162

Tree&BinaryTree

Tree&BinaryTree

163樹(shù)的類(lèi)型定義n(n≥0)個(gè)元素的有限集合樹(shù)的類(lèi)型定義n(n≥0)個(gè)元素的有限集合164基本術(shù)語(yǔ)基本術(shù)語(yǔ)165結(jié)點(diǎn)結(jié)點(diǎn)的度樹(shù)的度葉子結(jié)點(diǎn)分支結(jié)點(diǎn)數(shù)據(jù)元素+若干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM結(jié)點(diǎn)結(jié)點(diǎn)的度樹(shù)的度葉子結(jié)點(diǎn)分支結(jié)點(diǎn)數(shù)據(jù)元素+若干指向子樹(shù)的分166(從根到結(jié)點(diǎn)的)路徑孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL(從根到結(jié)點(diǎn)的)路徑孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)由從根到該結(jié)點(diǎn)167結(jié)點(diǎn)的層次樹(shù)的深度ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)中葉子結(jié)點(diǎn)所在的最大層次結(jié)點(diǎn)的層次樹(shù)的深度ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次168任何一棵非空樹(shù)是一個(gè)二元組Tree=（root，F(xiàn)）其中root被稱為根結(jié)點(diǎn)F被稱為子樹(shù)森林森林是m（m≥0）棵互不相交的樹(shù)的集合ArootBCDEFGHIJMKLF任何一棵非空樹(shù)是一個(gè)二元組森林是m（m≥0）棵互ArootB169(１)有確定的根(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系有向樹(shù)有序樹(shù)子樹(shù)之間存在確定的次序關(guān)系無(wú)序樹(shù)子樹(shù)之間不存在確定的次序關(guān)系(１)有確定的根有向樹(shù)有序樹(shù)子樹(shù)之間存在確定的次序關(guān)系無(wú)序170結(jié)點(diǎn)(node)結(jié)點(diǎn)的度(degree)分支(branch)結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)子女(child)結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)兄弟(sibling)結(jié)點(diǎn)祖先(ancestor)結(jié)點(diǎn)子孫(descendant)結(jié)點(diǎn)結(jié)點(diǎn)所處層次(level)樹(shù)的高度(depth)樹(shù)的度(degree)結(jié)點(diǎn)(node)兄弟(sibling)結(jié)點(diǎn)171對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)172~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))

根結(jié)點(diǎn)(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~173樹(shù)的抽象數(shù)據(jù)類(lèi)型定義樹(shù)的抽象數(shù)據(jù)類(lèi)型定義174數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合1751.若D為空集，則稱為空樹(shù)2.在D中存在唯一的稱為根的數(shù)據(jù)元素root3.當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)

數(shù)據(jù)關(guān)系R1.若D為空集，則稱為空樹(shù)數(shù)據(jù)關(guān)系R176基本操作查找類(lèi)插入類(lèi)刪除類(lèi)基本操作查找類(lèi)插入類(lèi)刪除類(lèi)177Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類(lèi)Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類(lèi)Value(178RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷RightSibling(T,cur_e)TreeEm179InitTree(&T)//初始化置空樹(shù)插入類(lèi)CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)InitTree(&T)//初始化置空樹(shù)插入類(lèi)Cr180ClearTree(&T)//將樹(shù)清空刪除類(lèi)DestroyTree(&T)//銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)ClearTree(&T)//將樹(shù)清空刪除類(lèi)Des181ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根ABCDEFGHIJMKLA(B(E,F(K,L)),182二叉樹(shù)的類(lèi)型定義二叉樹(shù)的類(lèi)型定義183二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交叉的二叉樹(shù)組成ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子184二叉樹(shù)的五種基本形態(tài)N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)二叉樹(shù)的五種基本形態(tài)N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)185二叉樹(shù)的主要基本操作查找類(lèi)插入類(lèi)刪除類(lèi)二叉樹(shù)的主要基本操作查找類(lèi)插入類(lèi)刪除186Root(T)Value(T,e)Parent(T,e)LeftChild(T,e)RightChild(T,e)LeftSibling(T,e)RightSibling(T,e)BiTreeEmpty(T)BiTreeDepth(T)Root(T)Value(T,e)P187PreOrderTraverse(T,Visit())InOrderTraverse(T,Visit())PostOrderTraverse(T,Visit())LevelOrderTraverse(T,Visit())PreOrderTraverse(T,Visit())188

InitBiTree(&T)Assign(T,&e,value)CreateBiTree(&T,definition)InsertChild(T,p,LR,c)InitBiTree(&T)189ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T,p,LR)ClearBiTree(&T)190完全二叉樹(shù)豐滿二叉樹(shù)排序二叉樹(shù)平衡二叉樹(shù)二叉樹(shù)的分類(lèi)完全二叉樹(shù)二叉樹(shù)的分類(lèi)191滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)123456789101112131415abcdefghij滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)完全二叉192二叉樹(shù)

的重要特性二叉樹(shù)

的重要特性193性質(zhì)1

在二叉樹(shù)的第i(i≥1)層上至多有2i-1個(gè)結(jié)點(diǎn)性質(zhì)1194用歸納法證明歸納基礎(chǔ)歸納假設(shè)歸納證明i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

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

i，命題成立二叉樹(shù)上每個(gè)結(jié)