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

C++ में सिंगल क्यू का उपयोग करके ट्री का जिग जैग लेवल ऑर्डर ट्रैवर्सल


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

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

C++ में सिंगल क्यू का उपयोग करके ट्री का जिग जैग लेवल ऑर्डर ट्रैवर्सल

आउटपुट -

3   1   7   2   8   9   5

सिंगल क्यू का उपयोग करके इस समस्या को हल करने के लिए, हम क्यू के साथ एक अतिरिक्त सेपरेशन फ्लैग और डायरेक्शन फ्लैग का उपयोग करेंगे।

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

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

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

void zigZagTraversal(struct Node* root, int n) {
    struct Node* queue[2 * n];
    int top = -1;
    int front = 1;
    queue[++top] = NULL;
    queue[++top] = root;
    queue[++top] = NULL;
    int prevFront = 0, count = 1;
    while (1) {
        struct Node* curr = queue[front];
        if (curr == NULL) {
            if (front == top)
                break;
            else {
                if (count % 2 == 0) {
                    for (int i = prevFront + 1; i < front; i++)
                        cout << queue[i]->data << "\t";
                } else {
                    for (int i = front - 1; i > prevFront; i--)
                        cout << queue[i]->data << "\t";
                }
                prevFront = front;
                count++;
                front++;
                queue[++top] = NULL;
                continue;
            }
        }
        if (curr->left != NULL)
            queue[++top] = curr->left;
        if (curr->right != NULL)
            queue[++top] = curr->right;
        front++;
    }
    if (count % 2 == 0) {
        for (int i = prevFront + 1; i < top; i++)
            cout << queue[i]->data << "\t";
    } else {
        for (int i = top - 1; i > prevFront; i--)
            cout << queue[i]->data << "\t";
    }
}

int main() {
    struct Node* root = insertNode(3);
    root->left = insertNode(1);
    root->right = insertNode(7);
    root->left->left = insertNode(5);
    root->left->right = insertNode(9);
    root->right->left = insertNode(8);
    root->right->right = insertNode(2);
    cout << "ट्री का जिग जैग ट्रैवर्सल है :\n";
    zigZagTraversal(root, 7);
    return 0;
}

आउटपुट

ट्री का जिग जैग ट्रैवर्सल है : 3   1   7   2   8   9   5
  1. C++ प्रोग्राम: लेवल ऑर्डर ट्रैवर्सल लाइन दर लाइन प्रिंट करना C++ प्रोग्राम: लेवल ऑर्डर ट्रैवर्सल लाइन दर लाइन प्रिंट करना

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

  1. डेटा स्ट्रक्चर में लेवल ऑर्डर ट्री ट्रैवर्सल डेटा स्ट्रक्चर में लेवल ऑर्डर ट्री ट्रैवर्सल

    इस खंड में हम बाइनरी सर्च ट्री के लिए लेवल-ऑर्डर ट्रैवर्सल तकनीक देखेंगे।मान लीजिए हमारे पास ऐसा एक ट्री है:ट्रैवर्सल क्रम इस प्रकार होगा: 10, 5, 16, 8, 15, 20, 23एल्गोरिदमlevelOrderTraverse(root): Begin    नोड्स स्टोर करने के लिए कतार que परिभाषित करें    रूट को que में इन्सर्ट

  1. पायथन में बाइनरी ट्री जिगजैग लेवल ऑर्डर ट्रैवर्सल पायथन में बाइनरी ट्री जिगजैग लेवल ऑर्डर ट्रैवर्सल

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जिगजैग लेवल ऑर्डर ट्रैवर्सल ढूंढना है। इसलिए पहली पंक्ति के लिए, बाएं से दाएं स्कैन करें, फिर दूसरी पंक्ति से दाएं से बाएं, फिर फिर से बाएं से दाएं और इसी तरह। इसलिए यदि ट्री इस तरह है -ट्रैवर्सल क्रम [[3],[20,9],[15,7]] होगा।इसे हल करने के लिए, हम इन चरणो