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

C++ में सभी नोड्स के लिए इनऑर्डर सक्सेसर भरना


इस समस्या में, हमें एक ट्री दिया गया है। संरचना में एक पॉइंटर next होता है। हमारा कार्य इस पॉइंटर को नोड के इनऑर्डर सक्सेसर के साथ भरना है।

struct node {
    int value;
    struct node* left;
    struct node* right;
    struct node* next;
}

सभी नेक्स्ट पॉइंटर्स NULL पर सेट हैं और हमें पॉइंटर को नोड के इनऑर्डर सक्सेसर पर सेट करना है।

इनऑर्डर ट्रैवर्सल - यह निम्न रूप में ट्रैवर्स करता है,

बायां नोड -> रूट नोड -> दायां नोड।

इनऑर्डर सक्सेसर - इनऑर्डर सक्सेसर वह नोड है जो ट्री के इनऑर्डर ट्रैवर्सल में वर्तमान नोड के बाद आता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

C++ में सभी नोड्स के लिए इनऑर्डर सक्सेसर भरना

इन-ऑर्डर ट्रैवर्सल है 7 8 3 5 9 1

प्रत्येक नोड को भरना:

5 का नेक्स्ट 9 है
8 का नेक्स्ट 3 है
7 का नेक्स्ट 8 है
3 का नेक्स्ट 5 है
9 का नेक्स्ट 1 है

इस समस्या को हल करने के लिए, हम ट्री को ट्रैवर्स करेंगे लेकिन रिवर्स इनऑर्डर फॉर्म में। फिर हम अंतिम विज़िट किए गए एलिमेंट को नंबर के नेक्स्ट में डालेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,

#include <iostream>
using namespace std;

struct node {
    int data;
    node *left;
    node *right;
    node *next;
};

node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    Node->next = NULL;
    return(Node);
}

void populateTree(node* pop) {
    static node *next = NULL;
    if (pop) {
        populateTree(pop->right);
        pop->next = next;
        next = pop;
        populateTree(pop->left);
    }
}

void printNext(node * root) {
    node *ptr = root->left->left;
    while(ptr) {
        cout << "Next of " << ptr->data << " is ";
        cout << (ptr->next ? ptr->next->data : -1) << endl;
        ptr = ptr->next;
    }
}

int main() {
    node *root = insertNode(15);
    root->left = insertNode(99);
    root->right = insertNode(1);
    root->left->left = insertNode(76);
    root->left->right = insertNode(31);
    cout << "इनऑर्डर सक्सेसर को नेक्स्ट में जोड़कर ट्री भर रहे हैं\n";
    populateTree(root);
    printNext(root);
    return 0;
}

आउटपुट

इनऑर्डर सक्सेसर को नेक्स्ट में जोड़कर ट्री भर रहे हैं

76 का नेक्स्ट 99 है
99 का नेक्स्ट 31 है
31 का नेक्स्ट 15 है
15 का नेक्स्ट 1 है
1 का नेक्स्ट -1 है
  1. C++ में बाइनरी ट्री के सभी इंटरनल नोड्स प्रिंट करना C++ में बाइनरी ट्री के सभी इंटरनल नोड्स प्रिंट करना

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

  1. C++ में दिए गए नोड से दूरी K पर सभी नोड्स प्रिंट करना C++ में दिए गए नोड से दूरी K पर सभी नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी ट्री, एक टारगेट नोड और एक पूर्णांक K दिया गया है। हमें ट्री के उन सभी नोड्स को प्रिंट करना है जो टारगेट नोड से दूरी K पर हैं। बाइनरी ट्री बाइनरी ट्री एक विशेष ट्री है जिसके प्रत्येक नोड में अधिकतम दो नोड्स होते हैं (एक/दो/कोई नहीं)। उदाहरण K = 2 टारगेट नोड: 9 आउटपुट

  1. C++ में लीफ नोड से दूरी K पर सभी नोड्स प्रिंट करना C++ में लीफ नोड से दूरी K पर सभी नोड्स प्रिंट करना

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