樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹中的某個(gè)結(jié)點(diǎn)的孩子可以有多個(gè)，所以僅僅使用簡(jiǎn)單的順序結(jié)構(gòu)或者鏈?zhǔn)浇Y(jié)構(gòu)是不能完全表示一整棵樹的。充分利用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，完全可以實(shí)現(xiàn)對(duì)樹的存儲(chǔ)結(jié)構(gòu)的表示。

樹的存儲(chǔ)結(jié)構(gòu)可以分為3種：雙親表示法，孩子表示法和孩子兄弟表示法

1.雙親表示法

采用的一組連續(xù)的存儲(chǔ)空間來存儲(chǔ)每個(gè)節(jié)點(diǎn)。以雙親作為索引的關(guān)鍵詞的一種存儲(chǔ)方式。每個(gè)結(jié)點(diǎn)只有一個(gè)雙親，所以選擇順序存儲(chǔ)占主要。

根節(jié)點(diǎn)沒有雙親，所以其在數(shù)組中存儲(chǔ)的值為-1。

其余的節(jié)點(diǎn)，只需要存儲(chǔ)其父節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)即可。

代碼解釋：

// 雙親表示法#define MAX_SIZE 100typedef?int?ElemType;
typedef?struct?PTNode{
????ElemType?data;
????int?parent;}PTNode;
typedef?struct?PTree{
????PTNode?nodes[MAX_SIZE];
????int?n;}PTree;

 2.孩子表示法

將每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)都用單鏈表連接起來形成一個(gè)線性結(jié)構(gòu)，n個(gè)節(jié)點(diǎn)具有n個(gè)孩子鏈表。由于每個(gè)結(jié)點(diǎn)可有多個(gè)子樹（無法確定子樹個(gè)數(shù)），可以考慮使用多重鏈表來實(shí)現(xiàn)。

代碼解釋：

// 孩子表示法typedef?int?ElemType;#define MAX_SIZE 100typedef?struct?CNode{
????int?child;
????struct?CNode?*next;}CNode;
typedef?struct?PNode{
????ElemType?data;
????struct?CNode?*child;}PNode;
typedef?struct?CTree{
????PNode?nodes[MAX_SIZE];
????int?n;}CTree;

3.孩子兄弟表示法

以二鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，又稱二叉樹表示法。任意一棵樹，他的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一結(jié)點(diǎn)，他的右兄弟如果存在，也是唯一的，因此，我們?cè)O(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和該結(jié)點(diǎn)的右兄弟。

使用孩子兄弟表示法需要將樹轉(zhuǎn)換為二叉樹。

轉(zhuǎn)換前：

轉(zhuǎn)換后：

代碼解釋：

typedef?int?ElemType;typedef?struct?Node{
????ElemType?data;
????struct?Node?*FirstChild;
????struct?Node?*NextBrother;
????}Node,TREE;

以上就是3種樹的存儲(chǔ)結(jié)構(gòu)，順序結(jié)構(gòu)或者鏈?zhǔn)浇Y(jié)構(gòu)只能表示一棵樹的部分結(jié)構(gòu)，只有結(jié)合雙親表示法，孩子表示法和孩子兄弟表示法才能完整的表示出一顆樹的結(jié)構(gòu)。對(duì)于樹的順序結(jié)構(gòu)和者鏈?zhǔn)浇Y(jié)構(gòu)在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中有更加詳細(xì)的講解，感興趣的小伙伴不要錯(cuò)過哦。