1、二叉樹的存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示三叉鏈表1二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)結(jié)構(gòu)的定義如下：#define MAXSIZE = 100； /暫定二叉樹中節(jié)點(diǎn)數(shù)的最大值為 100Typedef struct ElemType *data； Int nodeNum； SqBiTree；/存儲(chǔ)空間基址(初始化時(shí)分配空間)/二叉樹中節(jié)點(diǎn)數(shù)/二叉樹的順序存儲(chǔ)結(jié)構(gòu)為了能在存儲(chǔ)結(jié)構(gòu)中反映出節(jié)點(diǎn)之間的邏輯關(guān)系，必須將二叉樹中節(jié)點(diǎn)依照一定規(guī)律安排在這組存儲(chǔ)單元中。對(duì)于完全二叉樹，只要從根起按層序存儲(chǔ)即可。顯然，這種順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹。因?yàn)?，在最壞的情況下，一 個(gè)深度為 k

2、且只有 k 個(gè)結(jié)點(diǎn)的單支樹(樹中不存在度為 2 的結(jié)點(diǎn))卻需要長 度為 2k-1 的一維數(shù)組。二叉樹的順序存儲(chǔ)圖如圖 1 所示：滿二叉樹般二叉樹滿二叉樹般二叉樹圖 1 順序存儲(chǔ)2 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹有不同的鏈?zhǔn)浇Y(jié)構(gòu)，其中最常用的是二叉鏈表與三叉鏈表。二叉鏈表 的結(jié)點(diǎn)形式如表 1 所示：lchilddatarchild表 1 鏈?zhǔn)酱鎯?chǔ)date 域：稱為數(shù)據(jù)域，用于存儲(chǔ)二叉樹結(jié)點(diǎn)中的數(shù)據(jù)元素，1child 域：稱為左孩子指針域，用于存放指向本結(jié)點(diǎn)左孩子的指針（左指針）。 rchild 域：稱為右孩子指針域，用于存放指向本結(jié)點(diǎn)右孩子的指針（右指針） 二叉鏈表中的所有存儲(chǔ)結(jié)點(diǎn)通過它們的左、右指

3、針的鏈接而形成一個(gè)整體。根指針：每個(gè)二叉鏈表還必須有一個(gè)指向根結(jié)點(diǎn)的指針。根指針具有標(biāo)識(shí)二 叉鏈表的作用，對(duì)二叉鏈表的訪問能從根指針開始。圖2中（a） （b）表示一棵二叉樹及其二叉鏈表。值得注意的是，二叉鏈表 中每個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是指向該結(jié)點(diǎn)的一個(gè)孩 子的指針，或者是空指針 NULL。二叉鏈表的類型定義如下：Typedef struct btnode *bitreptr；Struct btnodeDatatype data；Bitreptr lchild,rchild；Bitreptr root；若二叉樹為空，則root=NULL。若某結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)

4、的指針 為空。具有n個(gè)結(jié)點(diǎn)的二叉樹中，一共有2n個(gè)指針域，其中只有n-1個(gè)用來指 向結(jié)點(diǎn)的的左右孩子，其余的 n+1 個(gè)指針域?yàn)?NULL。在二叉鏈表這種存儲(chǔ)結(jié)構(gòu)上，二叉樹的多數(shù)基本運(yùn)算如求根 ,求左、右孩子 等很容易實(shí)現(xiàn)。但求雙親運(yùn)算PARENT（BT,X）的實(shí)現(xiàn)卻比較麻煩，而且其時(shí)間性 能不高。3 三叉鏈表protected:BiTreeNode *lchildprotected:BiTreeNode *lchild；BiTreeNode *rchild；BiTreeNode *parent；/ 指向左子樹的指針/ 指向右子樹的指針/ 指向雙親的指針三叉鏈表存儲(chǔ)每個(gè)節(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：LchildIata)RchildParent其中，data、lchild以及rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent域?yàn)橹?向該結(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親 結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開銷。為了便于查找任一結(jié)點(diǎn)的雙親結(jié)點(diǎn)，可以在結(jié)點(diǎn)中再增加一