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

โจทย์นี้เหมือนกับบทความก่อนหน้า (ID 1004078620) แตกต่างเพียงชื่อตัวแปรจาก k เป็น x และโครงสร้างต้นไม้ตัวอย่าง

โค้ด C++ (เหมือนกันแต่เปลี่ยนชื่อตัวแปร)

#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 x) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, x);
    root->rightChild = deleteLeafNode(root->rightChild, x);
    if (root->data == x && 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(4);
    root->leftChild = newNode(2);
    root->rightChild = newNode(12);
    root->leftChild->leftChild = newNode(3);
    root->leftChild->rightChild = newNode(5);
    root->rightChild->rightChild = newNode(9);
    
    deleteLeafNode(root, 3);  // ลบโหนดใบที่มีค่า 3
    
    cout << "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

ผลลัพธ์

Inorder traversal after deletion : 5 2 9 12 4

สรุป: อัลกอริทึมเดียวกันกับบทความก่อนหน้า ใช้ Post-order traversal ตรวจสอบโหนดใบที่มีค่าเท่ากับ x แล้วลบออก