【正文】 因此就必須把多維結(jié)構(gòu)映射為一維的結(jié)構(gòu)，即把多維結(jié)構(gòu)按一定次序排列成一維的。　　四、樹型結(jié)構(gòu)　　線性表、棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)所表達(dá)和處理的數(shù)據(jù)以線性結(jié)構(gòu)為組織形式。然而，在計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的各個(gè)領(lǐng)域中，存在著大量需要用更復(fù)雜的邏輯結(jié)構(gòu)加以表示的問(wèn)題。因此必須研究更復(fù)雜的邏輯結(jié)構(gòu)及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。樹形結(jié)構(gòu)就是這些更復(fù)雜的結(jié)構(gòu)中最重要的一類。　　　　樹是一類重要的樹形結(jié)構(gòu)，其定義如下:樹是n(n0)個(gè)結(jié)點(diǎn)的有窮集合，滿足:　　(1)有且僅有一個(gè)稱為根的結(jié)點(diǎn)?！　?2)其余結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的非空集合，T 1 ，T 2 ，…，T m ，這些集合中的每一個(gè)都是一棵樹，稱為根的子樹?！　≡跇渖希Y(jié)點(diǎn)沒有直接前趨。對(duì)樹上任一結(jié)點(diǎn)X來(lái)說(shuō)，X是它的任一子樹的根結(jié)點(diǎn)惟一的直接前趨。為了討論方便，我們引入樹的若干習(xí)慣術(shù)語(yǔ)。樹上任一結(jié)點(diǎn)所擁有的子樹的數(shù)目稱為該結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支點(diǎn)。一棵樹中所有結(jié)點(diǎn)的度的最大值稱為該樹的度。若樹中結(jié)點(diǎn)A是結(jié)點(diǎn)B的直接前趨，則稱A為B的雙親或父結(jié)點(diǎn)，稱B為A的孩子(即“子女”)或子結(jié)點(diǎn)。易知任何結(jié)點(diǎn)A的孩子B也就是A的一棵子樹的根結(jié)點(diǎn)，父結(jié)點(diǎn)相同的結(jié)點(diǎn)互稱為兄弟。一棵樹上的任何結(jié)點(diǎn)(不包括根本身)稱為根的子孫。反之若B是A的子孫，則稱A是B的祖先，結(jié)點(diǎn)的層數(shù)(或深度)從根開始算起:根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。一棵樹中所有結(jié)點(diǎn)層數(shù)的最大值稱為該樹的高度或深度?！　?及一切樹形結(jié)構(gòu))是一種“分支層次”結(jié)構(gòu)。所謂“分支”是指樹中任一結(jié)點(diǎn)的子孫可以按它們所在的子樹的不同而劃分成不同的“分支”。所謂“層次”是指樹上所有結(jié)點(diǎn)可以按它們的層數(shù)劃分不同的“層次”。在實(shí)際應(yīng)用中，樹中的一個(gè)結(jié)點(diǎn)可用來(lái)存儲(chǔ)實(shí)際問(wèn)題中的一個(gè)數(shù)據(jù)元素，而結(jié)點(diǎn)間的邏輯關(guān)系(即父結(jié)點(diǎn)與子結(jié)點(diǎn)之間的鄰接關(guān)系)往往用來(lái)表示數(shù)據(jù)元素之間的某種重要的、必須加以表達(dá)的關(guān)系?！　∮脠D示法表示任何樹形結(jié)構(gòu)時(shí)，箭頭的方向總是從上到下，即從父結(jié)點(diǎn)指向子結(jié)點(diǎn)，因此，可以簡(jiǎn)單地用連線代替箭頭?！　?　?、偾蟾鵕OOT(T)，引用型運(yùn)算，其結(jié)果是結(jié)點(diǎn)X在樹T的根結(jié)點(diǎn)?！　、谇箅p親PARENT(T，X)，引用型運(yùn)算，其結(jié)果是結(jié)點(diǎn)X在樹T上的雙親結(jié)點(diǎn)。若X是樹T的根或X不在T上，則結(jié)果為一特殊標(biāo)志?！　、矍蠛⒆覥HILD(T，X，i)，引用型運(yùn)算，其結(jié)果是樹T上的結(jié)點(diǎn)X的第i個(gè)孩子。若X不在T上或X沒有第i個(gè)孩子，則結(jié)果為一特殊標(biāo)志?！　、芙銫REATE(X，T 1 ，…，T k )k≥1，加工型運(yùn)算，其作用是建立一棵以X為根，以T 1 ，…，T k 為第1，…k棵子樹的樹?！　、菁糁ELETE(T，X，i)，加工型運(yùn)算，其作用是刪除樹T上結(jié)點(diǎn)X的第i棵子樹。若T無(wú)第i棵子樹，則為空操作?！　　　?1)二叉樹的基本概念　　二叉樹是結(jié)點(diǎn)的有窮集合，它或者是空集，或者同時(shí)滿足下述兩個(gè)條件:(1)有且僅有一個(gè)稱為根的結(jié)點(diǎn):　　(2)其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合T 1 、T 2 ，T 1 與T 2 都是二叉樹，并且T 1 與T 2 有順序關(guān)系(T 1 在T 2 之前)，它們分別稱為根的左子樹和右子樹?！　《鏄涫且活惻c樹不同的樹形結(jié)構(gòu)。它們的區(qū)別是:第一，二叉樹可以是空集，這種二叉樹稱為空二叉樹。第二，二叉樹的任一結(jié)點(diǎn)都有兩棵子樹(當(dāng)然，它們中的任何一個(gè)可以是空子樹)，并且這兩棵子樹之間有次序關(guān)系，也就是說(shuō)，它們的位置不能交換。相應(yīng)地，二叉樹上任一結(jié)點(diǎn)左、右子樹的根分別稱為該結(jié)點(diǎn)的左孩子和右孩子。另外，二叉樹上任一結(jié)點(diǎn)的度定義為該結(jié)點(diǎn)的孩子數(shù)(即非空子樹數(shù))。除這個(gè)幾個(gè)術(shù)語(yǔ)之外，樹的其它術(shù)語(yǔ)也適用于二叉樹?！　√貏e值得注意的是，由于二叉樹上任一結(jié)點(diǎn)的子樹有左、右之分，因此即使一結(jié)點(diǎn)只有一棵非空子樹，仍須區(qū)別它是該結(jié)點(diǎn)的左子樹還是右子樹，這是與樹不同的?！　?2)二叉樹的性質(zhì)　　在某些情況下，了解二叉樹的下列性質(zhì)是有幫助的?！　　　《鏄渫ǔＳ袃深惔鎯?chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！　?1)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　　二叉樹有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是二叉樹鏈表與三叉鏈表?！　∑渲?，data域稱為數(shù)據(jù)域，用于存儲(chǔ)二叉樹結(jié)點(diǎn)中的數(shù)據(jù)元素。lchild域稱為左孩子指針域，用于存放指向本結(jié)點(diǎn)左孩子的指針(這個(gè)指針及指針域有時(shí)簡(jiǎn)稱為左指針)。類似地，rchild域稱為右孩子指針域，用于存放指向本結(jié)點(diǎn)右孩子的指針(簡(jiǎn)稱右指針)。二叉鏈表中的所有存儲(chǔ)結(jié)點(diǎn)通過(guò)它們的左、右指針的鏈接而形成一個(gè)整體。此外，每個(gè)二叉鏈表還必須有一個(gè)指向根結(jié)點(diǎn)的指針，該指針?lè)Q為根指針。根指針具有標(biāo)識(shí)二叉鏈表的作用，對(duì)二叉鏈表的訪問(wèn)只能從根指針開始。值得注意的是，二叉鏈表中每個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是指向該結(jié)點(diǎn)的一個(gè)孩子的指針，或者是空指針NULL。　　若二叉樹為空，則root=NULL。若某結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。具有n個(gè)結(jié)點(diǎn)的二叉樹中，一共有2n個(gè)指針域，其中只有n1個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的n+1個(gè)指針域?yàn)镹ULL?！　《鏄涞逆?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作方便，表達(dá)簡(jiǎn)明(二叉樹的邏輯關(guān)系———結(jié)點(diǎn)間的父子關(guān)系———在二叉鏈表和三叉鏈表中被直接表達(dá)成對(duì)應(yīng)存儲(chǔ)結(jié)點(diǎn)之間的指針)，因而成為二叉樹最常用的存儲(chǔ)結(jié)構(gòu)。然而在某些情況下，二叉樹的順序存儲(chǔ)結(jié)構(gòu)也很有用?！　?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可知，若對(duì)任一完全二叉樹上的所有結(jié)點(diǎn)按層編號(hào)，則結(jié)點(diǎn)編號(hào)之間的數(shù)值關(guān)系可以準(zhǔn)確地反映結(jié)點(diǎn)之間的邏輯關(guān)系。因此，對(duì)于任何完全二叉樹來(lái)說(shuō)，可以采用“以編號(hào)為地址”的策略將結(jié)點(diǎn)存入作為順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組。具體地說(shuō)就是:將編號(hào)為i的結(jié)點(diǎn)存入一維數(shù)組的第i個(gè)單元?！　≡谶@一存儲(chǔ)結(jié)構(gòu)中，由于一結(jié)點(diǎn)的存儲(chǔ)位置(即下標(biāo))也就是它的編號(hào)，故結(jié)點(diǎn)間的邏輯關(guān)系可通過(guò)它們下標(biāo)間的數(shù)值關(guān)系確定?！　　　∮捎诙鏄涞幕具\(yùn)算在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)比較簡(jiǎn)單，無(wú)需詳加討論。下面研究二叉樹的一種較為復(fù)雜的重要運(yùn)算———遍歷及其在二叉鏈表上的實(shí)現(xiàn)?！　”闅v一棵二叉樹就是按某種次序系統(tǒng)地“訪問(wèn)”二叉樹上的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被“訪問(wèn)”一次。所謂“訪問(wèn)”一個(gè)結(jié)點(diǎn)，是指對(duì)該結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行某種處理，處理的內(nèi)容依具體問(wèn)題而定，通常比較簡(jiǎn)單。遍歷運(yùn)算的關(guān)鍵在于訪問(wèn)結(jié)點(diǎn)的“次序”，這種次序應(yīng)保證二叉樹上的每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次且僅一次?！　∮啥x可知，一棵二叉樹由三部分組成:根、左子樹和右子樹。因此對(duì)二叉樹的遍歷也可相應(yīng)地分解成三項(xiàng)“子任務(wù)”:　?、僭L問(wèn)根根點(diǎn)?！　、诒闅v左子樹(即依次訪問(wèn)左子樹上的全部結(jié)點(diǎn))。③遍歷右子樹(即依次訪問(wèn)右子樹上的全部結(jié)點(diǎn))?！　∫?yàn)樽?、右子樹都是二叉?可以是空二叉樹)，對(duì)它們的遍歷可以按上述方法繼續(xù)分解，直到每棵子樹均為空二叉樹為止。由此可見，上述三項(xiàng)子任務(wù)之間的次序決定了遍歷的次序。若以D、L、R分別表示這三項(xiàng)子任務(wù)，則人有六種可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任務(wù)②在子任務(wù)③之前完成，這樣就只剩下前三種次序，按這三種次序進(jìn)行的遍歷分別稱為先根遍歷(或前序遍歷)、中根(或中序)遍歷、后根(或后序)遍歷。三種遍歷方法的定義如下:　　先根遍歷 若需遍歷的二叉樹為空，執(zhí)行空操作。否則，依次執(zhí)行下列操作:　?、僭L問(wèn)根結(jié)點(diǎn)?！　、谙雀闅v左子樹。　?、巯雀闅v右子樹?！　≈懈闅v 若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操作:　　①中根遍歷左子樹。②訪問(wèn)根結(jié)點(diǎn)。③中根遍右子樹?！　『蟾闅v 若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操作:　?、俸蟾闅v左子樹。②后根遍歷右子樹。③訪問(wèn)根結(jié)點(diǎn)?！　★@然，上述三種遍歷方法的區(qū)別在于執(zhí)行子任務(wù)“訪問(wèn)根結(jié)點(diǎn)”的“時(shí)機(jī)”不同。最先(最后、在中間)執(zhí)行此子任務(wù)，則為先根(后根、中根)遍歷?！　“茨撤N遍歷方法遍歷一棵二叉樹，將得到該二叉樹上所有結(jié)點(diǎn)的訪問(wèn)序列?！　　　涫且环N常用的數(shù)據(jù)結(jié)構(gòu)。為了適應(yīng)各種應(yīng)用問(wèn)題的需要，多種不同的存儲(chǔ)結(jié)構(gòu)也相應(yīng)地建立起來(lái)。下面介紹樹的三種常用存儲(chǔ)結(jié)構(gòu)?！　?1)孩子鏈表表示法　　孩子鏈表表示法是樹的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與二叉樹的二叉鏈表存儲(chǔ)方法類似，孩子鏈表表示法的基本思想是:樹上的一個(gè)結(jié)點(diǎn)的內(nèi)容(數(shù)據(jù)元素)以及指向該結(jié)點(diǎn)所有孩子的指針存儲(chǔ)在一起以便于運(yùn)算的實(shí)現(xiàn)。由于樹上的結(jié)點(diǎn)的度(孩子數(shù))沒有限制，而且各個(gè)結(jié)點(diǎn)的度可能相差很大，一種自然的表示方法是為樹上的每個(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ǔ)樹上的結(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ù)據(jù)結(jié)構(gòu)的大多數(shù)運(yùn)算?！　?3)雙親表示法　　樹上每個(gè)結(jié)點(diǎn)的孩子可以有任意多個(gè)，但雙親只有一個(gè)。因此，通過(guò)指向雙親的指針而將樹中所有結(jié)點(diǎn)組織在一起形成一種存儲(chǔ)結(jié)構(gòu)是十分簡(jiǎn)法的。樹的這種存儲(chǔ)表示方法稱為雙親表示法。在雙親表示法下，每個(gè)存儲(chǔ)結(jié)點(diǎn)由兩個(gè)域組成:數(shù)據(jù)域———用于存儲(chǔ)樹上結(jié)點(diǎn)中的數(shù)據(jù)元素?！爸羔槨庇颉糜谥甘颈窘Y(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)鏈表往往更加方便、直觀?！　§o態(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ù)組中的序號(hào)(下標(biāo)值)?！　　　∨c二叉樹類似，遍歷是樹的一種重要運(yùn)算。樹的主要遍歷方法有以下三種?！　?1)先根遍歷若樹非空，則　?、僭L問(wèn)根結(jié)點(diǎn)?！　、谝来蜗雀闅v根的各個(gè)子樹T 1 ，…，T m 。　　(2)后根遍歷若樹非空，則　　①依次先根遍歷根的各個(gè)子樹T 1 ，…，T m 。②訪問(wèn)根結(jié)點(diǎn)?！　?3)層次遍歷　　①若樹非空，訪問(wèn)根結(jié)點(diǎn)?！　、谌舻?，…，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)一致?！　　　∫话銟滢D(zhuǎn)換為二叉樹的基本思想是:將樹中每個(gè)結(jié)點(diǎn)用兩個(gè)鏈接表示就可以了，一個(gè)指向它最左邊的孩子，另一個(gè)指向它右邊的一個(gè)兄弟，從圖形上看，具體步驟是:　?、偌泳€:在兄弟結(jié)點(diǎn)直接加一虛線?！　、谀ň€:對(duì)每個(gè)結(jié)點(diǎn)，除了其最左的一個(gè)孩子外，抹去該結(jié)點(diǎn)原來(lái)與其余孩子之間的邊線?！　、坌D(zhuǎn):將新加上的虛線改為實(shí)線，并將虛線以及有關(guān)的實(shí)線順時(shí)鐘旋轉(zhuǎn)45度?！　《鏄溥€原為一般樹的步驟是:　　①加線:若某結(jié)點(diǎn)是一父結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)的右孩子以及沿著右鏈搜索到的所有右孩子結(jié)點(diǎn)都用線與那個(gè)父結(jié)點(diǎn)連接起來(lái)?！　、谀ň€:抹去原二叉樹中所有結(jié)點(diǎn)與其右孩子的連線?！　、坌D(zhuǎn):將虛線及有關(guān)實(shí)線逆時(shí)鐘旋轉(zhuǎn)約45度，并將幾個(gè)結(jié)點(diǎn)按層次排列?！　　　∩洲D(zhuǎn)換為二叉樹的步驟是:　?、賹⑸种械拿靠脴滢D(zhuǎn)換為二叉樹?！　、谏种械谝豢脴涞母Y(jié)點(diǎn)就是轉(zhuǎn)換后二叉樹的根結(jié)點(diǎn)，依次將后一棵樹作為前一棵樹根結(jié)點(diǎn)的右子樹?！　《鏄滢D(zhuǎn)換為森林的步驟是:　　①森林第一棵樹的根就是二叉樹的根。　?、诙鏄涞淖笞訕滢D(zhuǎn)換為森林的第一棵樹，二叉樹的右子樹對(duì)應(yīng)于森林中其余的樹。③二叉樹右子樹的根結(jié)點(diǎn)作為余下樹中第一棵樹的根結(jié)點(diǎn)……，以此類推?！　∥濉D　　圖的概念　　圖是一種較線性表和樹形結(jié)構(gòu)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中每個(gè)數(shù)據(jù)元素只有一個(gè)(直接)前驅(qū)和后繼，即各數(shù)據(jù)元素之間僅有線性關(guān)系。在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有明顯的層次關(guān)系，每一層中的數(shù)據(jù)元素只和上一層中的一個(gè)元素(即雙親結(jié)點(diǎn))相關(guān)。而在圖中，任意兩個(gè)數(shù)據(jù)元素之間均有可能相關(guān)?！　D(graph)是圖型結(jié)構(gòu)的簡(jiǎn)稱。它是一種復(fù)雜的非線性數(shù)