মান x বিশিষ্ট লিফ নোড মুছে ফেলা C++-এ

প্রথমে একটি স্ট্রাকচার দিয়ে ট্রি নোড সংজ্ঞায়িত করা হয় যাতে থাকে ডেটা এবং লেফট ও রাইট চাইল্ড পয়েন্টার।

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

newNode(int data) ফাংশন ইন্টিজার ভ্যালু নিয়ে নোড তৈরি করে এবং পয়েন্টার রিটার্ন করে। লেফট ও রাইট চাইল্ড নাল সেট করা হয়।

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

deleteLeafNode(Node* root, int x) ফাংশন রুট নোড এবং ডিলিট করার ডেটা ভ্যালু নেয়। যদি নোড পেরেন্ট হয় তবে এর লেফট ও রাইট চাইল্ড ও মুছে ফেলা হয়। ফাংশনটি মডিফাইড রুট রিটার্ন করে।

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;
}

ডিলিশনের পর ট্রি দেখানোর জন্য inorder(Node* root) ফাংশন ইনঅর্ডার ট্রভারসাল করে।

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

উদাহরণ

#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* deleteNode(Node* root, int x) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteNode(root->leftChild, x);
    root->rightChild = deleteNode(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);
    deleteNode(root, 3);
    cout << "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

আউটপুট

Inorder traversal after deletion : 5 2 9 12 4