順序存儲結構，用一段地址連續的存儲單元依次存儲線性表的數據元素。存儲的元素之間是一對一的關系，但是在樹形結構中元素之間是一對多的關系。

樹中某個結點的孩子可以有多個，則無論按何種順序将樹中所有結點存儲到數組中，結點的存儲位置都無法直接反映邏輯關系。簡單說就是我們單純地按照數組存儲，我們将無法知道每個元素的雙親、孩子節點是誰。所以單純的順序存儲結構是不能滿足樹的實現要求的。

不過我們可以利用順序存儲和鍊式存儲結構的特點，完全可以實現對樹的存儲結構的表示。我們這裡要介紹三種不同的表示法：雙親表示法 、孩子表示法、孩子兄弟表示法。

樹的存儲結構

樹形結構，除了根結點外，其餘每個結點，它不一定有孩子，但是一定有且僅有一個雙親親。我們假設以一組連續空間存儲樹的結點，同時在每個結點中設置一個指示器，指示其雙親結點到鍊表中的位置。也就是說每個節點除了知道自己是誰以外，還必須知道它的雙親是誰。

雙親表示法

Data是該節點的數據域；parent 是該節點指向雙親節點的指針域；

class Node<T>{ //數據 T data; //雙親節點的下标 int parent; } class Tree{ //數組的大小 int max_size=10; //數組容器 Node [] nodes=new Node[max_size]; //根節點的下标 int root; }

有了結構的定義，我們就可以來實現雙親表示法了。由于根結點是沒有雙親，所以我們約定根結點的位置域設置為-1，這也就意味着，我們所有的結點都存有雙親的位置。

雙親表示法

這樣的存儲結構，我們可以根據結點的 parent 指針很容易找到他的雙親結點，所用的時間複雜度為 0(1)，直到 parent等于-1時，表示找到了樹結點的根。但是我們要知道結點的孩子是誰，我們隻能遍曆整個數組才行。我們可以增加指向左孩子的指針域，或者增加指向右孩子的指針域。如下圖雙親表示法增加左孩子節點的指針

雙親表示法增加左孩子節點

孩子表示法就是先用數組存儲每個節點，然後用單鍊表把每個節點的子節點串聯起來。會編程的小夥伴都知道 Map 的數據結構。樹的孩子表示法非常類似于 Map 的數據結構。

節點的存儲結果

其中Data是數據域，存儲某節點的數據信息。 FirstChild是頭指針域，存儲該結點的孩子鍊表的頭指針。

孩子節點的結構

child是數據域，存儲某個結點在表頭數組中的下标。next是指針域，用來存儲某結點的下一個孩子結點的指針。

孩子表示法

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

孩子兄弟表示法

data是數據域，firstchild為指針域，存儲第一個孩子結點的地址，rightsib是指針域，存儲該結點的右兄弟的地址。

孩子兄弟表示法

這種方法給查找某結點的某個孩子帶來了方便，隻需要通過firstchild 找到此結點的左兒子，然後再通過左兒子找到二弟，一直下去，直到找到具體的孩子。當然，如果想要找到雙親，完全可以增加一個parent 指針域來解決。參考《大話數據結構》 #以書之名#

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!