前言

提示：以下是本篇文章正文內(nèi)容

🧡基本概念

🌳樹(shù)的定義

樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，n = 0時(shí)，稱(chēng)為空樹(shù)，這是一種特殊情況

在任意一棵非空樹(shù)中應(yīng)滿(mǎn)足：
①有且僅有一個(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ā)，按照某種次序訪(fǎng)問(wèn)樹(shù)中所有的節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次

訪(fǎng)問(wèn)：抽象操作，可以是對(duì)節(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出節(jié)點(diǎn)的數(shù)據(jù)

遍歷的實(shí)質(zhì)：樹(shù)的結(jié)構(gòu)(非線(xiàn)性結(jié)構(gòu)) – > 線(xiàn)性結(jié)構(gòu)

樹(shù)通常有前序(根)遍歷，后序(根)遍歷，層序(次)遍歷三種

🍉前序遍歷

樹(shù)的前序遍歷操作定義為：若樹(shù)為空，則空操作返回；否則:
(1)先訪(fǎng)問(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)最后訪(fǎng)問(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è)訪(fǎng)問(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)成線(xiàn)性表

基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來(lái)，看成是一個(gè)線(xiàn)性表，且以單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表。這n個(gè)單鏈表共有n個(gè)頭指針，這n個(gè)頭指針又組成了一個(gè)線(xiàn)性表,為了便于進(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)文章希望大家以后多多支持腳本之家！

最新評(píng)論