ต้นไม้และกราฟ

ต้นไม้และกราฟคือโครงสร้างข้อมูลแบบไม่เป็นเชิงเส้นที่ใช้แสดงข้อมูลแบบลำดับชั้นและข้อมูลในเครือข่าย

ในบทเรียนนี้ คุณจะได้เรียนรู้:

• ต้นไม้และกราฟมีโครงสร้างอย่างไร
• วิธีนำต้นไม้ทวิภาคไปใช้งานใน C
• วิธีแสดงกราฟโดยใช้รายการประชิดและเมทริกซ์ประชิด

ต้นไม้เป็นโครงสร้างข้อมูลแบบลำดับชั้นที่ประกอบด้วยโหนด

คำศัพท์สำคัญ:

• ราก - โหนดบนสุด
• โหนดแม่และโหนดลูก - โหนดที่เชื่อมต่อกันโดยตรง
• ใบ - โหนดที่ไม่มีโหนดลูก

ในภาษา C โหนดของต้นไม้แบบทวิภาคกำหนดโดยใช้ struct ซึ่งมีพอยน์เตอร์ไปยังโหนดลูกด้านซ้ายและด้านขวา

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

วิธีการท่อง:

• Inorder (LNR) - ซ้าย, Node, ขวา
• Preorder (NLR) - Node, ซ้าย, ขวา
• Postorder (LRN) - ซ้าย, ขวา, Node

โปรแกรมนี้ท่องต้นไม้แบบทวิภาคด้วยวิธี inorder

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

กราฟคือกลุ่มของโหนด (จุดยอด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม

กราฟมีได้หลายแบบ:

• มีทิศทาง - เส้นเชื่อมมีทิศทาง
• ไม่มีทิศทาง - เส้นเชื่อมไม่มีทิศทาง

สามารถแทนกราฟได้โดยใช้:

• เมทริกซ์การเชื่อมโยง - อาร์เรย์สองมิติที่แทนการเชื่อมต่อ
• รายการการเชื่อมโยง - รายการที่โหนดแต่ละโหนดชี้ไปยังโหนดข้างเคียง

วิธีการท่องที่ใช้กันทั่วไป:

• การค้นหาแบบกว้างก่อน (BFS) - เยี่ยมชมโหนดข้างเคียงทั้งหมดก่อนลงไปยังระดับที่ลึกขึ้น
• การค้นหาแบบลึกก่อน (DFS) - สำรวจให้ลึกที่สุดเท่าที่ทำได้ก่อนย้อนกลับ

ในบทเรียนนี้ คุณได้เรียนรู้:

• โครงสร้างของต้นไม้และกราฟ
• วิธีท่องต้นไม้
• วิธีแทนและท่องกราฟ

จบหัวข้อโครงสร้างข้อมูลในภาษา C แล้ว