(2)二叉樹的順序存儲(chǔ)結(jié)構(gòu)

　　二叉樹的順序存儲(chǔ)結(jié)構(gòu)由一個(gè)一維數(shù)組構(gòu)成，二叉樹上的結(jié)點(diǎn)按某種次序分別存入該數(shù)組的各個(gè)單元。顯然，這里的關(guān)鍵在于結(jié)點(diǎn)的存儲(chǔ)次序，這種次序應(yīng)能反映結(jié)點(diǎn)之間的邏輯關(guān)系(父子關(guān)系)，否則二叉樹的基本運(yùn)算就難以實(shí)現(xiàn)。

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

　　在這一存儲(chǔ)結(jié)構(gòu)中，由于一結(jié)點(diǎn)的存儲(chǔ)位置(即下標(biāo))也就是它的編號，故結(jié)點(diǎn)間的邏輯關(guān)系可通過它們下標(biāo)間的數(shù)值關(guān)系確定。

　　(3)雙親表示法

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

　　為了區(qū)別這兩種鏈?zhǔn)浇Y(jié)構(gòu)，通常將指針域定義為高級語言中的指針類型的各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(如單鏈表、二叉鏈表等等)稱為“動(dòng)態(tài)鏈表”，相應(yīng)的指針稱為“動(dòng)態(tài)指針”;將指針域定義為整型、子界型等類型的各種鍵式存儲(chǔ)結(jié)構(gòu)稱為“靜態(tài)鏈表”，相應(yīng)的“指針”稱為:“靜態(tài)指針”。動(dòng)態(tài)鏈表中的結(jié)點(diǎn)是通過高級語言中的標(biāo)準(zhǔn)過程例如C語言的庫函數(shù)malloc(size)動(dòng)態(tài)(即運(yùn)行期間)生成的(動(dòng)態(tài)鏈表由此得名)，無需事先規(guī)定鏈表的容量，因此動(dòng)態(tài)鏈表的大小是動(dòng)態(tài)變化的。相反，靜態(tài)鏈有的容量必須事先說明，因而其大小是固定的。然而，在某些情況下，特別是當(dāng)結(jié)點(diǎn)數(shù)固定不變且可事先確定時(shí)，采用靜態(tài)鏈表往往更加方便、直觀。

　　靜態(tài)雙親鏈表由一個(gè)一維數(shù)組樹成。數(shù)組的每個(gè)分量包含兩個(gè)域:數(shù)據(jù)域和雙親域。數(shù)據(jù)域用于存儲(chǔ)樹上一個(gè)結(jié)點(diǎn)中的數(shù)據(jù)元素;雙親域用于存放本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的序號(下標(biāo)值)。