人妖在线一区,国产日韩欧美一区二区综合在线,国产啪精品视频网站免费,欧美内射深插日本少妇

新聞動(dòng)態(tài)

Python數(shù)據(jù)結(jié)構(gòu)之樹(shù)的全面解讀

發(fā)布日期:2021-12-15 02:40 | 文章來(lái)源:CSDN

提示:以下是本篇文章正文內(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處理。

相關(guān)文章

實(shí)時(shí)開(kāi)通

自選配置、實(shí)時(shí)開(kāi)通

免備案

全球線路精選!

全天候客戶(hù)服務(wù)

7x24全年不間斷在線

專(zhuān)屬顧問(wèn)服務(wù)

1對(duì)1客戶(hù)咨詢(xún)顧問(wèn)

在線
客服

在線客服:7*24小時(shí)在線

客服
熱線

400-630-3752
7*24小時(shí)客服服務(wù)熱線

關(guān)注
微信

關(guān)注官方微信
頂部