এই টিউটোরিয়ালে আমরা শিখব কিভাবে একটি বাইনারি ট্রিতে নোড ডিলিট করা যায়।
বাইনারি ট্রির নোডগুলো বাইনারি সার্চ ট্রির মত কোনো অর্ডার মেনে চলে না। তাহলে বাইনারি ট্রিতে একটি নোড ডিলিট করার পর নোডগুলো কীভাবে সাজাব?
আমরা ট্রির গভীরতম নোডটিকে ডিলিট হচ্ছে নোডটির সাথে রিপ্লেস করব। এবং তারপর গভীরতম নোডটিকে ট্রি থেকে ডিলিট করব।
সমস্যা সমাধানের ধাপগুলো:
বাইনারি নোড struct দিয়ে ট্রি ইনিশিয়ালাইজ করুন।
ট্রির নোডগুলো প্রিন্ট করার জন্য একটি ফাংশন (প্রি-অর্ডার, ইন-অর্ডার, পোস্ট-অর্ডার) লিখুন।
নোড ডিলিট করার জন্য একটি ফাংশন লিখুন।
ট্রি ট্রাভার্স করার জন্য একটি কিউ ইনিশিয়ালাইজ করুন।
কিউ খালি না হওয়া পর্যন্ত ইটারেট করুন।
দেওয়া কীવાલুয়ের নোডটি খুঁজে বের করুন এবং একটি ভেরিয়েবলে স্টোর করুন।
কিউ থেকে последнего নোডটি হলো গভীরতম নোড।
আরেকটি ফাংশন ব্যবহার করে গভীরতম নোড ডিলিট করুন।
কিউ ব্যবহার করে ট্রি ট্রাভার্স করুন।
যখন নোডটি পাওয়া যায়, সেটি ডিলিট করে রিটার্ন করুন।
ট্রি প্রিন্ট করে নোড ডিলিট হয়েছে কিনা তা দেখুন।
উদাহরণ
নিচে কোডটি দেওয়া হলো:
#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
উপসংহার
টিউটোরিয়াল সম্পর্কে কোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানান।
