數(shù)據(jù)結(jié)構(gòu)-基于Python語(yǔ)言（微課版） 課件T14-樹(shù)(樹(shù))

樹(shù)第八章：樹(shù)

主講：周翔回顧請(qǐng)簡(jiǎn)述一下稀疏矩陣的十字鏈表存儲(chǔ)結(jié)構(gòu)。請(qǐng)簡(jiǎn)述一下廣義表的遞歸運(yùn)算思想。預(yù)習(xí)檢查什么是二叉樹(shù)二叉樹(shù)有哪些性質(zhì)本章目標(biāo)3樹(shù)的概念和基本術(shù)語(yǔ)線(xiàn)索二叉樹(shù)和哈夫曼樹(shù)重點(diǎn)了解掌握2二叉樹(shù)的創(chuàng)建二叉樹(shù)及其性質(zhì)二叉樹(shù)的存儲(chǔ)及遍歷1什么是樹(shù)什么是樹(shù)樹(shù)定義：是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合T。n=0時(shí)（沒(méi)有結(jié)點(diǎn)），稱(chēng)為空樹(shù)。n>0時(shí)，必有一根。根（root）結(jié)點(diǎn)，它沒(méi)有前驅(qū)結(jié)點(diǎn)。其余n-1個(gè)結(jié)點(diǎn)可以劃分成m個(gè)根的子樹(shù)什么是樹(shù)ABDEFGHIJKMLC根樹(shù)中每一個(gè)元素稱(chēng)為一個(gè)結(jié)點(diǎn)根結(jié)點(diǎn)A有三棵子樹(shù)以B為根結(jié)點(diǎn)的子樹(shù)以C為根結(jié)點(diǎn)的子樹(shù)以D為根結(jié)點(diǎn)的子樹(shù)然后子樹(shù)又有子樹(shù)構(gòu)成，因此樹(shù)的定義具有遞歸性什么是樹(shù)樹(shù)的遞歸定義樹(shù)的固有特性：一棵樹(shù)是由若干棵子樹(shù)構(gòu)成的每棵子樹(shù)的除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。樹(shù)的圖解表示法樹(shù)形表示法文氏圖表示法（嵌套集合形式）廣義表形式（嵌套括號(hào)表示法）凹入表示法樹(shù)的圖解表示法樹(shù)形表示法樹(shù)形表示法是樹(shù)結(jié)構(gòu)最常用的表示方法，在樹(shù)形圖表示中，結(jié)點(diǎn)用圓圈表示，元素名稱(chēng)寫(xiě)在圓圈中，各結(jié)點(diǎn)之間的關(guān)系用連接線(xiàn)來(lái)表示。中國(guó)河北安徽邯鄲邢臺(tái)青島六安蚌埠山東濟(jì)南合肥樹(shù)的圖解表示法文氏圖表示法（嵌套集合形式）ABEKLFCGDHMIJ樹(shù)的圖解表示法廣義表形式（嵌套括號(hào)表示法）用廣義表來(lái)表示樹(shù)形結(jié)構(gòu)時(shí)，根結(jié)點(diǎn)寫(xiě)在最外層，即表的最左邊，第一層是其直接孩子結(jié)點(diǎn)，第二層是其孫子結(jié)點(diǎn)，這樣逐層深入。（中國(guó)（河北（邯鄲，邢臺(tái)），山東（濟(jì)南，青島），安徽（合肥，六安，蚌埠）））中國(guó)河北安徽邯鄲邢臺(tái)青島六安蚌埠山東濟(jì)南合肥樹(shù)的圖解表示法凹入表示法樹(shù)的基本概念及常用術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其他結(jié)點(diǎn)的分支信息結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)。樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。樹(shù)的基本概念及常用術(shù)語(yǔ)ABDEFGHIJKMLC在樹(shù)中，一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目稱(chēng)為結(jié)點(diǎn)的度A結(jié)點(diǎn)有B,C,D三棵子樹(shù)，它的度為3B結(jié)點(diǎn)有E,F,G三棵子樹(shù)，它的度為3C結(jié)點(diǎn)有H一棵子樹(shù)，它的度為1D結(jié)點(diǎn)有I,J兩棵子樹(shù)，它的度為2樹(shù)中各結(jié)點(diǎn)度的最大值稱(chēng)為樹(shù)的度，通常將度為m的樹(shù)稱(chēng)為m次樹(shù)。本樹(shù)就是一棵3次樹(shù)樹(shù)的基本概念及常用術(shù)語(yǔ)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)。 如下圖中的K，L，F(xiàn)，G，M，I，J。分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)。樹(shù)的基本概念及常用術(shù)語(yǔ)在一棵樹(shù)中，度不為0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)，度為0的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)或葉子結(jié)點(diǎn)，也就是沒(méi)有后繼結(jié)點(diǎn)的結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。ABDEFGHIJKMLCB,C,D,F,J是分支結(jié)點(diǎn)E,G,H,I,K,L,M是葉子結(jié)點(diǎn)樹(shù)的基本概念及常用術(shù)語(yǔ)結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類(lèi)推。結(jié)點(diǎn)的層序編號(hào)：將樹(shù)中的結(jié)點(diǎn)按從上到下，同層按從左到右的次序排成一個(gè)線(xiàn)性序列，依次給它們編以連續(xù)的自然數(shù)。ABCDEFGHIKLMN1層2層4層3層14329871065111213樹(shù)的基本概念及常用術(shù)語(yǔ)森林：m(m≥0)棵互不相交的樹(shù)的集合。將一棵非空的樹(shù)根結(jié)點(diǎn)刪去，樹(shù)就變成一個(gè)森林。ABDEFGHIJKMLC多棵樹(shù)組成了森林樹(shù)的基本概念及常用術(shù)語(yǔ)常借助人類(lèi)家族樹(shù)的術(shù)語(yǔ)，以便直觀理解結(jié)點(diǎn)間的層次關(guān)系老王王一王二王小一王小二王小三王小四王小小一王小小二樹(shù)的基本概念及常用術(shù)語(yǔ)孩子結(jié)點(diǎn)：雙親結(jié)點(diǎn)：兄弟結(jié)點(diǎn)：堂兄弟結(jié)點(diǎn)：祖先結(jié)點(diǎn)：子孫結(jié)點(diǎn)：前輩結(jié)點(diǎn)：后輩結(jié)點(diǎn)：----前三個(gè)最常用結(jié)點(diǎn)E、F是結(jié)點(diǎn)B的孩子結(jié)點(diǎn)結(jié)點(diǎn)B是結(jié)點(diǎn)E、F的雙親結(jié)點(diǎn)結(jié)點(diǎn)B、C、D互為兄弟結(jié)點(diǎn)結(jié)點(diǎn)E、G、H互為堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)K的祖先結(jié)點(diǎn)有：ABE結(jié)點(diǎn)D的子孫結(jié)點(diǎn)有：HIJM結(jié)點(diǎn)G的前輩結(jié)點(diǎn)有：ABCD(層號(hào)小)結(jié)點(diǎn)G的后輩結(jié)點(diǎn)有：KLM(層號(hào)大)樹(shù)的基本概念及常用術(shù)語(yǔ)ABDEFGHIJKMLCB,C,D為A的孩子結(jié)點(diǎn)A結(jié)點(diǎn)為B,C,D的父結(jié)點(diǎn)B,C,D互為的兄弟結(jié)點(diǎn)進(jìn)一步推廣，隔了代的兄弟結(jié)點(diǎn)稱(chēng)為堂兄弟結(jié)點(diǎn)，而在垂直關(guān)系上，它們又稱(chēng)為子孫結(jié)點(diǎn)樹(shù)的基本概念及常用術(shù)語(yǔ)有序樹(shù)：如果在樹(shù)的每一組兄弟結(jié)點(diǎn)之間定義一個(gè)從左到右的次序，則得到一棵有序樹(shù)；否則稱(chēng)為無(wú)序樹(shù)。設(shè)結(jié)點(diǎn)n的所有兒子按其從左到右的次序排列為n1，n2，…，nk，則稱(chēng)n1是n的最左兒子，或簡(jiǎn)稱(chēng)左兒子，并稱(chēng)ni是ni-1的右鄰兄弟，或簡(jiǎn)稱(chēng)右兄弟（i=2，3，...，k)。

