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

二元樹的鍊式儲存結構是指用鍊錶來表示一棵二元樹，也就是用鍊錶來指示元素之間的邏輯關係。二元樹的鍊式儲存結構通常有兩種儲存形式：二元鍊錶和三叉鍊錶。

本教學操作環境：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語言影片教學》

以上是二元樹的鍊式儲存結構是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！