इस ट्यूटोरियल में, हम सीखेंगे कि बाइनरी ट्री में नोड को कैसे हटाया जाए।
बाइनरी ट्री में नोड्स बाइनरी सर्च ट्री की तरह किसी क्रम का पालन नहीं करते हैं। तो बाइनरी ट्री में नोड हटाने के बाद नोड्स को कैसे व्यवस्थित करें?
खैर, हम ट्री के सबसे गहरे नोड को हटाए जा रहे नोड से बदल देंगे। और फिर हम सबसे गहरे नोड को नोड से हटा देंगे।
समस्या को हल करने के चरण देखते हैं।
बाइनरी नोड स्ट्रक्चर के साथ ट्री को इनिशियलाइज़ करें।
ट्री के नोड्स प्रिंट करने के लिए एक फंक्शन लिखें (प्रीऑर्डर, इनऑर्डर, और पोस्टऑर्डर)।
नोड हटाने के लिए एक फंक्शन लिखें।
ट्री के माध्यम से पुनरावृति करने के लिए एक क्यू इनिशियलाइज़ करें।
क्यू खाली होने तक पुनरावृति करें।
दिए गए की के साथ नोड खोजें और इसे एक वेरिएबल में स्टोर करें।
और क्यू से अंतिम नोड सबसे गहरा नोड है।
दूसरे फंक्शन का उपयोग करके सबसे गहरे नोड को हटाएं।
ट्री के माध्यम से ट्रैवर्स करने के लिए क्यू का उपयोग करें।
जब हमें नोड मिले तो इसे हटाएं और लौटाएं।
ट्री प्रिंट करें ताकि पता चल सके कि नोड हटाया गया है या नहीं।
उदाहरण
कोड देखते हैं।
#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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें कमेंट सेक्शन में बताएं।
