全國(guó)計(jì)算機(jī)等級(jí)考試四級(jí)復(fù)習(xí)綱要二

6.樹(shù)

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

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

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

　�。�2）孩子兄弟鏈表表示法

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

　　值得注意的是，孩子兄弟鏈表的結(jié)構(gòu)形式與二叉鏈表完全相同;但存儲(chǔ)結(jié)點(diǎn)中指針的含義不同。二叉鏈表中存儲(chǔ)結(jié)點(diǎn)的左、右指針?lè)謩e指向左、右孩子;而孩子兄弟鏈表中存儲(chǔ)結(jié)點(diǎn)的兩個(gè)指針?lè)謩e指向“長(zhǎng)子”和“大弟”。

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

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

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

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

　　7.樹(shù)的遍歷

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

　　（1）先根遍歷若樹(shù)非空，則

　�、僭L問(wèn)根結(jié)點(diǎn);

　�、谝来蜗雀�遍歷根的各個(gè)子樹(shù)T 1 ，…，T m 。

　�。�2）后根遍歷若樹(shù)非空，則

　�、僖来蜗雀�遍歷根的各個(gè)子樹(shù)T 1 ，…，T m 。②訪問(wèn)根結(jié)點(diǎn);

　�。�3）層次遍歷

　�、偃魳�(shù)非空，訪問(wèn)根結(jié)點(diǎn);
　　
　　②若第1，…，i（i≥1）層結(jié)點(diǎn)已被訪問(wèn)，且第i+1層結(jié)點(diǎn)未訪問(wèn)，則從左到右依次訪問(wèn)第i+1層結(jié)點(diǎn)。

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

　�、偌泳�:在兄弟結(jié)點(diǎn)直接加一虛線;
　　
　�、谀ň�:對(duì)每個(gè)結(jié)點(diǎn)，除了其最左的一個(gè)孩子外，抹去該結(jié)點(diǎn)原來(lái)與其余孩子之間的邊線;

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

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

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

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

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

　�、偕�林第一棵樹(shù)的根就是二叉樹(shù)的根;

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

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

更多信息請(qǐng)?jiān)L問(wèn)：考試吧計(jì)算機(jī)等級(jí)考試欄目