二叉樹的存儲結構
二叉樹的存儲可分為兩種：順序存儲結構和鏈式存儲結構。
1.順序存儲結構
把一個滿二叉樹自上而下、從左到右順序編號，依次存放在數組內，可得到圖6.8(a)所示的結果。設滿二叉樹結點在數組中的索引號為i，那麼有如下性質。
（1）如果i = 0，此結點為根結點，無雙親。
（2）如果i > 0，則其雙親結點為(i -1) / 2 。（注意，這裡的除法是整除，結果中的小數部分會被捨棄。）
（3）結點i的左孩子為2i + 1，右孩子為2i + 2。
（4）如果i > 0，當i為奇數時，它是雙親結點的左孩子，它的兄弟為i + 1；當i為偶數時，它是雙新結點的右孩子，它的兄弟結點為i – 1。
（5）深度為k的滿二叉樹需要長度為2 k-1的數組進行存儲。
通過以上性質可知，使用數組存放滿二叉樹的各結點非常方便，可以根據一個結點的索引號很容易地推算出它的雙親、孩子、兄弟等結點的編號，從而對這些結點進行訪問，這是一種存儲二叉滿二叉樹或完全二叉樹的最簡單、最省空間的做法。
為了用結點在數組中的位置反映出結點之間的邏輯關系，存儲一般二叉樹時，只需要將數組中空結點所對應的位置設為空即可，其效果如圖6.8(b)所示。這會造成一定的空間浪費，但如果空結點的數量不是很多，這些浪費可以忽略。
一個深度為k的二叉樹需要2 k-1個存儲空間，當k值很大並且二叉樹的空結點很多時，最壞的情況是每層只有一個結點，再使用順序存儲結構來存儲顯然會造成極大地浪費，這時就應該使用鏈式存儲結構來存儲二叉樹中的數據。
1.鏈式存儲結構
二叉樹的鏈式存儲結構可分為二叉鏈表和三叉鏈表。二叉鏈表中，每個結點除了存儲本身的數據外，還應該設置兩個指針域left和right，它們分別指向左孩子和右孩子（如圖6.9(a)所示）。
當需要在二叉樹中經常尋找某結點的雙親，每個結點還可以加一個指向雙親的指針域parent，如圖6.9(b)所示，這就是三叉鏈表。
圖6.10所示的是二叉鏈表和三叉鏈表的存儲結構，其中虛線箭頭表示parent指針所指方向。
二叉樹還有一種叫雙親鏈表的存儲結構，它只存儲結點的雙親信息而不存儲孩子信息，由於二叉樹是一種有序樹，一個結點的兩個孩子有左右之分，因此結點中除了存放雙新信息外，還必須指明這個結點是左孩子還是右孩子。由於結點不存放孩子信息，無法通過頭指針出發遍歷所有結點，因此需要借助數組來存放結點信息。圖6.10(a)所示的二叉樹使用雙親鏈表進行存儲將得到圖6.11所示的結果。由於根節點沒有雙新，所以它的parent指針的值設為-1。
雙親鏈表中元素存放的順序是根據結點的添加順序來決定的，也就是說把各個元素的存放位置進行調換不會影響結點的邏輯結構。由圖6.11可知，雙親鏈表在物理上是一種順序存儲結構。
二叉樹存在多種存儲結構，選用何種方法進行存儲主要依賴於對二叉樹進行什麼操作來確定。而二叉鏈表是二叉樹最常用的存儲結構，下面幾節給出的有關二叉樹的算法大多基於二叉鏈表存儲結構。
