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

從一張圖中解釋什么是樹

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

什么是樹

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

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

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

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

子節(jié)點(diǎn)，父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)，它對應(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 的父親。

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

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

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

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

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

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

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

樹的特點(diǎn)

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

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

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

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

雙親表示法

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

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

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

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

//樹結(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)就可以來實(shí)現(xiàn)雙親表示法。由于根結(jié)點(diǎn)是沒有雙親的，所以我們約定根結(jié)點(diǎn)的位置域設(shè)置為-1，這也就意味著，我們所有的結(jié)點(diǎn)都存有他雙親的位置。如圖1-2中的樹結(jié)構(gòu)和表1-3中的樹雙親表示。

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

孩子表示法

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

方案一

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

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

方案二

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

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

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

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

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

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

//樹的孩子表示法結(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;
//樹結(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)。

孩子兄弟表示法

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

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

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

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

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