二元樹的鍊式儲存結構是什麼-常見問題-PHP中文網

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

青灯夜游

發布： 2022-01-25 12:04:49

原創

10152 人瀏覽過

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

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

本教學操作環境：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;
}

登入後複製

程式輸出結果：

登入後複製

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

二元樹的鍊式儲存結構是什麼圖 4 自訂二元樹的鍊式儲存結構