樹(shù)的遞歸結(jié)構(gòu)

從一張圖中解釋什么是樹(shù)

這張圖，主要講解關(guān)于cart這個(gè)單詞的所有的可能組合，按照常理，需要先考慮三個(gè)字母的排列，然后對(duì)三個(gè)字母進(jìn)行拆分，直到最后一個(gè)節(jié)點(diǎn)，這個(gè)過(guò)程就類似于樹(shù) 到底什么是樹(shù)

什么是樹(shù)

樹(shù)是節(jié)點(diǎn)集合(A tree is a collection of nodes)，

集合：集合是允許一個(gè)元素都沒(méi)有的集合，稱之為空集。

首先，集合是允許一個(gè)元素都沒(méi)有的集合，稱之為空集，那么書(shū)是不是也允許一個(gè)節(jié)點(diǎn)都沒(méi)有的呢，是的，一個(gè)節(jié)點(diǎn)都沒(méi)有的樹(shù)，稱之為空樹(shù)，如果不是空的，則會(huì)存在根節(jié)點(diǎn)r和零個(gè)或更多非空子樹(shù)，T1，T2.。。Tk，他們的根由來(lái)自r的有向連接，什么叫有向邊，大致可以理解為箭頭。用圖的關(guān)系說(shuō)明樹(shù)的內(nèi)部關(guān)系

根節(jié)點(diǎn)（root）一棵樹(shù)只有一個(gè)跟節(jié)點(diǎn)，所有的節(jié)點(diǎn)都在該節(jié)點(diǎn)的下面，嘗試把圖倒過(guò)來(lái)看，可以看成一個(gè)我們?nèi)粘Ｒ?jiàn)到的數(shù)的根部，在這里顯然字母A就是這顆樹(shù)的根節(jié)點(diǎn)。

子節(jié)點(diǎn)，父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)，它對(duì)應(yīng)的下面有連這的節(jié)點(diǎn)，那么被連著的節(jié)點(diǎn)就是這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，也叫做孩子，那么這個(gè)節(jié)點(diǎn)叫做被連接的節(jié)點(diǎn)的父親，看圖，B被A連這，所以B是A的一個(gè)孩子，同理，CDE等等這一行都是A的孩子，同時(shí)F，它連這K L M 同時(shí)被A連這，那么F是A的一個(gè)孩子，同時(shí)又是K L M 的父親。

樹(shù)葉：樹(shù)葉就是那些沒(méi)有孩子的節(jié)點(diǎn)，比如B，C，D等等，例如下圖的綠色部分。

兄弟: 按照我們的理解，同一個(gè)父母生的當(dāng)然是兄妹，如下圖所示，顏色相同的都是兄妹

路徑 我們同樣可以定義從父親到他孩子的路徑，下面的路徑，我們就取上圖的一部分，一個(gè)子樹(shù)，作為例子

比如，A->O的路徑為A->E->J->O它的長(zhǎng)度為3，實(shí)際為它的邊數(shù)，圖中紅色的部分。

節(jié)點(diǎn)的深度：節(jié)點(diǎn)的深度指的是節(jié)點(diǎn)到樹(shù)根的長(zhǎng)度，看下圖，我們可以輕易的知道，j節(jié)點(diǎn)的深度為2，可以理解為 A-> E -> J 邊長(zhǎng)為2.顯然，此時(shí)根節(jié)點(diǎn)的深度為0.

節(jié)點(diǎn)的高度：高度是從節(jié)點(diǎn)到葉子的最長(zhǎng)路徑，比如節(jié)點(diǎn)F的高度為1，顯然所有葉子節(jié)點(diǎn)高度為0.

樹(shù)的高度，樹(shù)的高度是跟的高度，顯然在這圖中，樹(shù)的高度為3，A->O

樹(shù)的特點(diǎn)

按照正常的邏輯，一個(gè)人不能同時(shí)有兩個(gè)父親，所以樹(shù)也一樣，下圖的兩個(gè)就解釋了這個(gè)問(wèn)題

一顆正常的樹(shù)，它的樹(shù)枝是不會(huì)長(zhǎng)成一個(gè)圓的，所以，樹(shù)中，是不可能出現(xiàn)環(huán)形的。圖中，紅色箭頭構(gòu)成了一個(gè)環(huán)，所以都不是一顆樹(shù)。

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

樹(shù)的存儲(chǔ)結(jié)構(gòu)有三種，分別為，雙親表示法，孩子表示法，孩子兄弟表示法。

雙親表示法

假設(shè)一組連續(xù)空間保存著樹(shù)的特點(diǎn)，同時(shí)在每個(gè)節(jié)點(diǎn)中，附帶一個(gè)指示器表示雙親節(jié)點(diǎn)中鏈表的為位置，也就是說(shuō)，每個(gè)節(jié)點(diǎn)除了知道自己是誰(shuí)以外，還知道他的雙親在哪里。

其中data是數(shù)據(jù)域，存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)信息。而parent是指針域，存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。

//樹(shù)的雙親表示法結(jié)點(diǎn)結(jié)構(gòu)定義
#define MAX_TRUE_SIZE 100
typedef int TElemType //樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類型

