কিউ ব্যবহার করে বাইনারি ট্রি কে থ্রেডেড বাইনারি ট্রি-তে রূপান্তর C++-এ | সেট ১

এই টিউটোরিয়ালে আমরা কিউ ডেটা স্ট্রাকচার ব্যবহার করে একটি বাইনারি ট্রিকে থ্রেডেড বাইনারি ট্রি-তে রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব।

এখানে একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হল সেই নির্দিষ্ট বাইনারি ট্রিকে একটি থ্রেডেড বাইনারি ট্রি-তে রূপান্তর করা কিউ ডেটা স্ট্রাকচারের সাহায্যে দ্রুত ইনঅর্ডার ট্রভারসালের জন্য অতিরিক্ত পথ যোগ করে।

উদাহরণ

#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