樹的遞歸結構和樹的存儲結構分析

樹的遞歸結構

從一張圖中解釋什么是樹

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

什么是樹

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

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

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

根節(jié)點（root）一棵樹只有一個跟節(jié)點，所有的節(jié)點都在該節(jié)點的下面，嘗試把圖倒過來看，可以看成一個我們日常見到的數(shù)的根部，在這里顯然字母A就是這顆樹的根節(jié)點。

子節(jié)點，父節(jié)點，一個節(jié)點，它對應的下面有連這的節(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等等，例如下圖的綠色部分。

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

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

比如，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)形的。圖中，紅色箭頭構成了一個環(huán)，所以都不是一顆樹。

樹的存儲結構

樹的存儲結構有三種，分別為，雙親表示法，孩子表示法，孩子兄弟表示法。

雙親表示法

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

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

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

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

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

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

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

孩子表示法

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

方案一

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

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

方案二

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

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

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

為此，設計兩種存儲結構，一個是孩子鏈表的孩子結點，

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

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

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

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

這種表示法叫做雙親孩子表示法，應該算是孩子表示法的改進。

孩子兄弟表示法

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

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

//孩子兄弟表示法結構定義
typedef struct CSDNode
{
	TElemType data;
	struct CSNode *firstchild,*rightsib;
}CSNode,*CSTree;

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

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