樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹中的某個結點的孩子可以有多個，所以僅僅使用簡單的順序結構或者鏈式結構是不能完全表示一整棵樹的。充分利用順序存儲結構和鏈式存儲結構的特點，完全可以實現對樹的存儲結構的表示。

樹的存儲結構可以分為3種：雙親表示法，孩子表示法和孩子兄弟表示法

1.雙親表示法

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

根節(jié)點沒有雙親，所以其在數組中存儲的值為-1。

其余的節(jié)點，只需要存儲其父節(jié)點對應的數組下標即可。

代碼解釋：

// 雙親表示法#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.孩子表示法

將每個節(jié)點的孩子節(jié)點都用單鏈表連接起來形成一個線性結構，n個節(jié)點具有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.孩子兄弟表示法

以二鏈表作為樹的存儲結構，又稱二叉樹表示法。任意一棵樹，他的結點的第一個孩子如果存在就是唯一結點，他的右兄弟如果存在，也是唯一的，因此，我們設置兩個指針，分別指向該結點的第一個孩子和該結點的右兄弟。

使用孩子兄弟表示法需要將樹轉換為二叉樹。

轉換前：

轉換后：

代碼解釋：

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

以上就是3種樹的存儲結構，順序結構或者鏈式結構只能表示一棵樹的部分結構，只有結合雙親表示法，孩子表示法和孩子兄弟表示法才能完整的表示出一顆樹的結構。對于樹的順序結構和者鏈式結構在本站的數據結構和算法教程中有更加詳細的講解，感興趣的小伙伴不要錯過哦。