//結(jié)點(diǎn)結(jié)構(gòu)
typedef struct PTNode   
{
	TElemType data;  //結(jié)點(diǎn)數(shù)據(jù)
	int parent;   	//雙親位置
}PTNode

//樹(shù)結(jié)構(gòu)
typedef struct
{
	PTNode nodes[MAX_TRUE_SIZE];  //結(jié)點(diǎn)數(shù)組
	int r,n     //根的位置和結(jié)點(diǎn)數(shù)
}PTree

有了這樣的數(shù)據(jù)結(jié)構(gòu)就可以來(lái)實(shí)現(xiàn)雙親表示法。由于根結(jié)點(diǎn)是沒(méi)有雙親的，所以我們約定根結(jié)點(diǎn)的位置域設(shè)置為-1，這也就意味著，我們所有的結(jié)點(diǎn)都存有他雙親的位置。如圖1-2中的樹(shù)結(jié)構(gòu)和表1-3中的樹(shù)雙親表示。

這樣的存儲(chǔ)結(jié)構(gòu)，我們可以根據(jù)結(jié)點(diǎn)的parent’指針很容易找到他的雙親結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)，直到parent為-1時(shí)，表示找到了樹(shù)結(jié)點(diǎn)的根

孩子表示法

換一種完全不同的考慮方法，由于樹(shù)中每個(gè)結(jié)點(diǎn)可能有多棵子樹(shù)，可以考慮用多重鏈表。每個(gè)結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一顆子樹(shù)的根結(jié)點(diǎn)，我們把這種方法叫做多重鏈表的表示方法。不過(guò)，樹(shù)的每個(gè)結(jié)點(diǎn)的度，也就是他的孩子個(gè)數(shù)是不同的，所以設(shè)計(jì)兩種方法：

方案一

指針域的個(gè)數(shù)就等于樹(shù)的度，樹(shù)的度就是樹(shù)各個(gè)結(jié)點(diǎn)度的最大值。其結(jié)構(gòu)如圖

其中data是數(shù)據(jù)域，child1到childd是指針域，用來(lái)指向該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。對(duì)于圖1-1來(lái)說(shuō)，樹(shù)的度是3，所以我們指針域個(gè)數(shù)就是3，

方案二

每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度，我們專門取一個(gè)位置來(lái)存儲(chǔ)結(jié)點(diǎn)指針的個(gè)數(shù)。

data為指針域，degree為度域，也就是存儲(chǔ)該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的個(gè)數(shù)

這就是我們要說(shuō)的孩子表示法，把每個(gè)結(jié)點(diǎn)的孩子都排列起來(lái)，以單鏈表為存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果是葉子結(jié)點(diǎn)則此單鏈表為空。然后n個(gè)頭指針又組成一個(gè)線性表，采用順序存儲(chǔ)結(jié)構(gòu)，存放進(jìn)一個(gè)一維數(shù)組，

為此，設(shè)計(jì)兩種存儲(chǔ)結(jié)構(gòu)，一個(gè)是孩子鏈表的孩子結(jié)點(diǎn)，

child是數(shù)據(jù)域，用來(lái)存儲(chǔ)某個(gè)結(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)。next是指針域，用來(lái)存儲(chǔ)指向結(jié)點(diǎn)的下一個(gè)孩子結(jié)點(diǎn)的指針。另一個(gè)是表頭數(shù)組的表頭結(jié)點(diǎn)。

data是數(shù)據(jù)域，存儲(chǔ)某結(jié)點(diǎn)的數(shù)據(jù)信息，firstchild是頭指針域，存儲(chǔ)該結(jié)點(diǎn)的孩子鏈表的頭指針。

//樹(shù)的孩子表示法結(jié)構(gòu)定義
#define MAX_TRUE_SIZE 100
typedef struct CTNode  //孩子結(jié)點(diǎn)
{
	int child；
	struct CTNode *next;
}*ChildPtr;
//表頭結(jié)構(gòu)
typedef struct
{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
//樹(shù)結(jié)構(gòu)
typedef struct
{
	CTBox nodes[MAX_TRUE_SIZE];  //結(jié)點(diǎn)數(shù)組
	int r,n;               //根的位置和結(jié)點(diǎn)數(shù)
}CTree

把把雙親表示法和孩子表示法綜合一下表示如下

這種表示法叫做雙親孩子表示法，應(yīng)該算是孩子表示法的改進(jìn)。

孩子兄弟表示法

任一棵樹(shù)，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此。我們?cè)O(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此結(jié)點(diǎn)的右兄弟。

data是數(shù)據(jù)域，fitstchild為指針域，存儲(chǔ)該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)的存儲(chǔ)地址，rightsib是指針域，存儲(chǔ)該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的存儲(chǔ)位置。

//孩子兄弟表示法結(jié)構(gòu)定義
typedef struct CSDNode
{
	TElemType data;
	struct CSNode *firstchild,*rightsib;
}CSNode,*CSTree;

這種方法的示意圖如下所示

這種表示法，給查找某個(gè)結(jié)點(diǎn)的某個(gè)孩子帶來(lái)了方便，只需要通過(guò)firstchild找到此結(jié)點(diǎn)的長(zhǎng)子，然后在通過(guò)長(zhǎng)子結(jié)點(diǎn)的rightsib找到它的二弟，接著一直找下去，直到找到具體的孩子。
編輯：hfy