এই টিউটোরিয়ালে, আমরা শিখব কিভাবে বাইনারি ট্রিতে একটি নোড মুছে ফেলতে হয়।
একটি বাইনারি গাছের নোডগুলি বাইনারি অনুসন্ধান গাছের মতো কোনো আদেশ অনুসরণ করে না। সুতরাং, বাইনারি ট্রিতে একটি নোড মুছে ফেলার পরে নোডগুলি কীভাবে সাজানো যায়?
ঠিক আছে, আমরা গাছের গভীরতম নোডটিকে মুছে ফেলা নোড দিয়ে প্রতিস্থাপন করব। এবং তারপর আমরা নোড থেকে গভীরতম নোড মুছে ফেলব।
আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
বাইনারি নোড স্ট্রাকট দিয়ে ট্রি শুরু করুন।
-
গাছের নোডগুলি প্রিন্ট করতে একটি ফাংশন (প্রি-অর্ডার, অর্ডার এবং পোস্টঅর্ডার) লিখুন।
-
নোড মুছে ফেলার জন্য একটি ফাংশন লিখুন।
-
গাছের মধ্য দিয়ে পুনরাবৃত্তি করার জন্য একটি সারি শুরু করুন।
-
সারি খালি না হওয়া পর্যন্ত পুনরাবৃত্তি করুন।
-
প্রদত্ত কী দিয়ে নোডটি সন্ধান করুন এবং এটি একটি ভেরিয়েবলে সংরক্ষণ করুন।
-
এবং সারির শেষ নোডটি হল গভীরতম নোড৷
৷
-
-
অন্য ফাংশন ব্যবহার করে গভীরতম নোড মুছুন।
-
গাছের মধ্য দিয়ে যাওয়ার জন্য সারি ব্যবহার করুন।
-
যখন আমরা নোড খুঁজে পাই তখন এটি মুছে দিন এবং ফেরত দিন
-
-
নোডটি মুছে ফেলা হয়েছে কিনা তা দেখতে গাছটি মুদ্রণ করুন৷
উদাহরণ
আসুন কোডটি দেখি।
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* node) {
if (node == NULL) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp == deleting_node) {
temp = NULL;
delete (deleting_node);
return;
}
if (temp->right) {
if (temp->right == deleting_node) {
temp->right = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->right);
}
}
if (temp->left) {
if (temp->left == deleting_node) {
temp->left = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->left);
}
}
}
}
Node* deleteNode(struct Node* root, int key) {
if (root == NULL){
return NULL;
}
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
return NULL;
}
else {
return root;
}
}
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
struct Node* key_node = NULL;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp->data == key) {
key_node = temp;
}
if (temp->left) {
nodes.push(temp->left);
}
if (temp->right) {
nodes.push(temp->right);
}
}
if (key_node != NULL) {
int deepest_node_data = temp->data;
deleteDeepestNode(root, temp);
key_node->data = deepest_node_data;
}
return root;
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << "Tree before deleting key: ";
inorder(root);
int key = 5;
root = deleteNode(root, key);
cout << "\nTree after deleting key: ";
inorder(root);
cout << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
Tree before deleting key: 3 2 4 1 8 6 9 5 7 Tree after deleting key: 3 2 4 1 8 6 9 7
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
