(2)二叉樹的順序存儲結構

　　二叉樹的順序存儲結構由一個一維數組構成，二叉樹上的結點按某種次序分別存入該數組的各個單元。顯然，這里的關鍵在于結點的存儲次序，這種次序應能反映結點之間的邏輯關系(父子關系)，否則二叉樹的基本運算就難以實現。

　　由二叉樹的性質5可知，若對任一完全二叉樹上的所有結點按層編號，則結點編號之間的數值關系可以準確地反映結點之間的邏輯關系。因此，對于任何完全二叉樹來說，可以采用“以編號為地址”的策略將結點存入作為順序存儲結構的一維數組。具體地說就是:將編號為i的結點存入一維數組的第i個單元。

　　在這一存儲結構中，由于一結點的存儲位置(即下標)也就是它的編號，故結點間的邏輯關系可通過它們下標間的數值關系確定。

　　(3)雙親表示法

　　樹上每個結點的孩子可以有任意多個，但雙親只有一個。因此，通過指向雙親的指針而將樹中所有結點組織在一起形成一種存儲結構是十分簡法的。樹的這種存儲表示方法稱為雙親表示法。在雙親表示法下，每個存儲結點由兩個域組成:數據域———用于存儲樹上結點中的數據元素;“指針”域———用于指示本結點之雙親所在的存儲結點。值得注意的是，“指針”域的類型定義可以有兩種選擇。第一種是將其定義為高級語言(如C語句)中的指針類型。通過將存儲結點中的指針域定義為高級語言中的指針類型，就得到各種鏈式存儲結構，如單鏈表、二叉鏈表、孩子鏈表等等。第二種選擇是將“指針”域定義為整型、子界型等型。嚴格地說，無論選擇上述哪種定義，得到的都是鏈式存儲結構，因為在這兩種定義之下，各存儲結點之間的聯結是通過“指針”完成的，而且這些指針反映了結點之間的邏輯關系。

　　為了區別這兩種鏈式結構，通常將指針域定義為高級語言中的指針類型的各種鏈式存儲結構(如單鏈表、二叉鏈表等等)稱為“動態鏈表”，相應的指針稱為“動態指針”;將指針域定義為整型、子界型等類型的各種鍵式存儲結構稱為“靜態鏈表”，相應的“指針”稱為:“靜態指針”。動態鏈表中的結點是通過高級語言中的標準過程例如C語言的庫函數malloc(size)動態(即運行期間)生成的(動態鏈表由此得名)，無需事先規定鏈表的容量，因此動態鏈表的大小是動態變化的。相反，靜態鏈有的容量必須事先說明，因而其大小是固定的。然而，在某些情況下，特別是當結點數固定不變且可事先確定時，采用靜態鏈表往往更加方便、直觀。

　　靜態雙親鏈表由一個一維數組樹成。數組的每個分量包含兩個域:數據域和雙親域。數據域用于存儲樹上一個結點中的數據元素;雙親域用于存放本結點的雙親結點在數組中的序號(下標值)。