Python數(shù)據(jù)結(jié)構(gòu)之樹(shù)的全面解讀
提示:以下是本篇文章正文內(nèi)容
🧡基本概念
🌳樹(shù)的定義
樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合,n = 0時(shí),稱(chēng)為空樹(shù),這是一種特殊情況
在任意一棵非空樹(shù)中應(yīng)滿足:
①有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)
②當(dāng)n > 1時(shí),其余結(jié)點(diǎn)可分為m(m > 0)個(gè)互不相交的有限集合T1,T2,…,Tm,其中每個(gè)集合本身又是一棵樹(shù),并且稱(chēng)為根結(jié)點(diǎn)的子樹(shù)==
∅ 空樹(shù)——結(jié)點(diǎn)數(shù)為0的樹(shù)
非空樹(shù)的特性:
有且僅有一個(gè)根節(jié)點(diǎn)
除了根節(jié)點(diǎn)外,任何一個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)
每個(gè)結(jié)點(diǎn)可以有0個(gè)或多個(gè)后繼
🌲基本術(shù)語(yǔ)
1.度
(1)結(jié)點(diǎn)的度:結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)
(2)樹(shù)的度:樹(shù)中各結(jié)點(diǎn)度的最大值
A的度為3,同時(shí)也是樹(shù)的度,B的度為2
2.葉子節(jié)點(diǎn)和分支節(jié)點(diǎn)
(1)葉子節(jié)點(diǎn)
度為0的節(jié)點(diǎn),也稱(chēng)為終端結(jié)點(diǎn)
(2)分支節(jié)點(diǎn)
度不為0的節(jié)點(diǎn),也稱(chēng)為非終端結(jié)點(diǎn)
在上圖中,K,L,M,F,G,I,J均為葉子節(jié)點(diǎn)
3.雙親與孩子
(1)祖先結(jié)點(diǎn):對(duì)于任何節(jié)點(diǎn)n ,它的祖先是位于根到節(jié)點(diǎn)n之間的路徑上的節(jié)點(diǎn)
(2)子孫結(jié)點(diǎn):一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)的子節(jié)點(diǎn)
在樹(shù)中,如果有一條路徑從節(jié)點(diǎn)x到節(jié)點(diǎn)y,則稱(chēng)x為y的祖先,y為x的子孫
(3)雙親結(jié)點(diǎn)(父節(jié)點(diǎn)):若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn),則這個(gè)結(jié)點(diǎn)稱(chēng)為其子結(jié)點(diǎn)的父節(jié)點(diǎn)
(4)孩子結(jié)點(diǎn):一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)
(5)兄弟結(jié)點(diǎn):具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)
(6)堂兄弟結(jié)點(diǎn):如果樹(shù)的兩個(gè)節(jié)點(diǎn)深度相同,但父節(jié)點(diǎn)不同,則它們是一對(duì)堂兄弟節(jié)點(diǎn)
B,C,D互為兄弟節(jié)點(diǎn),E,G,I互為堂兄弟節(jié)點(diǎn),B為E,F的父節(jié)點(diǎn),而E,F為B的子節(jié)點(diǎn)
(4)樹(shù)的深度
節(jié)點(diǎn)所在層數(shù):根節(jié)點(diǎn)的層數(shù)為1,對(duì)于其他任何節(jié)點(diǎn),若某節(jié)點(diǎn)在第K層,則其孩子節(jié)點(diǎn)在K+1層
樹(shù)的深度:樹(shù)中所有節(jié)點(diǎn)的最大層數(shù),也稱(chēng)為高度
在上圖中,樹(shù)的深度為4
(5)樹(shù)的類(lèi)型
有序樹(shù):樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右是有次序的,不能互換
無(wú)序樹(shù):樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右是無(wú)次序的,可以互換
注:在數(shù)據(jù)結(jié)構(gòu)中,一般的討論的一般是有序樹(shù)
(6)森林
森林是m(m≥0)棵互不相交的樹(shù)的集合,m可為0,空森林
💚樹(shù)的邏輯結(jié)構(gòu)
樹(shù)的遍歷:從根節(jié)點(diǎn)出發(fā),按照某種次序訪問(wèn)樹(shù)中所有的節(jié)點(diǎn),使得每個(gè)節(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次
訪問(wèn):抽象操作,可以是對(duì)節(jié)點(diǎn)進(jìn)行的各種處理,這里簡(jiǎn)化為輸出節(jié)點(diǎn)的數(shù)據(jù)
遍歷的實(shí)質(zhì):樹(shù)的結(jié)構(gòu)(非線性結(jié)構(gòu)) – > 線性結(jié)構(gòu)
樹(shù)通常有前序(根)遍歷,后序(根)遍歷,層序(次)遍歷三種
🍉前序遍歷
樹(shù)的前序遍歷操作定義為:若樹(shù)為空,則空操作返回;否則:
(1)先訪問(wèn)根節(jié)點(diǎn)
(2)然后按照從左到右的順序前序遍歷根節(jié)點(diǎn)的每一顆子樹(shù)
如圖前序遍歷序列:A–>B–>D–>E–>H–>I–>F–>C–>G
🍓后序遍歷
樹(shù)的后序遍歷操作定義為:若樹(shù)為空,則空操作返回;否則:
(1)先按照從左到右的順序后序遍歷根節(jié)點(diǎn)的每一顆子樹(shù)
(2)最后訪問(wèn)根節(jié)點(diǎn)
如圖后序遍歷序列:D–>H–>I–>E–>F–>B–>G–>C–A
🍒層序遍歷
樹(shù)的層序遍歷操作定義為:從樹(shù)的第一層(即根節(jié)點(diǎn))開(kāi)始,自上而下的逐層遍歷,在同一層中,按照從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪問(wèn)
如圖層序遍歷序列:A–>B–>C–>D–>E–>F–>G–>H–>I
💜樹(shù)的存儲(chǔ)結(jié)構(gòu)
實(shí)現(xiàn)樹(shù)的存儲(chǔ)結(jié)構(gòu),關(guān)鍵在于表示樹(shù)中的節(jié)點(diǎn)之間的關(guān)系
🍀雙親表示法
基本思想:用一維數(shù)組來(lái)存儲(chǔ)樹(shù)的各個(gè)節(jié)點(diǎn)(一般按層序存儲(chǔ)),數(shù)組中的一個(gè)元素對(duì)應(yīng)樹(shù)中的一個(gè)節(jié)點(diǎn),包括節(jié)點(diǎn)的數(shù)據(jù)信息和節(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。
節(jié)點(diǎn)結(jié)構(gòu)
struct PNode { DataType data; //數(shù)據(jù)域 int parent;//指針域,雙親在數(shù)組中的下標(biāo) }
樹(shù)的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表
如圖所示:
還可以將孩子節(jié)點(diǎn)或者兄弟節(jié)點(diǎn)的下標(biāo)也進(jìn)行存儲(chǔ)
🍁孩子鏈表表示法
將結(jié)點(diǎn)的所有孩子放在一起,構(gòu)成線性表
基本思想:把每個(gè)結(jié)點(diǎn)的孩子排列起來(lái),看成是一個(gè)線性表,且以單鏈表存儲(chǔ),則n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表。這n個(gè)單鏈表共有n個(gè)頭指針,這n個(gè)頭指針又組成了一個(gè)線性表,為了便于進(jìn)行查找采用順序存儲(chǔ)。最后, 將存放n個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來(lái),構(gòu)成孩子鏈表的表頭數(shù)組
鏈表中的每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和多個(gè)指針域,每個(gè)指針域指向該節(jié)點(diǎn)的一個(gè)孩子節(jié)點(diǎn)
方案一:
指針域的個(gè)數(shù)等于樹(shù)的深度
缺點(diǎn):浪費(fèi)存儲(chǔ)空間
方案二:
指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度
缺點(diǎn):每個(gè)結(jié)點(diǎn)結(jié)構(gòu)不一致
孩子節(jié)點(diǎn)
struct CTNode { int child; CTNode *next; // 指向下一個(gè)孩子結(jié)點(diǎn)的指針 }
表頭結(jié)點(diǎn)
struct CBNode { DataType data; CTNode *firstChild; // 每個(gè)鏈表的頭指針 }
存儲(chǔ)結(jié)構(gòu)
🍃雙親孩子表示法
在孩子鏈表中表頭數(shù)組添加了節(jié)點(diǎn)的雙親結(jié)點(diǎn)
🍂孩子兄弟表示法
某節(jié)點(diǎn)的第一個(gè)孩子是唯一的,某一節(jié)點(diǎn)的右兄弟是唯一的,設(shè)置兩個(gè)分別指向該節(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針
struct TNode { DataType data; TNode *firstChild,*rightSib; }
總結(jié)
提示:這里對(duì)文章進(jìn)行總結(jié):
到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之樹(shù)的全面解讀的文章就介紹到這了,更多相關(guān)Python 數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站!
版權(quán)聲明:本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有,歡迎引用、轉(zhuǎn)載,請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站,禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像,否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái),僅供學(xué)習(xí)參考,不代表本站立場(chǎng),如有內(nèi)容涉嫌侵權(quán),請(qǐng)聯(lián)系alex-e#qq.com處理。