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