前言

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

🧡基本概念

🌳樹的定義

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

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

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

非空樹的特性：

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

🌲基本術(shù)語

1.度

(1)結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)

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

A的度為3，同時也是樹的度，B的度為2

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

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

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

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

(2)子孫結(jié)點：一個結(jié)點含有的子樹的根結(jié)點的子節(jié)點

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

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

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

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

(6)堂兄弟結(jié)點：如果樹的兩個節(jié)點深度相同，但父節(jié)點不同，則它們是一對堂兄弟節(jié)點
B,C,D互為兄弟節(jié)點，E,G,I互為堂兄弟節(jié)點，B為E,F的父節(jié)點，而E,F為B的子節(jié)點

(4)樹的深度
節(jié)點所在層數(shù)：根節(jié)點的層數(shù)為1，對于其他任何節(jié)點，若某節(jié)點在第K層，則其孩子節(jié)點在K+1層

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

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

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

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

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

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

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

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

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

🍉前序遍歷

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

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

🍓后序遍歷

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

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

🍒層序遍歷

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

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

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

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

🍀雙親表示法

基本思想：用一維數(shù)組來存儲樹的各個節(jié)點（一般按層序存儲），數(shù)組中的一個元素對應(yīng)樹中的一個節(jié)點，包括節(jié)點的數(shù)據(jù)信息和節(jié)點的雙親在數(shù)組中的下標。

節(jié)點結(jié)構(gòu)

struct PNode
{
	DataType data; //數(shù)據(jù)域
	int parent;   //指針域，雙親在數(shù)組中的下標
}

樹的雙親表示法實質(zhì)上是一個靜態(tài)鏈表
如圖所示：

還可以將孩子節(jié)點或者兄弟節(jié)點的下標也進行存儲

🍁孩子鏈表表示法

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

基本思想：把每個結(jié)點的孩子排列起來，看成是一個線性表，且以單鏈表存儲，則n個結(jié)點共有n個孩子鏈表。這n個單鏈表共有n個頭指針，這n個頭指針又組成了一個線性表,為了便于進行查找采用順序存儲。最后, 將存放n個頭指針的數(shù)組和存放n個結(jié)點的數(shù)組結(jié)合起來，構(gòu)成孩子鏈表的表頭數(shù)組

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

方案一：
指針域的個數(shù)等于樹的深度

缺點：浪費存儲空間

方案二：
指針域的個數(shù)等于該結(jié)點的度

缺點：每個結(jié)點結(jié)構(gòu)不一致

孩子節(jié)點

struct CTNode
{
	int child;
	CTNode *next; // 指向下一個孩子結(jié)點的指針
}

表頭結(jié)點

struct CBNode
{
	DataType data;
	CTNode *firstChild; // 每個鏈表的頭指針
}

存儲結(jié)構(gòu)

🍃雙親孩子表示法

在孩子鏈表中表頭數(shù)組添加了節(jié)點的雙親結(jié)點

🍂孩子兄弟表示法

某節(jié)點的第一個孩子是唯一的，某一節(jié)點的右兄弟是唯一的，設(shè)置兩個分別指向該節(jié)點的第一個孩子和右兄弟的指針

struct TNode
{
	DataType data;
	TNode *firstChild,*rightSib;
}

總結(jié)

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

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

最新評論