C++ এ x এর মান সহ লিফ নোডগুলি মুছুন?

আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।

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

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

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

এখন আমরা আমাদের ডিলিট নোড (নোড* রুট, 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;
}

অবশেষে ডিলিট করার পর ট্রি ডিসপে করার জন্য আমাদের কাছে একটি ফাংশন ইনঅর্ডার (নোড* রুট) আছে যা ইনঅর্ডার ফাংশনে ট্রিকে অতিক্রম করে।

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

উদাহরণ

আসুন x

#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