其中，data域稱為數(shù)據(jù)域，用于存儲(chǔ)二叉樹結(jié)點(diǎn)中的數(shù)據(jù)元素;lchild域稱為左孩子指針域，用于存放指向本結(jié)點(diǎn)左孩子的指針（這個(gè)指針及指針域有時(shí)簡稱為左指針）。類似地，rchild域稱為右孩子指針域，用于存放指向本結(jié)點(diǎn)右孩子的指針（簡稱右指針）。二叉鏈表中的所有存儲(chǔ)結(jié)點(diǎn)**它們的左、右指針的鏈接而形成一個(gè)整體。此外，每個(gè)二叉鏈表還必須有一個(gè)指向根結(jié)點(diǎn)的指針，該指針稱為根指針。根指針具有標(biāo)識二叉鏈表的作用，對二叉鏈表的訪問只能從根指針開始。值得注意的是，二叉鏈表中每個(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è)指針域，其中只有n-1個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的n+1個(gè)指針域?yàn)镹ULL。
二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作方便，表達(dá)簡明（二叉樹的邏輯關(guān)系———結(jié)點(diǎn)間的父子關(guān)系———在二叉鏈表和三叉鏈表中被直接表達(dá)成對應(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可知，若對任一完全二叉樹上的所有結(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)系確定。來源：www.examda.com
5.二叉樹的遍歷
由于二叉樹的基本運(yùn)算在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)比較簡單，無需詳加討論。下面研究二叉樹的一種較為復(fù)雜的重要運(yùn)算———遍歷及其在二叉鏈表上的實(shí)現(xiàn)。
遍歷一棵二叉樹就是按某種次序系統(tǒng)地“訪問”二叉樹上的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被“訪問”一次。所謂“訪問”一個(gè)結(jié)點(diǎn)，是指對該結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行某種處理，處理的內(nèi)容依具體問題而定，通常比較簡單。遍歷運(yùn)算的關(guān)鍵在于訪問結(jié)點(diǎn)的“次序”，這種次序應(yīng)**二叉樹上的每個(gè)結(jié)點(diǎn)均被訪問一次且僅一次。
由定義可知，一棵二叉樹由三部分組成:根、左子樹和右子樹。因此對二叉樹的遍歷也可相應(yīng)地分解成三項(xiàng)“子任務(wù)”:
①訪問根根點(diǎn);
②遍歷左子樹（即依次訪問左子樹上的全部結(jié)點(diǎn)）;③遍歷右子樹（即依次訪問右子樹上的全部結(jié)點(diǎn)）。
因?yàn)樽?、右子樹都是二叉樹（可以是空二叉樹），對它們的遍歷可以按上述方法繼續(xù)分解，直到每棵子樹均為空二叉樹為止。由此可見，上述三項(xiàng)子任務(wù)之間的次序決定了遍歷的次序。若以D、L、R分別表示這三項(xiàng)子任務(wù)，則人有六種可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任務(wù)②在子任務(wù)③之前完成，這樣就只剩下前三種次序，按這三種次序進(jìn)行的遍歷分別稱為先根遍歷（或前序遍歷）、中根（或中序）遍歷、后根（或后序）遍歷。三種遍歷方法的定義如下:
先根遍歷 若需遍歷的二叉樹為空，執(zhí)行空操作;否則，依次執(zhí)行下列操作:
①訪問根結(jié)點(diǎn);
②先根遍歷左子樹;
③先根遍歷右子樹。
中根遍歷 若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操作:
①中根遍歷左子樹;②訪問根結(jié)點(diǎn);③中根遍右子樹。
后根遍歷 若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行下列操作:
①后根遍歷左子樹。②后根遍歷右子樹。③訪問根結(jié)點(diǎn)。
顯然，上述三種遍歷方法的區(qū)別在于執(zhí)行子任務(wù)“訪問根結(jié)點(diǎn)”的“時(shí)機(jī)”不同;最先（最后、在中間）執(zhí)行此子任務(wù)，則為先根（后根、中根）遍歷。
按某種遍歷方法遍歷一棵二叉樹，將得到該二叉樹上所有結(jié)點(diǎn)的訪問序列。
6.樹
樹是一種常用的數(shù)據(jù)結(jié)構(gòu)。為了適應(yīng)各種應(yīng)用問題的需要，多種不同的存儲(chǔ)結(jié)構(gòu)也相應(yīng)地建立起來。下面介紹樹的三種常用存儲(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ù)組。對每個(gè)結(jié)點(diǎn)X的孩子鏈表來說，其中的所有表結(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)的左、右指針分別指向左、右孩子;而孩子兄弟鏈表中存儲(chǔ)結(jié)點(diǎn)的兩個(gè)指針分別指向“長子”和“大弟”。
在孩子兄弟鏈表表示法中，結(jié)點(diǎn)形式統(tǒng)一，結(jié)點(diǎn)間的聯(lián)系比較簡捷。同時(shí)，在這種存儲(chǔ)結(jié)構(gòu)上容易實(shí)現(xiàn)樹數(shù)據(jù)結(jié)構(gòu)的大多數(shù)運(yù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)值）。來源：www.examda.com
7.樹的遍歷
與二叉樹類似，遍歷是樹的一種重要運(yùn)算。樹的主要遍歷方法有以下三種。
（1）先根遍歷若樹非空，則
①訪問根結(jié)點(diǎn);
②依次先根遍歷根的各個(gè)子樹T 1 ，…，T m 。
（2）后根遍歷若樹非空，則
①依次先根遍歷根的各個(gè)子樹T 1 ，…，T m 。②訪問根結(jié)點(diǎn);
（3）層次遍歷
①若樹非空，訪問根結(jié)點(diǎn);
②若第1，…，i（i≥1）層結(jié)點(diǎn)已被訪問，且第i+1層結(jié)點(diǎn)未訪問，則從左到右依次訪問第i+1層結(jié)點(diǎn)。
顯然，按層次遍歷所得的結(jié)點(diǎn)訪問序列中，各結(jié)點(diǎn)的序號與按層編號所得的編號一致。
8.樹與二叉樹之間的轉(zhuǎn)換
一般樹轉(zhuǎn)換為二叉樹的基本思想是:將樹中每個(gè)結(jié)點(diǎn)用兩個(gè)鏈接表示就可以了，一個(gè)指向它最左邊的孩子，另一個(gè)指向它右邊的一個(gè)兄弟，從圖形上看，具體步驟是:
①加線:在兄弟結(jié)點(diǎn)直接加一虛線;
②抹線:對每個(gè)結(jié)點(diǎn)，除了其最左的一個(gè)孩子外，抹去該結(jié)點(diǎn)原來與其余孩子之間的邊線;
③旋轉(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)連接起來;