圖中的兩棵樹(shù)作為無(wú)序樹(shù)是相同的，但作為有序樹(shù)是不同的，因?yàn)榻Y(jié)點(diǎn)A的兩個(gè)兒子在兩棵樹(shù)中左右次序是不同的。

樹(shù)的基本概念及常用術(shù)語(yǔ)兄弟結(jié)點(diǎn)之間的左右次序關(guān)系的延拓：如果A與B是兄弟，并且A在B的左邊，則規(guī)定A的任一子孫都在B的任一子孫的左邊。A的子孫B的子孫樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法孩子表示法孩子兄弟表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)——雙親表示法雙親表示法先按層序編號(hào)按結(jié)點(diǎn)的層序編號(hào)，在數(shù)組中對(duì)應(yīng)單元存放一個(gè)結(jié)點(diǎn)(data,parent)結(jié)點(diǎn)data部分存放樹(shù)結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)元素結(jié)點(diǎn)parent部分存放該結(jié)點(diǎn)雙親結(jié)點(diǎn)的編號(hào)DataParentA-1B0C0D1E1F1G20123456樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子表示法孩子表示法ABCDEFGHIJ

0

12345678912∧

34∧56∧789∧ABCDEFGHJIABCDEFGHIJ

0

12345678912∧

34∧56∧789∧孩子結(jié)點(diǎn)ChildNodeChildnext順序表結(jié)點(diǎn)DataNodeDataFirstChildNodes[MAX]樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法也叫左孩子-右兄弟表示法樹(shù)的左孩子右兄弟表示法，類(lèi)似于中國(guó)的長(zhǎng)兄如父的思想，它指的是由左邊的孩子結(jié)點(diǎn)來(lái)接管右邊的孩子結(jié)點(diǎn)，類(lèi)似于年長(zhǎng)的孩子照管年幼的孩子。鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的最左兒子和右鄰兄弟。

firstChildnextSiblingdata樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法ABDEFGHIJKMLC樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法（1）根結(jié)點(diǎn)A有三個(gè)孩子，則將右邊的孩子結(jié)點(diǎn)托管給左邊的孩子結(jié)點(diǎn)。ABDEFGHIJKMLC樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法（2）繼續(xù)調(diào)整。結(jié)點(diǎn)B有三個(gè)孩子E、F和G；結(jié)點(diǎn)C有一個(gè)孩子H；結(jié)點(diǎn)D有兩個(gè)孩子I和J，則分別將右邊的孩子托管給左邊的孩子。ABDEFGHIJKMLC樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法（3）調(diào)整更深層次，結(jié)點(diǎn)G有一個(gè)孩子K；結(jié)點(diǎn)J有兩個(gè)孩子L和M，將M托管給L。ABDEFGHIJKMLC樹(shù)的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法最終轉(zhuǎn)換之后的結(jié)果就是一棵這樣的樹(shù)，由此可見(jiàn)，