二叉鏈表

typedef struct CSNode{

ElemType data;

struct CSNode *firstchild ， *netsibling;

} CSNode，* CSTree;

由于二叉樹的存儲結(jié)構(gòu)比較簡單，處理起來也比較方便，所以有時需要把復(fù)雜的樹，轉(zhuǎn)換為簡單的二叉樹后再作處理。

三叉鏈表是二叉樹的另一種主要的鏈式存儲結(jié)構(gòu)。三叉鏈表與二叉鏈表的主要區(qū)別在于，它的結(jié)點比二叉鏈表的結(jié)點多一個指針域，該域用于存儲一個指向本結(jié)點雙親的指針。三叉鏈表的結(jié)點形式如下:

(a)一棵二叉樹BT

(b)BT的二叉鏈表示意圖

(c)BT的三叉鏈表示意圖

用二叉鏈表做為存儲結(jié)構(gòu)，先序遍歷算法可描述為:

void InOrder(BinTree T)

{ //算法里①~⑥是為了說明執(zhí)行過程加入的標號

① if(T) { // 如果二叉樹非空

② printf("%c"，T->data); // 訪問結(jié)點 ③ InOrder(T->lchild); ④ InOrder(T->rchild); ⑤ }

⑥ } // InOrder

void createBiTree(BiTree *bt){

char ch;

ch = getchar();

if(ch == '.')

*bt = NULL;

else{

*bt = (BiTree)malloc(sizeof(BiTNode));//向內(nèi)存申請節(jié)點空間

(*bt)->data = ch;

createBiTree(&((*bt)->LChild));//生成左子樹

createBiTree(&((*bt)->RChild));//生成右子樹

}

}/*createBiTree*/

/*==================打印二叉樹=============*/

void printTree(BiTree bt,int nLayer){

int i;

if(bt == NULL)

return ;

printTree(bt ->RChild,nLayer+1);

for(i=0;i<nLayer;i++)

printf(" ");

printf("%c\n",bt->data);

printTree(bt->LChild,nLayer+1);

}

圖一:

(a)1 2 4 . . 6 . . 3 . 5 . 7 . 8 . .

(b)1 2 4 . . 5 . . 3 6 . . 7 . . 運行結(jié)果:

圖二:

(a)7 3 1 . . 2 . . 9 . 10 . 8 . 4 . .

(b)7 3 1 . . 5 4 . . . 11 10 . . 15 . .

運行結(jié)果:

二叉排序樹的查找過程和次優(yōu)二叉樹類似，通常采取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)。中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列，一個無序序列可以通過構(gòu)造一棵二叉排序樹變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。每次插入的新的結(jié)點都是二叉排序樹上新的葉子結(jié)點，在進行插入操作時，不必移動其它結(jié)點，只需改動某個結(jié)點的指針，由空變?yōu)榉强占纯?。搜?插入,刪除的復(fù)雜度等于樹高，O(log(n)).