মুছে ফেলা মোডটি নীচে এবং ডানদিকের নোড দ্বারা প্রতিস্থাপন করে সঞ্চালিত করা হয়৷
আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।
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);
} deletion(struct Node* root, int data) ফাংশনটি প্রদত্ত ডেটা মান সহ নোড মুছে ফেলার জন্য ব্যবহৃত হয়। অনুসন্ধান এবং মুছে ফেলার জন্য এটি রুট নোড এবং ডেটা মান নেয়। যদি কোনও চাইল্ড নোড না থাকে এবং ডেটা মান রুটের ডেটা মানের সমান হয় তবে নাল ফেরত দেওয়া হয় অন্যথায় রুট নোড ফেরত দেওয়া হয়।
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
} এখন আমরা struct Node * টাইপের একটি সারি তৈরি করি এবং এটির নাম q রাখি এবং রুট নোডটিকে q এ পুশ করি। আমরা টেম্প এবং ডেটা_নোড ঘোষণা করি যা নোডের নির্দেশক এবং ডেটা_নোডকে NULL হিসাবে সেট করে।
struct Node* temp; struct Node* data_node = NULL;
এরপরে, গভীরতম নোড খুঁজে পেতে আমরা লেভেল অর্ডার ট্রাভার্সাল করি। কিউ q খালি না হওয়া পর্যন্ত যখন লুপ চালানো হয়। সারি হল একটি FIFO ডেটা স্ট্রাকচার তাই সারির শেষ উপাদানটি হবে ডানদিকের সবচেয়ে গভীরতম নোড কারণ আমরা লেভেল অর্ডার ট্রাভার্সালের মাধ্যমে যাচ্ছি। তাপমাত্রা সর্বদা সারির সামনের দিকে নির্দেশ করে এবং আমরা এগিয়ে যাওয়ার সাথে সাথে উপাদানগুলি সামনে থেকে পপ করা হয়।
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
} এরপর যদি data_node NULL না হয় তাহলে আমরা নোডটিকে ডিলিট করা ডাটা x-এ সংরক্ষণ করি এবং টেম্প মুছে দিই যেটি গভীরতম নোড। ডেটা_নোড মান তারপর গভীরতম নোড মান দিয়ে প্রতিস্থাপিত হয় এবং গভীরতম নোডটি মুছে ফেলা হয়। নতুন নোডটি মুছে ফেলা এবং প্রতিস্থাপনের পরে ফাংশন থেকে ফিরে আসে।
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root, temp);
data_node->data = x;
} DeleteDeepest(struct Node* root,struct Node* deepestNode) ফাংশন পরীক্ষা করে যে পাস করা নোডটি আসলে গভীরতম নোড কিনা বা এটি ডান বা বাম চাইল্ড সবচেয়ে গভীরতম নোড কিনা সেক্ষেত্রে এটি প্যারেন্টকে মুছে ফেলার আগে চাইল্ড ভ্যালু নাল সেট করে দেয় যা গভীরতম নোড।
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
} উদাহরণ
বাইনারি ট্রি -
-এ মুছে ফেলার জন্য আমরা নিম্নলিখিত বাস্তবায়ন দেখি#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
struct Node* temp = new Node;
temp->data = data;
temp->leftChild = temp->rightChild = NULL;
return temp;
};
void inorder(struct Node* temp){
if (!temp)
return;
inorder(temp->leftChild);
cout << temp->data << " ";
inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
}
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* data_node = NULL;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
}
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root,temp);
data_node->data = x;
}
return root;
}
// Driver code
int main(){
struct Node* root = NewNode(12);
root->leftChild = NewNode(13);
root->leftChild->leftChild = NewNode(9);
root->leftChild->rightChild = NewNode(14);
root->rightChild = NewNode(11);
root->rightChild->leftChild = NewNode(17);
root->rightChild->rightChild = NewNode(10);
cout << "Inorder traversal before deletion : ";
inorder(root);
int data = 13;
root = deletion(root, data);
cout <<endl<< "Inorder traversal after deletion : ";
inorder(root);
return 0;
} আউটপুট
উপরের কোডটি নিম্নলিখিত আউটপুট −
তৈরি করবেInorder traversal before deletion : 9 13 14 12 17 11 10 Inorder traversal after deletion : 9 10 14 12 17 11
