सी ++ में बाइनरी ट्री में हटाना?

हटाए गए मोड को नीचे और सबसे दाहिनी ओर नोड से बदलकर हटाना किया जाना है।

आइए पहले उस संरचना को परिभाषित करें जो एक ट्री नोड का प्रतिनिधित्व करेगी जिसमें डेटा और उसके बाएँ और दाएँ नोड बच्चे शामिल हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह एक रूट नोड है अन्यथा एक चाइल्ड नोड है।

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

इसके बाद हम अपना नया नोड (इंट डेटा) फ़ंक्शन बनाते हैं जो एक इंट मान लेता है और इसे नोड के डेटा सदस्य को असाइन करता है। फ़ंक्शन पॉइंटर को बनाए गए स्ट्रक्चर नोड पर लौटाता है। साथ ही, नव निर्मित नोड के बाएँ और दाएँ बच्चे को शून्य पर सेट किया गया है।

struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

दिए गए डेटा मान के साथ नोड को हटाने के लिए विलोपन (स्ट्रक्चर नोड * रूट, इंट डेटा) फ़ंक्शन का उपयोग किया जाता है। यह रूट नोड और डेटा मान को खोजने और हटाने के लिए लेता है। यदि कोई चाइल्ड नोड नहीं है और डेटा मान रूट के डेटा मान के बराबर है तो नल वापस कर दिया जाता है अन्यथा रूट नोड वापस आ जाता है।

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;
   }

अब हम टाइप स्ट्रक्चर नोड * की एक कतार बनाते हैं और इसे q नाम देते हैं और रूट नोड को q पर धकेलते हैं। हम अस्थायी और डेटा_नोड भी घोषित करते हैं जो नोड की ओर इशारा करते हैं और डेटा_नोड को NULL के रूप में सेट करते हैं।

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);
}

अगला यदि data_node NULL नहीं है, तो हम हटाए गए डेटा को x में संग्रहीत करने के लिए नोड को संग्रहीत करते हैं और उस अस्थायी को हटाते हैं जो सबसे गहरा नोड है। फिर data_node मान को सबसे गहरे नोड मान से बदल दिया जाता है और सबसे गहरे नोड को हटा दिया जाता है। नया नोड हटाने और बदलने के बाद फ़ंक्शन से वापस आ जाता है।

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