搜尋
首頁常見問題二元樹的鍊式儲存結構是什麼

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

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

本教學操作環境: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中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)