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

樹第八章：樹

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

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

樹的基本概念及常用術(shù)語兄弟結(jié)點(diǎn)之間的左右次序關(guān)系的延拓：如果A與B是兄弟，并且A在B的左邊，則規(guī)定A的任一子孫都在B的任一子孫的左邊。A的子孫B的子孫樹的存儲(chǔ)結(jié)構(gòu)雙親表示法孩子表示法孩子兄弟表示法樹的存儲(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部分存放樹結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)元素結(jié)點(diǎn)parent部分存放該結(jié)點(diǎn)雙親結(jié)點(diǎn)的編號(hào)DataParentA-1B0C0D1E1F1G20123456樹的存儲(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]樹的存儲(chǔ)結(jié)構(gòu)——孩子表示法樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法也叫左孩子-右兄弟表示法樹的左孩子右兄弟表示法，類似于中國(guó)的長(zhǎng)兄如父的思想，它指的是由左邊的孩子結(jié)點(diǎn)來接管右邊的孩子結(jié)點(diǎn)，類似于年長(zhǎng)的孩子照管年幼的孩子。鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的最左兒子和右鄰兄弟。

firstChildnextSiblingdata樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法ABDEFGHIJKMLC樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法（1）根結(jié)點(diǎn)A有三個(gè)孩子，則將右邊的孩子結(jié)點(diǎn)托管給左邊的孩子結(jié)點(diǎn)。ABDEFGHIJKMLC樹的存儲(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樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法（3）調(diào)整更深層次，結(jié)點(diǎn)G有一個(gè)孩子K；結(jié)點(diǎn)J有兩個(gè)孩子L和M，將M托管給L。ABDEFGHIJKMLC樹的存儲(chǔ)結(jié)構(gòu)——孩子兄弟表示法孩子兄弟表示法最終轉(zhuǎn)換之后的結(jié)果就是一棵這樣的樹，由此可見，