Apakah struktur penyimpanan berpaut bagi pokok binari?

Struktur storan terpaut bagi pokok binari merujuk kepada penggunaan senarai terpaut untuk mewakili pepohon binari, iaitu, menggunakan senarai terpaut untuk menunjukkan hubungan logik antara unsur. Struktur storan terpaut pokok binari biasanya mempunyai dua bentuk storan: senarai terpaut binari dan senarai terpaut triplet.

Persekitaran pengendalian tutorial ini: sistem Windows 7, versi c99, komputer Dell G3.

Struktur storan terpaut bagi pepohon binari menggunakan senarai terpaut untuk mewakili pepohon perduaan, iaitu, senarai terpaut digunakan untuk menunjukkan perhubungan logik antara elemen. Biasanya terdapat dua bentuk storan:

• Setiap nod dalam senarai terpaut terdiri daripada tiga medan Sebagai tambahan kepada medan data, terdapat juga dua medan penunjuk, yang digunakan untuk memberikan Alamat storan anak kiri dan anak kanan nod.

• Setiap nod dalam senarai terpaut terdiri daripada empat medan Selain medan data, terdapat juga tiga medan penunjuk, yang digunakan untuk memberikan anak kiri dan anak kanan. nod. dan alamat storan di mana nod induk berada.

Struktur storan berpaut bagi pokok binari (penjelasan terperinci dalam bahasa C)

Rajah 1 Normal Gambarajah skematik pokok binari

ditunjukkan dalam Rajah 1. Ini adalah pokok binari biasa Jika ia disimpan dalam rantai, anda hanya perlu bermula dari nod akar pokok dan simpan setiap nod dan anak kiri dan kanannya menggunakan senarai terpaut. Oleh itu, struktur simpanan rantai yang sepadan dengan Rajah 1 ditunjukkan dalam Rajah 2:

Rajah 2 Diagram skematik struktur storan berantai bagi pokok binari

Seperti yang dapat dilihat dari Rajah 2, apabila storan berantai pokok binari digunakan, struktur nod terdiri daripada 3 bahagian (seperti yang ditunjukkan dalam Rajah 3):

• Penuding ke nod anak kiri (Lchild); >

  Menunjuk ke nod anak kanan Penunjuk (Rchild); Rajah 3 Struktur nod pokok binari
• mewakili kod bahasa C struktur nod ini:

Kod bahasa C yang sepadan dengan struktur simpanan rantai dalam Rajah 2 ialah:

• Hasil keluaran program:

Malah, struktur simpanan rantaian pokok binari adalah jauh lebih banyak daripada yang ditunjukkan dalam Rajah 2. Sebagai contoh, dalam beberapa senario sebenar, operasi "mencari nod induk nod" boleh dilakukan Dalam kes ini, medan penunjuk boleh ditambah pada struktur nod untuk setiap nod untuk menghala ke nod induknya, seperti yang ditunjukkan. dalam Rajah 4. :

Rajah 4 Struktur storan terpaut bagi pokok binari tersuai

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

Struktur senarai terpaut seperti ini biasanya dipanggil senarai terpaut tiga kali.

Menggunakan senarai berpaut tiga serampang yang ditunjukkan dalam Rajah 4, kita boleh mencari nod induk setiap nod dengan mudah. Oleh itu, apabila menyelesaikan masalah praktikal, menggunakan struktur senarai terpaut yang sesuai untuk menyimpan pokok binari boleh mencapai dua kali ganda hasil dengan separuh usaha.

#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;
}

Cadangan berkaitan: "

Tutorial Video Bahasa C

4

"

Atas ialah kandungan terperinci Apakah struktur penyimpanan berpaut bagi pokok binari?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!