淺談數據結構中樹的存儲結構

樹的基本定義我已經在前一篇手記中淺顯地講解了一下，既然定義的一棵樹，那

么我們應該使用什麼結構既能存儲樹中結點所包含的數據，又能存儲各節點之間的關係呢。根據順序存儲和鏈式存儲的不同特點，我們將用四種表示法：雙親表示法、孩子的多重鏈表表示法、孩子鏈表表示法、孩子兄弟表示法。

1、雙親表示法

在樹中除了根結點以外，其他結點都會僅有一個雙親結點。

將數組中的下標用於表示雙親結點的位置或者是左孩子或者右孩子或是由兄弟。當然，這樣的結構依賴於存儲的順序是採用的是層序遍歷。

2、孩子的多重鏈表表示法

這種表示方法分2種，一種是多重鏈表表示法，即用樹的度就表示一個節點指針域的個數，這樣很大程度上浪費了內存資源。第二種是孩子鏈表表示法，即一個節點的指針域的個數和其孩子的個數(該節點的度)相等。

3、孩子鏈表表示法

用多個單鏈表表示孩子，在同一個單鏈表中的孩子有著共同的雙親。

有孩子鏈表表示法衍生出來的雙親孩子表示法，既是將雙親表示法和孩子鏈表表示法相結合起來了，將孩子與雙親，雙親與孩子之間的關係展示出來，可以不用遍歷便可尋找孩子的雙親或者雙親的孩子。

4、孩子兄弟表示法

存儲區域分三塊，中間那塊存儲結點的數據，左邊指向該節點的第一個孩子，右邊指向該節點的右兄弟。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！