【文章內容簡介】 ，其定義如下：樹是 n(n0)個結點的有窮集合，滿足： (1)有且僅有一個稱為根的結點； (2)其余結點分為 m(m≥ 0)個互不相交的非空集合， T1， T2，…， Tm，這些集合中的每一個都是一棵樹，稱為根的子樹。在樹上，根結點沒有直接前趨。對樹上任一結點 X來說， X是它的任一子樹的根結點的惟一的直接前趨。為了討論方便，我們引入樹的若干習慣術語。樹上任一結點所擁有的子樹的數(shù)目稱為該結點的度。度為 0的結點稱為葉子或終端結點，度大于 0的結點稱為非終端結點或分支點。一棵樹中所有結點的度的最大值稱為該樹的度。若樹中結點 A是結點 B的直接前趨，則稱 A為 B的雙親或父結點，稱 B為 A的孩子 (即 “子女 ”)或子結點。易知任何結點 A的孩子 B也就是 A的一棵子樹的根結點，父結點相同的結點互稱為兄弟。一棵樹上的任何結點 (不包括根本身 )稱為根的子孫。反之若 B是 A的子孫，則稱 A是 B的祖先。結點的層數(shù) (或深度 )從根開始算起：根的層數(shù)為 1，其余結點的層數(shù)為其雙親的層數(shù)加 1。一棵樹中所有結點層數(shù)的最大值稱為該樹的高度或深度。樹 (及一切樹形結構 )是一種 “分支層次 ”結構。所謂 “分支 ”是指樹中任一結點的子孫可以按它們所在的子樹的不同而劃分成不同的“分支 ”；所謂 “層次 ”是指樹上所有結點可以按它們的層數(shù)劃分不同的 “層 次 ”。在實際應用中，樹中的一個結點可用來存儲實際問題中的一個數(shù)據(jù)元素，而結點間的邏輯關系 (即父結點與子結點之間的鄰接關系 )往往用來表示數(shù)據(jù)元素之間的某種重要的、必須加以表達的關系。用圖示法表示任何樹形結構時，箭頭的方向總是從上到下，即從父結點指向子結點，因此，可以簡單地用連線代替箭頭。 ： ①求根 ROOT(T)，引用型運算，其結果是結點 X在樹 T的根結點。 ②求雙親 PARENT(T， X)，引用型運算，其結果是結點 X在樹 T上的雙親結點；若 X是樹T的根或 X不在 T上，則結果為一特殊標志。 ③求孩子 CHILD(T， X， i)，引用型運算，其結果是樹 T上的結點 X的第 i個孩子；若 X不在 T上或 X沒有第 i個孩子，則結果為一特殊標志。 ④建樹 CREATE(X， T1，…， Tk)， k≥ 1,加工型運算，其作用是建立一棵以 X為根，以T1，…， Tk為第 1，… k棵子樹的樹。 ⑤剪枝 DELETE(T， X， i)，加工型運算，其作用是刪除樹 T上結點 X的第 i棵子樹；若 T無第 i棵子樹，則為空操作。 (1)二叉樹的基本概念二叉樹是結點的有窮集合，它或者是空集，或者同時滿足下述兩個條件： ①有且僅有一個稱為根的結點： ②其余結點分為兩個互不相交的集合 T T2， T1與 T2都是二叉樹，并且 T1與 T2有順序關系 (T1在 T2之前 )，它們分別稱為根的左子樹和右子樹。二叉樹是一類與樹不同的樹形結構。它們的區(qū)別是：第一，二叉樹可以是空集，這種二叉樹稱為空二叉樹；第二，二叉樹的任一結點都有兩棵子樹 (當然，它們中的任何一個可以是空子樹 )，并且這兩棵子樹之間有次序關系，也就是說，它們的位置不能交換。相應地，二叉樹上任一結點左、右子樹的根分別稱為該結點的左孩子和右孩子。另外，二叉樹上任一結點的度定義為該結點的孩子數(shù) (即非空子樹數(shù) )。除這個幾 個術語之外，樹的其它術語也適用于二叉樹。特別值得注意的是，由于二叉樹上任一結點的子樹有左、右之分，因此即使一結點只有一棵非空子樹，仍須區(qū)別它是該結點的左子樹還是右子樹，這是與樹不同的。二叉樹的基本運算包括：ⅰ初始化 INITLATE(BT)，加工型運算，其作用是設置一棵空二叉樹 BT= ROOT(BT)，引用型運算，其結果是二叉樹 BT的根結點；若 BT為空二叉樹，運算結果為一特殊標志。ⅲ求雙親 PARENT(BT，X)，引用型運算，其結果是結點 X在二叉樹 BT上的雙親；若 X是 BT的根或 X根本不是 BT上的結點，運算結果為一特殊標志。ⅳ求左孩子 LCHILD(BT， X)和求右孩子 RCHILD(BT，X)，引用型運算，其結果分別為結點 X在二叉樹 BT上的左、右孩子；若 X為 BT的葉子或 X不在 BT上，運算結果為一特殊標志。ⅴ建樹 CREAT(X， LBT， RBT)，加工型運算，其作用是建立一棵以結點 X為根，以二叉樹 LBT、 RBT分別為 X的左、右子樹的二叉樹。ⅵ剪枝 DELLEFT(BT， X)和 DELRIGHT(BT， X)，加工型運算，其作用分別為刪除二叉樹BT上結點 X的左、右子樹；若 X無左或右子樹，運算為空操作。與其它數(shù) 據(jù)結構相同，在實際應用中根據(jù)需要對基本運算適當增減。 (2)二叉樹的性質在某些情況下，了解二叉樹的下列性質是有幫助的。性質 1二叉樹第 i(i≥ 1)層上至多有 2i1個結點。性質 2深度為 k(k≥ 1)的二叉樹至多有 2k1個結點。性質 3對任何二叉樹，若度數(shù)為 2的結點數(shù)為 n2，則葉子數(shù) n0=n2+1。有兩種特殊形態(tài)的二叉樹在討論問題時很有用，這就是滿二叉樹和完全二叉樹。深度為 k(k≥ 1)且有2k1個結點的二叉樹稱為滿二叉樹。由性質 2知，滿二叉樹上各層的結點數(shù)已達到了二叉樹可以容納的最大值。如果在一棵深度為 k(k≥ 1)的滿二叉樹上刪去第 k層上最右邊的連續(xù) j(0≤ j2k1)個結點，就得到一棵深度為 k的完全二叉樹。顯然，滿二叉樹也是完全二叉樹，但反之不然。完全二叉樹有下述重要性質 (其中［ x］表示不大于 x的最大整數(shù) )：性質 4具有 n個結點的完全二叉樹的深度為［ log2n］ +1。完全二叉樹另一個重要性質是對其結點的 “按層編號 ”將得到很好的結果。所謂 “按層編號 ”是指：將一棵樹中的所有 n個結點按從第一層到最大層、每層從左到右的順序依次標記為 1， 2，…， n。性質 5如果將一棵有 n個結點的完全二叉樹按層編號，則對任一編號為 i(1≤ i≤ n)的結點 X有： (1)若 i=1，則結點 X是根；若 i1，則 X的雙親 PARENT(X)的編號為［ i/2］。 (2)若 2in，則結點 X無左孩子 (且無右孩子 )；否則， X的孩子 LCHILD(X)的編號為 2i。 (3)若 2i+1n，則結點 X無右孩子，否則， X的右孩子 RCHILD(X)的編號為 2i+1 ，順序存儲結構和鏈式存儲結構。 (1)二叉樹的鏈式存儲結構二叉樹有不同的鏈式存儲結構，其中最常用的是二叉樹鏈表與三叉鏈表。二叉樹鏈表的結點形式如下： lchild data rchild 其中， data域稱為數(shù)據(jù)域，用于存儲二叉樹結點中的數(shù)據(jù)元素； lchild域稱為左孩子指針域，用于存放指向本結點左孩子的指針 (這個指針及指針域有時簡稱為左指針 )。類似地， rchild域稱為右孩子指針域，用于存放指向本結點右孩子的指針 (簡稱右指針 )。二叉鏈表中的所有存儲結點通過它們的左、右指針的鏈接而形成一個整體。此外，每個二叉鏈表還必須有一個指向根結點的指針，該指針稱為根指針。根指針具有標識二叉鏈表的作用，對二叉鏈表的訪問只能從根指針開始。值得注意的是，二叉鏈表中每 個存儲結點的每個指針域必須有一個值，這個值或者是指向該結點的一個孩子的指針，或者是空指針 NULL。若二叉樹為空，則 root=NULL。若某結點的某個孩子不存在，則相應的指針為空。具有 n個結點的二叉樹中，一共有 2n個指針域，其中只有 n1個用來指向結點的左右孩子，其余的 n+1個指針域為 NULL。二叉樹的鏈式存儲結構操作方便，表達簡明 (二叉樹的邏輯關系 ——結點間的父子關系 ——在二叉鏈表和三叉鏈表中被直接表達成對應存儲結點之間的指針 )，因而成為二叉樹最常用的存儲結構。然而在某些情況下，二叉樹的順序存儲結構也很有用 。 (2)二叉樹的順序存儲結構二叉樹的順序存儲結構由一個一維數(shù)組構成，二叉樹上的結點按某種次序分別存入該數(shù)組的各個單元。顯然，這里的關鍵在于結點的存儲次序，這種次序應能反映結點之間的邏輯關系 (父子關系 )，否則二叉樹的基本運算就難以實現(xiàn)。由二叉樹的性質 5可知，若對任一完全二叉樹上的所有結點按層編號，則結點編號之間的數(shù)值關系可以準確地反映結點之間的邏輯關系。因此，對于任何完全二叉樹來說，可以采用 “以編號為地址 ”的策略將結點存入作為順序存儲結構的一維數(shù)組。具體地說就是：將編號為 i的結點存入一維數(shù)組的第 i個 單元。在這一存儲結構中，由于一結點的存儲位置 (即下標 )也就是它的編號，故結點間的邏輯關系可通過它們下標間的數(shù)值關系確定。 ，無需詳加討論。下面研究二叉樹的一種較為復雜的重要運算 ——遍歷及其在二叉鏈表上的實現(xiàn)。遍歷一棵二叉樹就是按某種次序系統(tǒng)地 “訪問 ”二叉樹上的所有結點，使每個結點恰好被 “訪問 ”一次。所謂 “訪問 ”一個結點，是指對該結點的數(shù)據(jù)域進行某種處理，處理的內容依具體問題而定，通常比較簡單。遍歷運算的關鍵在于訪問結點的 “次序 ”，這種次序應保 證二叉樹上的每個結點均被訪問一次且僅一次。由定義可知，一棵二叉樹由三部分組成：根、左子樹和右子樹。因此對二叉樹的遍歷也可相應地分解成三項 “子任務 ”： ①訪問根根點； ②遍歷左子樹 (即依次訪問左子樹上的全部結點 )； ③遍歷右子樹 (即依次訪問右子樹上的全部結點 )。因為左、右子樹都是二叉樹 (可以是空二叉樹 )，對它們的遍歷可以按上述方法繼續(xù)分解，直到每棵子樹均為空二叉樹為止。由此可見，上述三項子任務之間的次序決定了遍歷的次序。若以 D、 L、 R分別表示這三項子任務，則人有六種可能的次序： DLR、 LDR、 LRD、 DRL、 RDL和 RLD。通常限定 “先左后右 ”，即子任務②在子任務③之前完成，這樣就只剩下前三種次序，按這三種次序進行的遍歷分別稱為先根遍歷 (或前序遍歷 )、中根 (或中序 )遍歷、后根 (或后序 )遍歷。三種遍歷方法的定義如下：先根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作： ①訪問根結點； ②先根遍歷左子樹 ③先根遍歷右子樹。中根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操作： ①中根遍歷左子樹； ②訪問根結點； ③中根遍右子樹。后根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操 作； ①后根遍歷左子樹 ②后根遍歷右子樹 ③訪問根結點。 顯然，上述三種遍歷方法的區(qū)別在于執(zhí)行子任務 “訪問根結點 ”的 “時機 ”不同； 最先(最后、在中間 )執(zhí)行此子任務，則為先根 (后根、中根 )遍歷。按某種遍歷方法遍歷一棵二叉樹，將得到該二叉樹上所有結點的訪問序列 。為了適應各種應用問題的需要，多種不同的存儲結構也相應地建立起來。下面介紹樹的三種常用存儲結構 (1)孩子鏈表表示法孩子鏈表表示法是樹的一種鏈式存儲結構。與二叉樹的二叉鏈表存儲方法類似，孩子鏈表表示法的基本思想是：樹上的一個 結點的內容 (數(shù)據(jù)元素 )以及指向該結點所有孩子的指針存儲在一起以便于運算的實現(xiàn)。由于樹上的結點的度 (孩子數(shù) )沒有限制，而且各個結點的度可能相差很大，一種自然的表示方法是為樹上的每個結點 X建立一個 “孩子鏈表 ”，以便存儲 X中的數(shù)據(jù)元素和指向 X的所有孩子的指針。一個孩子鏈表是一個帶頭結點的單鏈表，單鏈表的頭結點含兩個域：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用于存儲結點 X中的數(shù)據(jù)元素；指針域用于存儲指向該單鏈表中第一個表結點 (首結點 )的指針。為了檢索方便，所有頭結點組織成一個數(shù)組，稱為表頭數(shù)組。對每個結點 X的孩子鏈表來說，其中的所有表結點也含兩個域，孩子域 (即數(shù)據(jù)域 )和指針域。第 i個表結點的孩子域存儲 X的第 i個孩子在頭結點數(shù)組中的下標值。 (2)孩子兄弟鏈表表示法孩子兄弟鏈表中所有存儲結點的形式相同，均含三個域：數(shù)據(jù)域 ——用于存儲樹上的結點中的數(shù)據(jù)元素；孩子域 ——用于存儲指向本結點第一個孩子的指針；兄弟域 ——用于存放指向本結點下一個兄弟的指針。值得注意的是，孩子兄弟鏈表的結構形式與二叉鏈表完全相同；但存儲結點中指針的含義不同。二叉鏈表中存儲結點的左、右指針分別指向左、右孩子；而孩子兄弟鏈表中存儲結點的兩個指針 分別指向 “長子 ”和 “大弟 ”。在孩子兄弟鏈表表示法中，結點形式統(tǒng)一，結點間的聯(lián)系比較簡潔。同時，在這種存儲結構上容易實現(xiàn)樹形數(shù)據(jù)結構的大多數(shù)運算。 (3)雙親表示法樹上每個結點的孩子可以有任意多個，但雙親只有一個。因此，通過指向雙親的指針而將樹中所有結點組織在一起形成一種存儲結構是十分簡法的。樹的這種存儲表示方法稱為雙親表示法。在雙親表示法下，每個存儲結點由兩個域組成：數(shù)據(jù)域 ——用于存儲樹上結點中的數(shù)據(jù)元素； “指針 ”域 ——用于指示本結點之雙親所在的存儲結點。值得注意的是， “指針 ”域的類型定義可以有兩種選擇。第 一種是將其定義為高級語言 (如 C語句 )中的指針類型。通過將存儲結點中的指針域定義為高級語言中的指針類型，就得到各種鏈式存儲結構，如單鏈表、二叉鏈表、孩子鏈表等等。第二種選擇是將 “指針 ”域定義為整型、子界型等型。嚴格地說，無論選擇上述哪種定義，得到的都是鏈式存儲結構，因為在這兩種定義之下，各存儲結點之間的聯(lián)結是通過 “指針 ”完成的，而且這些指針反映了結點之間的邏輯關系。為了區(qū)別這兩種鏈式結構，通常將指針域定義為高級語言中的指針類型的各種鏈式存儲結構 (如單鏈表、二叉鏈表等等 )稱為 “動態(tài)鏈表 ”，相應的指針稱為 “動態(tài)指針 ”；將指針域定義為整型、子界型等類型的各種鍵式存儲結構稱為 “靜態(tài)鏈表 ”，相應的 “指針 ”稱為： “靜態(tài)指針 ”。動態(tài)鏈表中的結點是