1.樹(shù)三種不同的表示法：
- 雙親表示法
- 孩子表示法
- 孩子兄弟表示法
雙親表示法
- 雙親表示法履肃，就是以雙親作為索引的關(guān)鍵詞的一種存儲(chǔ)方式
- 我們假設(shè)以一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中坐桩，附設(shè)一個(gè)指示其雙親結(jié)點(diǎn)在數(shù)組中位置的元素
-
也就是說(shuō)尺棋，每個(gè)結(jié)點(diǎn)除了知道自己是誰(shuí)之外，還知道它的雙親在哪里
雙親表示法
定義:
// 樹(shù)的雙親表示法結(jié)點(diǎn)結(jié)構(gòu)定義
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode
{
ElemType data; // 結(jié)點(diǎn)數(shù)據(jù)
int parent; // 雙親位置(下標(biāo))
}PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE];
int r; // 根的位置(下標(biāo))
int n; // 結(jié)點(diǎn)數(shù)目
}PTree;
雙親表示法這樣的存儲(chǔ)結(jié)構(gòu)绵跷，我們可以根據(jù)某結(jié)點(diǎn)的parent指針找到它的雙親結(jié)點(diǎn)膘螟，所用的時(shí)間復(fù)雜度為O(1),索引到parent位-1時(shí)，表示找到了樹(shù)結(jié)點(diǎn)的根
缺點(diǎn)：
如果我們要知道某結(jié)點(diǎn)的孩子是什么碾局，只能遍歷整個(gè)樹(shù)結(jié)構(gòu)
那我們對(duì)這個(gè)結(jié)構(gòu)做如下改進(jìn)荆残，每個(gè)結(jié)點(diǎn)添加孩子的下標(biāo)：
雙親表示法-孩子
如果我們又比較關(guān)心它們兄弟之間的關(guān)系呢？那么結(jié)構(gòu)可以改為這樣
雙親表示法-兄弟
孩子表示法
由于樹(shù)中每個(gè)結(jié)點(diǎn)可能有多棵子樹(shù)净当，可以考慮用多重鏈表來(lái)實(shí)現(xiàn)内斯，這就有了如下的表示法：
樹(shù)
孩子表示法
如圖所示，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)自身的值與索引外像啼，還增加了一個(gè)指針俘闯，指向子樹(shù)的左子樹(shù)，左子樹(shù)依次指向右子樹(shù)埋合，這樣备徐，不管是孩子還是兄弟的查找都變得很容易了
雙親孩子表示法
在孩子表示法中，只找到孩子還不夠完善甚颂，我們合并之前的雙親表示法蜜猾，就得到了雙親孩子表示法：
雙親孩子表示法
