之前談?wù)摰逆湵斫嬗场㈥?duì)列都是一對(duì)一的線性結(jié)構(gòu)，那么一對(duì)多的情況如何處理呢睬关？“樹”有效的解決了這種一對(duì)多的數(shù)據(jù)結(jié)構(gòu)關(guān)系矮燎。

一、樹的定義

1.樹的定義

樹（Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集转砖。n=0時(shí)稱為空樹须鼎。在任意一顆非空樹中：

1. 有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)；
2. 當(dāng)n>1時(shí)府蔗，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互補(bǔ)交互的有限集T1莉兰、T2...Tm，其中每一個(gè)集合本身又是一棵樹礁竞，并稱為根的子樹（SubTree）糖荒。
   
   Tree

2.樹的特點(diǎn)

• n>0時(shí)，根節(jié)點(diǎn)是唯一的模捂，不可能存在多個(gè)根節(jié)點(diǎn)捶朵。數(shù)據(jù)結(jié)構(gòu)中的樹只有一個(gè)根節(jié)點(diǎn)蜘矢。
• m>0時(shí)，子樹的個(gè)數(shù)沒有限制综看，但他們一定是互不相交的品腹。

3.結(jié)點(diǎn)的分類

• 結(jié)點(diǎn)：樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和若干指向其子樹的分支。
• 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹红碑。
• 葉子結(jié)點(diǎn)（Leaf）/終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)舞吭。
• 分支結(jié)點(diǎn)/非終端結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。
• 內(nèi)部結(jié)點(diǎn)：除根節(jié)點(diǎn)以外析珊，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)羡鸥。
• 樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。
  
  結(jié)點(diǎn)的分類

4.結(jié)點(diǎn)之間的關(guān)系

• 孩子（Child）和雙親（Parent）：結(jié)點(diǎn)的子樹的根忠寻，相應(yīng)的惧浴，該結(jié)點(diǎn)稱為孩子的雙親。（注意是雙親奕剃，不是單親）
• 兄弟（sibling）：同一個(gè)雙親的孩子之間互稱兄弟衷旅。
• 結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過分支上的所有結(jié)點(diǎn)。
• 子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫纵朋。
• 無序樹和有序樹：如果將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的柿顶，不能互換的，則稱該數(shù)為有序樹操软，否則為無序樹嘁锯。
• 森林(fores):m(m>=0)棵互不相較的樹的集合。

二寺鸥、樹的存儲(chǔ)結(jié)構(gòu)

對(duì)于存儲(chǔ)結(jié)構(gòu)，可能會(huì)聯(lián)想到前面的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)品山。但是對(duì)于數(shù)這種可能會(huì)有很多孩子的特殊數(shù)據(jù)結(jié)構(gòu)胆建，只用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)很那實(shí)現(xiàn)，那么可以將這兩者結(jié)合肘交，產(chǎn)生主要的三種存儲(chǔ)結(jié)構(gòu)表示法：雙親表示法笆载、孩子表示法、孩子兄弟表示法涯呻。

1.雙親表示法

雙親表示法定義

假設(shè)以一組連續(xù)空間存儲(chǔ)數(shù)的結(jié)點(diǎn)凉驻，同時(shí)在每個(gè)結(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)到鏈表中的位置复罐。

雙親表示的結(jié)點(diǎn)結(jié)構(gòu)

代碼實(shí)現(xiàn)雙親表示法

/* 樹的雙親表法結(jié)點(diǎn)結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

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

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

雙親表示法的特點(diǎn)

• 由于根結(jié)點(diǎn)是沒有雙親的涝登，約定根結(jié)點(diǎn)的位置位置域?yàn)?1.
• 根據(jù)結(jié)點(diǎn)的parent指針很容易找到它的雙親結(jié)點(diǎn)。所用時(shí)間復(fù)雜度為O(1)效诅，直到parent為-1時(shí)胀滚，表示找到了樹結(jié)點(diǎn)的根趟济。
• 缺點(diǎn)：如果要找到孩子結(jié)點(diǎn)，需要遍歷整個(gè)結(jié)構(gòu)才行咽笼。

2.孩子表示法

孩子表示法定義

把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來顷编，以單鏈表作為存儲(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ù)組中钮惠。

孩子表示法

孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)

孩子表示法有兩種結(jié)點(diǎn)結(jié)構(gòu)：孩子鏈表的孩子結(jié)點(diǎn)和表頭數(shù)組的表頭結(jié)點(diǎn)

• 孩子鏈表的孩子結(jié)點(diǎn)

• 表頭數(shù)組的表頭結(jié)點(diǎn)

代碼實(shí)現(xiàn)孩子表示法

/* 樹的孩子表示法結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CTNode{  // 孩子結(jié)點(diǎn)
    int child; // 孩子結(jié)點(diǎn)的下標(biāo)
    struct CTNode * next; // 指向下一結(jié)點(diǎn)的指針
}*ChildPtr;

typedef struct {  // 表頭結(jié)構(gòu)
    ElemeType data; // 存放在數(shù)中的結(jié)點(diǎn)數(shù)據(jù)
    ChildPtr firstchild; // 指向第一個(gè)孩子的指針
}CTBox;

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

雙親孩子表示法定義

對(duì)于孩子表示法，查找某個(gè)結(jié)點(diǎn)的某個(gè)孩子其监，或者找某個(gè)結(jié)點(diǎn)的兄弟萌腿，只需要查找這個(gè)結(jié)點(diǎn)的孩子單鏈表即可。但是當(dāng)要尋找某個(gè)結(jié)點(diǎn)的雙親時(shí)抖苦，就不是那么方便了毁菱。所以可以將雙親表示法和孩子表示法結(jié)合，形成雙親孩子表示法锌历。

/* 樹的雙親孩子表示法結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CTNode{  // 孩子結(jié)點(diǎn)
    int child;  // 孩子結(jié)點(diǎn)的下標(biāo)
    struct CTNode * next;  // 指向下一結(jié)點(diǎn)的指針
}*ChildPtr;

typedef struct {  // 表頭結(jié)構(gòu)
    ElemeType data;  // 存放在數(shù)中的結(jié)點(diǎn)數(shù)據(jù)
    int parent;      // 存放雙親的下標(biāo)
    ChildPtr firstchild;  // 指向第一個(gè)孩子的指針
}CTBox;

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

3.孩子兄弟表示法

孩子兄弟表示法定義

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

孩子兄弟表示法的結(jié)點(diǎn)結(jié)構(gòu)

代碼實(shí)現(xiàn)孩子兄弟表示法

/* 樹的孩子兄弟表示法結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CSNode{
    ElemeType data;
    struct CSNode * firstchild;
    struct CSNode * rightsib;
    
}CSNode, *CSTree;