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

從一張圖中解釋什么是樹

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

什么是樹

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

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

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

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

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

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

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

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

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

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

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

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

樹的特點

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

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

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

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

雙親表示法

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

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

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

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

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

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

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

孩子表示法

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

方案一

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

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

方案二

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

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

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

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

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

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

//樹的孩子表示法結(jié)構(gòu)定義
#define MAX_TRUE_SIZE 100
typedef struct CTNode  //孩子結(jié)點
{
	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é)點數(shù)組
	int r,n;               //根的位置和結(jié)點數(shù)
}CTree

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

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

孩子兄弟表示法

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

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

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

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

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