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

🧡基本概念

🌳樹的定義

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

在任意一棵非空樹中應(yīng)滿足：
①有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)
②當(dāng)n > 1時(shí)，其余結(jié)點(diǎn)可分為m（m > 0）個(gè)互不相交的有限集合T1，T2，…，Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根結(jié)點(diǎn)的子樹==

∅ 空樹——結(jié)點(diǎn)數(shù)為0的樹

非空樹的特性：

有且僅有一個(gè)根節(jié)點(diǎn)
除了根節(jié)點(diǎn)外，任何一個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)
每個(gè)結(jié)點(diǎn)可以有0個(gè)或多個(gè)后繼

🌲基本術(shù)語

1.度

(1)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)

(2)樹的度：樹中各結(jié)點(diǎn)度的最大值

A的度為3，同時(shí)也是樹的度，B的度為2

2.葉子節(jié)點(diǎn)和分支節(jié)點(diǎn)
(1)葉子節(jié)點(diǎn)
度為0的節(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)

(2)分支節(jié)點(diǎn)
度不為0的節(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)

在上圖中，K,L,M,F,G,I,J均為葉子節(jié)點(diǎn)

3.雙親與孩子
(1)祖先結(jié)點(diǎn)：對于任何節(jié)點(diǎn)n ，它的祖先是位于根到節(jié)點(diǎn)n之間的路徑上的節(jié)點(diǎn)

(2)子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)的子節(jié)點(diǎn)

在樹中，如果有一條路徑從節(jié)點(diǎn)x到節(jié)點(diǎn)y,則稱x為y的祖先，y為x的子孫

(3)雙親結(jié)點(diǎn)（父節(jié)點(diǎn)）：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父節(jié)點(diǎn)

(4)孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)

(5)兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)

(6)堂兄弟結(jié)點(diǎn)：如果樹的兩個(gè)節(jié)點(diǎn)深度相同，但父節(jié)點(diǎn)不同，則它們是一對堂兄弟節(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)樹的深度
節(jié)點(diǎn)所在層數(shù)：根節(jié)點(diǎn)的層數(shù)為1，對于其他任何節(jié)點(diǎn)，若某節(jié)點(diǎn)在第K層，則其孩子節(jié)點(diǎn)在K+1層

樹的深度：樹中所有節(jié)點(diǎn)的最大層數(shù)，也稱為高度
在上圖中，樹的深度為4

(5)樹的類型
有序樹：樹中結(jié)點(diǎn)的各子樹從左至右是有次序的，不能互換
無序樹：樹中結(jié)點(diǎn)的各子樹從左至右是無次序的，可以互換

注：在數(shù)據(jù)結(jié)構(gòu)中，一般的討論的一般是有序樹

(6)森林
森林是m（m≥0）棵互不相交的樹的集合，m可為0，空森林

💚樹的邏輯結(jié)構(gòu)

樹的遍歷：從根節(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中所有的節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪問一次且僅被訪問一次

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

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

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

🍉前序遍歷

樹的前序遍歷操作定義為：若樹為空，則空操作返回；否則:
(1)先訪問根節(jié)點(diǎn)
(2)然后按照從左到右的順序前序遍歷根節(jié)點(diǎn)的每一顆子樹

如圖前序遍歷序列：A–>B–>D–>E–>H–>I–>F–>C–>G

🍓后序遍歷

樹的后序遍歷操作定義為：若樹為空，則空操作返回；否則:
(1)先按照從左到右的順序后序遍歷根節(jié)點(diǎn)的每一顆子樹
(2)最后訪問根節(jié)點(diǎn)

如圖后序遍歷序列：D–>H–>I–>E–>F–>B–>G–>C–A

🍒層序遍歷

樹的層序遍歷操作定義為：從樹的第一層(即根節(jié)點(diǎn)）開始，自上而下的逐層遍歷，在同一層中，按照從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪問

如圖層序遍歷序列：A–>B–>C–>D–>E–>F–>G–>H–>I

💜樹的存儲(chǔ)結(jié)構(gòu)

實(shí)現(xiàn)樹的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵在于表示樹中的節(jié)點(diǎn)之間的關(guān)系

🍀雙親表示法

基本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)節(jié)點(diǎn)（一般按層序存儲(chǔ)），數(shù)組中的一個(gè)元素對應(yīng)樹中的一個(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í)質(zhì)上是一個(gè)靜態(tài)鏈表
如圖所示：

還可以將孩子節(jié)點(diǎn)或者兄弟節(jié)點(diǎn)的下標(biāo)也進(jìn)行存儲(chǔ)

🍁孩子鏈表表示法

將結(jié)點(diǎn)的所有孩子放在一起，構(gòu)成線性表

基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來，看成是一個(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é)合起來，構(gòu)成孩子鏈表的表頭數(shù)組

鏈表中的每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該節(jié)點(diǎn)的一個(gè)孩子節(jié)點(diǎn)

方案一：
指針域的個(gè)數(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é)

提示：這里對文章進(jìn)行總結(jié)：

到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之樹的全面解讀的文章就介紹到這了,更多相關(guān)Python 數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。