หาโหนดใบซ้ายลึกที่สุดใน Binary Tree ด้วย C++

บทนำ

ในบทช่วยสอนนี้ เราจะหาโหนดใบ (leaf node) ด้านซ้ายที่ลึกที่สุดใน Binary Tree (ต้นไม้แบบทวิภาค) โดยใช้ภาษา C++

ตัวอย่างต้นไม้:

        A
       / \
      B   C
     /   / \
    D   E   F
           /
          G

โหนดใบซ้ายลึกที่สุดคือ D

ขั้นตอนการแก้ปัญหา

1. สร้างโครงสร้าง Node ที่มีข้อมูล (char), ตัวชี้ซ้าย (left) และขวา (right)
2. สร้าง Binary Tree ตัวอย่างพร้อมข้อมูลทดสอบ
3. เขียนฟังก์ชันแบบเรียกซ้ำ (recursive) เพื่อหาโหนดใบซ้ายลึกที่สุด รับพารามิเตอร์ 3 ตัว: โหนดราก, บูลีนบอกว่าเป็นลูกซ้ายหรือไม่, และตัวชี้ผลลัพธ์
4. ถ้าโหนดปัจจุบันเป็นลูกซ้าย และเป็นโหนดใบ (ไม่มีลูก) ให้อัปเดตผลลัพธ์
5. เรียกฟังก์ชันซ้ำสำหรับต้นไม้ย่อยซ้าย (ส่ง true) และขวา (ส่ง false)
6. ถ้าผลลัพธ์เป็น NULL แสดงว่าไม่มีโหนดใบซ้าย
7. พิมพ์ข้อมูลของโหนดผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

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

Node *addNewNode(char data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void getDeepestLeftLeafNode(Node *root, bool isLeftNode, Node **resultPointer) {
    if (root == NULL) return;
    
    // ถ้าเป็นลูกซ้ายและเป็นโหนดใบ
    if (isLeftNode && !root->left && !root->right) {
        *resultPointer = root;
        return;
    }
    
    getDeepestLeftLeafNode(root->left, true, resultPointer);
    getDeepestLeftLeafNode(root->right, false, resultPointer);
}

int main() {
    Node* root = addNewNode('A');
    root->left = addNewNode('B');
    root->right = addNewNode('C');
    root->left->left = addNewNode('D');
    root->right->left = addNewNode('E');
    root->right->right = addNewNode('F');
    root->right->left->right = addNewNode('G');
    
    Node *result = NULL;
    getDeepestLeftLeafNode(root, false, &result);
    
    if (result) {
        cout << "The deepest left child is " << result->data << endl;
    } else {
        cout << "There is no left leaf in the given tree" << endl;
    }
    return 0;
}

ผลลัพธ์

The deepest left child is D

สรุป

อัลกอริทึมนี้ใช้ DFS (Depth-First Search) พร้อมติดตามว่าโหนดเป็นลูกซ้ายหรือไม่ เนื่องจากเราเรียกซ้ายก่อนขวา โหนดใบซ้ายที่พบล่าสุดจะเป็นลึกที่สุด หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