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

樹第八章：樹

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

圖中的兩棵樹作為無序樹是相同的，但作為有序樹是不同的，因為結(jié)點A的兩個兒子在兩棵樹中左右次序是不同的。

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

0

12345678912∧

34∧56∧789∧ABCDEFGHJIABCDEFGHIJ

0

12345678912∧

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

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