C Academy · บทเรียน

โหนดและโครงสร้างต้นไม้

จำลองโหนดด้วยพอยน์เตอร์

โหนดและโครงสร้างต้นไม้ เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

ต้นไม้ทวิภาคคืออะไร

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

โหนดที่อยู่บนสุดคือราก โหนดที่ไม่มีโหนดลูกคือใบไม้ รูปแบบนี้ทำให้ต้นไม้ทวิภาคเหมาะอย่างยิ่งสำหรับการค้นหา การเรียงลำดับ และการประมวลผลแบบเรียกตัวเอง

โครงสร้าง Node

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

พอยน์เตอร์แต่ละตัวชี้ไปยัง Node อื่น หรือชี้ไปที่ NULL เมื่อไม่มีโหนดลูกในด้านนั้น

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

เหตุผลที่ใช้พอยน์เตอร์อ้างอิงตัวเอง

โหนดไม่สามารถบรรจุโหนดเต็มอีกโหนดหนึ่งเป็นค่าได้ เพราะจะต้องใช้พื้นที่เก็บข้อมูลไม่สิ้นสุด แต่ให้เก็บ พอยน์เตอร์ ไปยังโหนดลูกแทน

พอยน์เตอร์มีขนาดคงที่ ดังนั้น struct จึงมีขนาดที่ทราบแน่นอน และยังเชื่อมโยงไปยังโหนดอื่นบนฮีพได้

struct Node {
    int value;
    struct Node *left;   /* 8 bytes on 64-bit */
    struct Node *right;  /* 8 bytes on 64-bit */
};

typedef เพื่อความสะดวก

การพิมพ์ struct Node ซ้ำทุกแห่งเป็นเรื่องน่าเบื่อ typedef ทำให้เราเขียนเพียง Node ได้

ยังจำเป็นต้องใช้แท็กภายใน struct เนื่องจากในจุดนั้นชนิดข้อมูลยังประกาศไม่สมบูรณ์

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

การจัดสรร Node

โหนดอยู่บนฮีพและสร้างด้วย malloc เรากำหนดค่าและเริ่มต้นพอยน์เตอร์โหนดลูกทั้งสองตัวเป็น NULL

ตรวจสอบเสมอว่า malloc ไม่ได้คืนค่าเป็น NULL ก่อนใช้หน่วยความจำ

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return NULL;
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

สร้างต้นไม้ขนาดเล็กด้วยตนเอง

เพื่อทำความเข้าใจการเชื่อมโยง ให้เราต่อโหนดสามโหนดด้วยตนเอง ได้แก่ รากหนึ่งโหนดกับโหนดลูกสองโหนด

โปรแกรมนี้สร้างต้นไม้และแสดงค่า จากนั้นโดยปกติเราจะคืนหน่วยความจำของต้นไม้ (จะกล่าวถึงในภายหลัง)

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

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Node *create_node(int v) {
    Node *n = malloc(sizeof(Node));
    n->value = v; n->left = NULL; n->right = NULL;
    return n;
}

int main(void) {
    Node *root = create_node(10);
    root->left = create_node(5);
    root->right = create_node(15);
    printf("%d %d %d\n", root->left->value, root->value, root->right->value);
    return 0;
}

ไปยังโหนดหลาน

คุณเลื่อนดูต้นไม้ด้วยการต่อเครื่องหมายลูกศร root->left->right จะเลื่อนลงไปยังโหนดลูกด้านซ้าย แล้วไปยังโหนดลูกด้านขวาของโหนดนั้น

ก่อนติดตามพอยน์เตอร์ ตรวจสอบให้แน่ใจว่าพอยน์เตอร์ไม่ใช่ NULL มิฉะนั้นโปรแกรมอาจหยุดทำงาน

/* root
 *   \
 *    right (15)
 *        \
 *         right->right (20)
 */
if (root->right != NULL && root->right->right != NULL)
    printf("%d\n", root->right->right->value);

นับโหนดแบบเรียกตัวเอง

การเรียกตัวเองเหมาะกับต้นไม้อย่างเป็นธรรมชาติ หากต้องการนับโหนด ต้นไม้ย่อยว่างจะมีศูนย์โหนด มิฉะนั้นให้นับโหนดนี้รวมกับต้นไม้ย่อยทั้งสอง

การตรวจสอบ NULL คือกรณีฐานที่หยุดการเรียกตัวเอง

int count_nodes(Node *root) {
    if (root == NULL) return 0;
    return 1 + count_nodes(root->left)
             + count_nodes(root->right);
}

วัดความสูง

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

เราเลือกค่าความสูงที่มากกว่าจากต้นไม้ย่อยทั้งสองแล้วบวกหนึ่ง กำหนดให้ต้นไม้ว่างมีความสูง -1 เพื่อให้โหนดเดี่ยวมีความสูง 0

int height(Node *root) {
    if (root == NULL) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

ระบุโหนดใบไม้

ใบไม้คือโหนดที่ไม่มีโหนดลูก โดยทั้ง left และ right เป็น NULL

ฟังก์ชันช่วยขนาดเล็กนี้มีประโยชน์กับกระบวนการท่องผ่านและการนับหลายรูปแบบ

int is_leaf(Node *n) {
    return n != NULL && n->left == NULL && n->right == NULL;
}

นำโครงสร้างมาใช้งาน

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

สังเกตว่าฟังก์ชันช่วยไม่เคยสมมติรูปร่างตายตัว แต่ทำงานกับต้นไม้ใดก็ได้ เพราะการเรียกตัวเองติดตามพอยน์เตอร์จริง

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

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }

int main(void){
    Node *root = nn(10);
    root->left = nn(5); root->right = nn(15);
    root->left->left = nn(2);
    printf("nodes=%d height=%d\n", count(root), height(root));
    return 0;
}

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบความเข้าใจเกี่ยวกับโครงสร้างโหนดของคุณ

ทบทวน

โหนดของต้นไม้ทวิภาคเก็บค่าและพอยน์เตอร์ที่อ้างอิงตัวเองสองตัว (left, right) ซึ่งกำหนดเป็น NULL เมื่อไม่มีโหนดลูก

เราจัดสรรโหนดด้วย malloc เชื่อมโยงด้วยตนเอง และประมวลผลแบบเรียกตัวเอง การตรวจสอบ NULL เป็นกรณีฐานเสมอสำหรับการนับ การวัดความสูง และการทดสอบว่าเป็นใบไม้

คำถามที่พบบ่อย

บทเรียน “โหนดและโครงสร้างต้นไม้” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “โหนดและโครงสร้างต้นไม้” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “โหนดและโครงสร้างต้นไม้”

จำลองโหนดด้วยพอยน์เตอร์ คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน

บทเรียน “โหนดและโครงสร้างต้นไม้” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy