二元樹的鏈式儲存結構是什麼

二元樹的鏈式儲存結構是指用連結串列來表示一棵二元樹，即用連結串列來指示元素之間的邏輯關係。二元樹的鏈式儲存結構通常有兩種儲存形式：二元連結串列和三元連結串列。

本教學操作環境：windows7系統、c99版本、Dell G3電腦。

二元樹的鏈式儲存結構就是用連結串列來表示一棵二元樹，即用連結串列來指示元素之間的邏輯關係。通常有兩種儲存形式：

• 連結串列中每個結點由三個域組成，除了資料域之外，還有兩個指標域，分別用來給出該結點的左孩子和右孩子所在的儲存地址。

• 連結串列中每個結點由四個域組成，除了資料域之外，還有三個指標域，分別用來給出該結點的左孩子、右孩子和雙親結點所在的儲存地址。

二元樹的鏈式儲存結構（C語言詳解）

圖 1 普通二元樹示意圖

如圖 1 所示，此為一棵普通的二元樹，若將其採用鏈式儲存，則只需從樹的根節點開始，將各個節點及其左右孩子使用連結串列儲存即可。因此，圖 1 對應的鏈式儲存結構如圖 2 所示：

圖 2 二元樹鏈式儲存結構示意圖

由圖 2 可知，採用鏈式儲存二元樹時，其節點結構由 3 部分構成（如圖 3 所示）：

• 指向左孩子節點的指標（Lchild）；

• 節點儲存的資料（data）；

• 指向右孩子節點的指標（Rchild）；

圖 3 二元樹節點結構

表示該節點結構的 C 語言程式碼為：

typedef struct BiTNode{
    TElemType data;//資料域
    struct BiTNode *lchild,*rchild;//左右孩子指標
    struct BiTNode *parent;
}BiTNode,*BiTree;

圖 2 中的鏈式儲存結構對應的 C 語言程式碼為：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//資料域
    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;
}

程式輸出結果：

4

其實，二元樹的鏈式儲存結構遠不止圖 2 所示的這一種。例如，在某些實際場景中，可能會做 "查詢某節點的父節點" 的操作，這時可以在節點結構中再新增一個指標域，用於各個節點指向其父親節點，如圖 4 所示：

圖 4 自定義二元樹的鏈式儲存結構

這樣的連結串列結構，通常稱為三元連結串列。

利用圖 4 所示的三元連結串列，我們可以很輕鬆地找到各節點的父節點。因此，在解決實際問題時，用合適的連結串列結構儲存二元樹，可以起到事半功倍的效果。

相關推薦：《C語言視訊教學》

以上就是二元樹的鏈式儲存結構是什麼的詳細內容，更多請關注TW511.COM其它相關文章！