6.樹

　　樹是一種常用的數(shù)據(jù)結(jié)構(gòu)。為了適應(yīng)各種應(yīng)用問題的需要，多種不同的存儲結(jié)構(gòu)也相應(yīng)地建立起來。下面介紹樹的三種常用存儲結(jié)構(gòu)。

　�。�1）孩子鏈表表示法

　　孩子鏈表表示法是樹的一種鏈式存儲結(jié)構(gòu)。與二叉樹的二叉鏈表存儲方法類似，孩子鏈表表示法的基本思想是:樹上的一個結(jié)點的內(nèi)容（數(shù)據(jù)元素）以及指向該結(jié)點所有孩子的指針存儲在一起以便于運算的實現(xiàn)。由于樹上的結(jié)點的度（孩子數(shù)）沒有限制，而且各個結(jié)點的度可能相差很大，一種自然的表示方法是為樹上的每個結(jié)點X建立一個“孩子鏈表”，以便存儲X中的數(shù)據(jù)元素和指向X的所有孩子的指針。一個孩子鏈表是一個帶頭結(jié)點的單鏈表，單鏈表的頭結(jié)點含兩個域:數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用于存儲結(jié)點X中的數(shù)據(jù)元素;指針域用于存儲指向該單鏈表中第一個表結(jié)點（首結(jié)點）的指針。為了檢索方便，所有頭結(jié)點組織成一個數(shù)組，稱為表頭數(shù)組。對每個結(jié)點X的孩子鏈表來說，其中的所有表結(jié)點也含兩個域，孩子域（即數(shù)據(jù)域）和指針域。第i個表結(jié)點的孩子域存儲X的第i個孩子在頭結(jié)點數(shù)組中的下標值。

　　（2）孩子兄弟鏈表表示法

　　孩子兄弟鏈表中所有存儲結(jié)點的形式相同，均含三個域:數(shù)據(jù)域———用于存儲樹上的結(jié)點中的數(shù)據(jù)元素;孩子域———用于存儲指向本結(jié)點第一個孩子的指針;兄弟域———用于存放指向本結(jié)點下一個兄弟的指針。

　　值得注意的是，孩子兄弟鏈表的結(jié)構(gòu)形式與二叉鏈表完全相同;但存儲結(jié)點中指針的含義不同。二叉鏈表中存儲結(jié)點的左、右指針分別指向左、右孩子;而孩子兄弟鏈表中存儲結(jié)點的兩個指針分別指向“長子”和“大弟”。

　　在孩子兄弟鏈表表示法中，結(jié)點形式統(tǒng)一，結(jié)點間的聯(lián)系比較簡捷。同時，在這種存儲結(jié)構(gòu)上容易實現(xiàn)樹數(shù)據(jù)結(jié)構(gòu)的大多數(shù)運算。

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

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

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

　　7.樹的遍歷

　　與二叉樹類似，遍歷是樹的一種重要運算。樹的主要遍歷方法有以下三種。

　　（1）先根遍歷若樹非空，則

　　①訪問根結(jié)點;

　　②依次先根遍歷根的各個子樹T 1 ，…，T m 。

　�。�2）后根遍歷若樹非空，則

　　①依次先根遍歷根的各個子樹T 1 ，…，T m 。②訪問根結(jié)點;

　　（3）層次遍歷

　�、偃魳浞强眨�訪問根結(jié)點;
　　
　�、谌舻�1，…，i（i≥1）層結(jié)點已被訪問，且第i+1層結(jié)點未訪問，則從左到右依次訪問第i+1層結(jié)點。

　　顯然，按層次遍歷所得的結(jié)點訪問序列中，各結(jié)點的序號與按層編號所得的編號一致。
　　　
　　8.樹與二叉樹之間的轉(zhuǎn)換
　　
　　一般樹轉(zhuǎn)換為二叉樹的基本思想是:將樹中每個結(jié)點用兩個鏈接表示就可以了，一個指向它最左邊的孩子，另一個指向它右邊的一個兄弟，從圖形上看，具體步驟是:

　　①加線:在兄弟結(jié)點直接加一虛線;
　　
　�、谀ň�:對每個結(jié)點，除了其最左的一個孩子外，抹去該結(jié)點原來與其余孩子之間的邊線;

　�、坌�轉(zhuǎn):將新加上的虛線改為實線，并將虛線以及有關(guān)的實線順時鐘旋轉(zhuǎn)45度。

　　二叉樹還原為一般樹的步驟是:
　　
　�、偌泳�:若某結(jié)點是一父結(jié)點的左孩子，則將該結(jié)點的右孩子以及沿著右鏈搜索到的所有右孩子結(jié)點都用線與那個父結(jié)點連接起來;
　　　
　�、谀ň�:抹去原二叉樹中所有結(jié)點與其右孩子的連線;

　�、坌�轉(zhuǎn):將虛線及有關(guān)實線逆時鐘旋轉(zhuǎn)約45度，并將幾個結(jié)點按層次排列。

　　9.二叉樹與森林之間的轉(zhuǎn)換

　　森林轉(zhuǎn)換為二叉樹的步驟是:
　　
　�、賹⑸�林中的每棵樹轉(zhuǎn)換為二叉樹;
　　
　　②森林中第一棵樹的根結(jié)點就是轉(zhuǎn)換后二叉樹的根結(jié)點，依次將后一棵樹作為前一棵樹根結(jié)點的右子樹。
　　
　　二叉樹轉(zhuǎn)換為森林的步驟是:

　�、偕�林第一棵樹的根就是二叉樹的根;

　�、诙�叉樹的左子樹轉(zhuǎn)換為森林的第一棵樹，二叉樹的右子樹對應(yīng)于森林中其余的樹;③二叉樹右子樹的根結(jié)點作為余下樹中第一棵樹的根結(jié)點……，以此類推。

希望與更多計算機等級考試的網(wǎng)友交流，請進入計算機等級考試論壇

更多信息請訪問：考試吧計算機等級考試欄目