一、樹的基本概念

1、樹的定義

樹是n（n>=0）個結點的有限集。當n = 0時，稱為空樹。在任意一棵非空樹中應滿足：

? ? 1、有且僅有一個特定的稱為根的結點。
? ? 2、當n>1時，其余節(jié)點可分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。

? ? 顯然，樹的定義是遞歸的，即在樹的定義中又用到了自身，樹是一種遞歸的數(shù)據(jù)結構。樹作為一種邏輯結構，同時也是一種分層結構，具有以下特點：

? ??①沒有父節(jié)點的節(jié)點稱為根節(jié)點；
??? ②每一個非根節(jié)點有且只有一個父節(jié)點；
??? ③每個子樹是不相交的；
??? ④n個結點的樹中有n-1條邊。

結合圖來看，可能會更好理解

這就是一棵典型的二叉樹

這里，2,3共有子節(jié)點5，也就是5有兩個父親，那么上圖就不是樹了。

這里，CF組成的子樹與DGH組成的子樹相交，那么上圖也不是樹了。

2、基本術語

1、祖先、子孫，父親、孩子、兄弟：

? ? ? 根節(jié)點A到結點K的路徑上的任意結點,稱為結點K的祖先。如結點B是結點K的祖先,而結點K是結點B的子孫。

? ? ? ?路徑上最接近結點K的結點E稱為K的父親,而K為結點E的孩子。根節(jié)點A是樹中唯一沒有父親的結點。

? ? ? ?有相同雙親的結點稱為兄弟,如結點K和結點L有相同的雙親E,即K和L為兄弟。

2、節(jié)點的度、樹的度

? ? ? 樹中一個結點的孩子個數(shù)稱為該結點的度,

? ? ? 樹中結點的最大度數(shù)稱為樹的度。

? ? ? 如結點B的度為2,結點D的度為3,樹的度為3。

3、分支結點、葉子結點

? ? ? 度大于0的結點稱為分支結點(又稱非終端結點，如BCDEH);

? ? ? 度為0(沒有孩子結點)的結點稱為葉子結點(又稱終端結點，如KLFGMIJ)。

? ? ?
4、結點的深度、高度、層次
? ? ?結點的層次從樹根開始定義,根結點為第1層,它的子結點為第2層,以此類推。

? ? ?雙親在同一層的結點互為堂兄弟,圖中結點G與E,F,H,I,J互為堂兄弟。

? ? ?結點的深度是從根結點開始自頂向下逐層累加的。

? ? ?結點的高度是從葉結點開始自底向上逐層累加的。

? ? ?樹的高度(或深度)是樹中結點的最大層數(shù)。圖中樹的高度為4。

5、有序樹、無序樹

? ? ?樹中任意節(jié)點的子節(jié)點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹。

? ? ?樹中任意節(jié)點的子節(jié)點之間有順序關系，這種樹稱為有序樹

6、路徑、路徑長度。

? ? ? 樹中兩個結點之間的路徑是由這兩個結點之間所經(jīng)過的結點序列構成的,而路徑長度是路徑上所經(jīng)過的邊的個數(shù)。
? ? ? 注意:由于樹中的分支是有向的,即從雙親指向孩子,所以樹中的路徑是從上向下的,同一雙親的兩個孩子之間不存在路徑。

7、森林

? ? ?森林是m (m≥0)棵互不相交的樹的集合。

? ? ? 森林的概念與樹的概念十分相近，因為只要把樹的根結點刪去就成了森林。反之，只要給m棵獨立的樹加上一個結點，并把這m棵樹作為該結點的子樹，則森林就變成了樹。

注意:上述概念無須刻意記憶， 根據(jù)實例理解即可。

二、樹的存儲結構

? ? 1、雙親表示法

實現(xiàn)：定義結構數(shù)組，存放樹的結點，每個結點有兩個域，分別是數(shù)據(jù)域和指針域（雙親域），數(shù)據(jù)域用于存放結點本身信息，指針域用于存放本結點的雙親結點在數(shù)組中的位置。

雙親表示的結點結構

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

雙親表示法示意圖：

雙親表示法結構定義：

//結點結構
struct PTNode
{   int data;           //數(shù)據(jù)域int parent;         //雙親域
}PTNode;//樹結構struct
{PTNode nodes[100];    //結點數(shù)組int r,n;                  //根結點位置和結點數(shù)
}

? ? 雙親表示法的特點

• 由于根結點是沒有雙親的，約定根結點的位置位置域為-1.
• 根據(jù)結點的parent指針很容易找到它的雙親結點。所用時間復雜度為O(1)，直到parent為-1時，表示找到了樹結點的根。
• 缺點：如果要找到孩子結點，需要遍歷整個結構才行。

? ? 2、孩子鏈表法

? ? 把每個結點的孩子結點排列起來，以單鏈表作存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空表，然后n個頭指針又組成一個線性表，采用順序存儲結構，存放在一個一維數(shù)組中。

孩子表示法有兩種結點結構：孩子鏈表的孩子結點和表頭數(shù)組的表頭結點

• 孩子鏈表的孩子結點的結點結構：

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

• 孩子鏈表的雙親結點的結點結構：

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

孩子鏈表的結構示意圖：

孩子鏈表表示法的結構定義：

//孩子結點
typedef struct CTNode
{   int child;struct CTNode *next;
}*ChildPtr; //雙親結點
typedef struct
{   ElemType data;ChildPtr firstchild;
}CTBox;//樹結構
typedef struct
{   CTBox nodes[100];int r, n;              //根的位置和結點數(shù)
}CTree;

? ? 特點：找孩子容易，找雙親困難。

? ? 對于孩子表示法，查找某個結點的某個孩子，或者找某個結點的兄弟，只需要查找這個結點的孩子單鏈表即可。但是當要尋找某個結點的雙親時，就不是那么方便了。所以可以將雙親表示法和孩子表示法結合，形成雙親孩子表示法。

樹的雙親孩子鏈表的結構示意圖：

樹的雙親孩子表示法結構定義:

typedef struct CTNode{  // 孩子結點int child;  // 孩子結點的下標struct CTNode * next;  // 指向下一結點的指針
}*ChildPtr;typedef struct {  // 表頭結構int data;  // 存放在數(shù)中的結點數(shù)據(jù)int parent;      // 存放雙親的下標ChildPtr firstchild;  // 指向第一個孩子的指針
}CTBox;typedef struct {  // 樹結構CTBox nodes[100]; // 結點數(shù)組int r;  // 根的位置int n;  // 結點樹
}CTree;

3、孩子兄弟表示法

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

孩子兄弟表示法的結點結構：

data(數(shù)據(jù)域)	firstchild(指針域)	rightsib(指針域)
存儲結點的數(shù)據(jù)信息	存儲該結點的第一個孩子的存儲地址	存儲該結點的右兄弟結點的存儲地址

孩子兄弟表示法結構示意圖：

孩子兄弟結點的結構定義：

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