Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी ट्री में डिलीशन (Deletion in Binary Tree)


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

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

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

इसके बाद हम newNode(int data) फंक्शन बनाते हैं जो एक int मान लेता है और इसे नोड के डेटा सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट Node का पॉइंटर वापस करता है। साथ ही, नव निर्मित नोड के बाएं और दाएं चाइल्ड को null पर सेट किया जाता है।

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

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

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

अब हम struct Node * प्रकार की एक क्यू बनाते हैं और इसे q नाम देते हैं और रूट नोड को q में पुश करते हैं। हम temp और data_node भी घोषित करते हैं जो Node के पॉइंटर हैं और data_node को NULL पर सेट करते हैं।

struct Node* temp; 
struct Node* data_node = NULL;

अगला, हम सबसे गहरे नोड को खोजने के लिए लेवल ऑर्डर ट्रैवर्सल करते हैं। व्हाइल लूप तब तक चलाया जाता है जब तक क्यू q खाली नहीं है। क्यू एक FIFO डेटा स्ट्रक्चर है इसलिए क्यू में अंतिम तत्व सबसे दाएं सबसे गहरा नोड होगा क्योंकि हम लेवल ऑर्डर ट्रैवर्सल द्वारा जा रहे हैं। temp हमेशा क्यू के फ्रंट को इंगित करता है और तत्व फ्रंट से पॉप होते हैं जैसे-जैसे हम आगे बढ़ते हैं।

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 में संग्रहीत करते हैं और temp को हटाते हैं जो सबसे गहरा नोड है। data_node का मान फिर सबसे गहरे नोड के मान से बदल दिया जाता है और सबसे गहरा नोड हटा दिया जाता है। डिलीशन और प्रतिस्थापन के बाद नया नोड फंक्शन से वापस किया जाता है।

if (data_node != NULL) { 
    int x = temp->data; 
    deleteDeepest(root, temp); 
    data_node->data = x; 
}

deleteDeepest(struct Node* root, struct Node* deepestNode) फंक्शन जांचता है कि पास किया गया नोड वास्तव में सबसे गहरा नोड है या इसका दायां या बायां चाइल्ड सबसे गहरा नोड है जिस स्थिति में यह पैरेंट को हटाने से पहले चाइल्ड मान को null पर सेट करता है जो 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

  1. C++ में बाइनरी ट्री में नोड का पोस्टऑर्डर सक्सेसर C++ में बाइनरी ट्री में नोड का पोस्टऑर्डर सक्सेसर

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

  1. C++ में बाइनरी ट्री में नोड का प्रीऑर्डर प्रीडिसेसर C++ में बाइनरी ट्री में नोड का प्रीऑर्डर प्रीडिसेसर

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

  1. C++ में बाइनरी ट्री में नोड का प्रीऑर्डर सक्सेसर C++ में बाइनरी ट्री में नोड का प्रीऑर्डर सक्सेसर

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