ลบโหนดใบ (Leaf Node) ที่มีค่าเท่ากับ k ใน Binary Tree ด้วย C++

โจทย์: ลบโหนดใบ (โหนดที่ไม่มีลูก) ที่มีค่าเท่ากับ k ออกจาก Binary Tree

แนวคิดการแก้ปัญหา (Post-order Traversal)

ใช้การเดินแบบ Post-order (ลูกซ้าย → ลูกขวา → ราก) เพื่อให้แน่ใจว่าโหนดลูกถูกประมวลผลก่อนโหนดแม่ เมื่อพบโหนดใบที่มีค่า k ให้คืนค่า nullptr ให้โหนดแม่

โครงสร้างโหนด

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

ฟังก์ชันลบโหนดใบ

Node* deleteLeafNode(Node* root, int k) {
    if (root == NULL)
        return nullptr;
    
    // ประมวลผลลูกซ้ายและขวาก่อน
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    
    // ถ้าเป็นโหนดใบและมีค่าเท่ากับ k ให้ลบ (คืน nullptr)
    if (root->data == k && root->leftChild == NULL && root->rightChild == NULL)
        return nullptr;
    
    return root;
}

ตัวอย่างเต็ม

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

struct Node* newNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return (newNode);
}

Node* deleteLeafNode(Node* root, int k) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && root->leftChild == NULL && root->rightChild == NULL)
        return nullptr;
    return root;
}

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}

int main(void) {
    struct Node* root = newNode(6);
    root->leftChild = newNode(7);
    root->rightChild = newNode(7);
    root->leftChild->leftChild = newNode(5);
    root->leftChild->rightChild = newNode(3);
    root->rightChild->rightChild = newNode(7);
    
    deleteLeafNode(root, 7);
    
    cout << "Inorder traversal after deleting given leaf node: ";
    inorder(root);
    return 0;
}

ผลลัพธ์

Inorder traversal after deleting given leaf node: 5 3 7 6

คำอธิบาย: โหนดใบที่มีค่า 7 ถูกลบทั้งหมด 3 ตัว โหนด 7 ด้านขวาสุดไม่ถูกลบเพราะมีลูกขวา (แต่ในตัวอย่างไม่มีลูก จริงๆ แล้วโครงสร้างต้นไม้ในโค้ดอาจแตกต่างจากรูปประกอบ)