C++ में बाइनरी ट्री को थ्रेडेड बाइनरी ट्री में बदलें | सेट 1 (क्यू का उपयोग करके)

इस ट्यूटोरियल में, हम एक प्रोग्राम पर चर्चा करेंगे जो क्यू डेटा संरचना का उपयोग करके बाइनरी ट्री को थ्रेडेड बाइनरी ट्री में परिवर्तित करता है।

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

उदाहरण

#include <iostream>
#include <queue>
using namespace std;

// थ्रेडेड ट्री के लिए नोड संरचना
struct Node {
    int key;
    Node *left, *right;
    bool isThreaded;
};

// इनऑर्डर पैटर्न को क्यू में डालना
void convert_queue(Node* root, std::queue<Node*>* q) {
    if (root == NULL)
        return;
    if (root->left)
        convert_queue(root->left, q);
    q->push(root);
    if (root->right)
        convert_queue(root->right, q);
}

// क्यू को पार करके थ्रेडेड ट्री बनाना
void create_threadedtree(Node* root, std::queue<Node*>* q) {
    if (root == NULL)
        return;
    if (root->left)
        create_threadedtree(root->left, q);
    q->pop();
    if (root->right)
        create_threadedtree(root->right, q);
    // यदि राइट पॉइंटर NULL है, तो इसे इनऑर्डर सक्सेसर पर इंगित करें
    else {
        root->right = q->front();
        root->isThreaded = true;
    }
}

// अंत में ट्री लेकर उसे थ्रेडेड में बदलना
void createThreaded(Node* root) {
    std::queue<Node*> q;
    convert_queue(root, &q);
    create_threadedtree(root, &q);
}

Node* leftMost(Node* root) {
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}

// थ्रेडेड ट्री का इनऑर्डर ट्रैवर्सल करना
void inOrder(Node* root) {
    if (root == NULL)
        return;
    Node* cur = leftMost(root);
    while (cur != NULL) {
        cout << cur->key << " ";
        // यदि थ्रेडेड नोड है, तो इनऑर्डर सक्सेसर पर जाएं
        if (cur->isThreaded)
            cur = cur->right;
        else
            cur = leftMost(cur->right);
    }
}

Node* newNode(int key) {
    Node* temp = new Node;
    temp->left = temp->right = NULL;
    temp->key = key;
    return temp;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    createThreaded(root);
    cout << "Traversing threaded tree:\n";
    inOrder(root);
    return 0;
}

आउटपुट

Traversing threaded tree: 4 2 5 1 6 3 7