C語(yǔ)言二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是怎樣的

本文小編為大家詳細(xì)介紹“C語(yǔ)言二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是怎樣的”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C語(yǔ)言二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是怎樣的”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈表來(lái)指示元素之間的邏輯關(guān)系。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常有兩種存儲(chǔ)形式：二叉鏈表和三叉鏈表。

本教程操作環(huán)境：windows7系統(tǒng)、c99版本、Dell G3電腦。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈表來(lái)指示元素之間的邏輯關(guān)系。通常有兩種存儲(chǔ)形式：

• 鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域之外，還有兩個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)的左孩子和右孩子所在的存儲(chǔ)地址。

• 鏈表中每個(gè)結(jié)點(diǎn)由四個(gè)域組成，除了數(shù)據(jù)域之外，還有三個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)的左孩子、右孩子和雙親結(jié)點(diǎn)所在的存儲(chǔ)地址。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（C語(yǔ)言詳解）

圖 1 普通二叉樹(shù)示意圖

如圖 1 所示，此為一棵普通的二叉樹(shù)，若將其采用鏈?zhǔn)酱鎯?chǔ)，則只需從樹(shù)的根節(jié)點(diǎn)開(kāi)始，將各個(gè)節(jié)點(diǎn)及其左右孩子使用鏈表存儲(chǔ)即可。因此，圖 1 對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖 2 所示：

圖 2 二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖

由圖 2 可知，采用鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)時(shí)，其節(jié)點(diǎn)結(jié)構(gòu)由 3 部分構(gòu)成（如圖 3 所示）：

• 指向左孩子節(jié)點(diǎn)的指針（Lchild）；

• 節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)（data）；

• 指向右孩子節(jié)點(diǎn)的指針（Rchild）；

圖 3 二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)

表示該節(jié)點(diǎn)結(jié)構(gòu)的 C 語(yǔ)言代碼為：

typedef struct BiTNode{
    TElemType data;//數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;//左右孩子指針
    struct BiTNode *parent;
}BiTNode,*BiTree;

圖 2 中的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)應(yīng)的 C 語(yǔ)言代碼為：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

程序輸出結(jié)果：

4

其實(shí)，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)遠(yuǎn)不止圖 2 所示的這一種。例如，在某些實(shí)際場(chǎng)景中，可能會(huì)做 "查找某節(jié)點(diǎn)的父節(jié)點(diǎn)" 的操作，這時(shí)可以在節(jié)點(diǎn)結(jié)構(gòu)中再添加一個(gè)指針域，用于各個(gè)節(jié)點(diǎn)指向其父親節(jié)點(diǎn)，如圖 4 所示：

圖 4 自定義二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

這樣的鏈表結(jié)構(gòu)，通常稱為三叉鏈表。

利用圖 4 所示的三叉鏈表，我們可以很輕松地找到各節(jié)點(diǎn)的父節(jié)點(diǎn)。因此，在解決實(shí)際問(wèn)題時(shí)，用合適的鏈表結(jié)構(gòu)存儲(chǔ)二叉樹(shù)，可以起到事半功倍的效果。

讀到這里，這篇“C語(yǔ)言二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是怎樣的”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。