Մակարդակի պատվերի անցում ՝ օգտագործելով երկու Հերթեր


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Զբոսանք Microsoft Morgan Stanley
Երկուական ծառ Լայնության առաջին որոնում Հերթ ծառ Reeառի անցում

Խնդիրի հայտարարություն

«Մակարդակի կարգի անցում ՝ օգտագործելով երկու հերթում» խնդիրը ասում է, որ ձեզ տրվում է երկուական ծառ, տպեք այն մակարդակի կարգի անցում տող առ տող.

Օրինակներ

Մուտքային

Մակարդակի պատվերի անցում ՝ օգտագործելով երկու Հերթեր

5
11 42
7 9 8
12 23 52 3

Մուտքային
Մակարդակի պատվերի անցում ՝ օգտագործելով երկու Հերթեր

1
2 3
4 5 6

Մակարդակի կարգի անցման ալգորիթմ `օգտագործելով երկու հերթ

Մակարդակի կարգի անցումը երկու հերթի միջոցով տպելու համար մենք նախ մղում ենք առաջին մակարդակը (արմատը) առաջին հերթին, իսկ առաջին հերթից մակարդակ դուրս գալուց հետո մենք հաջորդ մակարդակը մղում ենք երկրորդ հերթի և երկրորդ հերթից մակարդակ դուրս գալիս, հաջորդ մակարդակը մղել առաջին հերթի: Կրկնեք այս գործընթացը մինչև երկու հերթերից որևէ մեկը դատարկ չլինի:

  1. Ստեղծեք երկուս պոչերը q1 և q2.
  2. Արմատը մղեք դեպի q1:
  3. Չնայած կամ q1 դատարկ չէ, կամ q2 դատարկ չէ, կրկնում ենք 4-րդ և 5-րդ քայլերը:
  4. Չնայած q1- ը դատարկ չէ, հերթով տարրերը մեկ առ մեկ հանում են, տպում և երեխաներին մղում դեպի q2: Հերթը դատարկվելուց հետո տպեք նոր տող:
  5. Չնայած q2- ը դատարկ չէ, հերթով տարրերը մեկ առ մեկ հանում են, տպում և երեխաներին մղում դեպի q1: Հերթը դատարկվելուց հետո տպեք նոր տող:

բացատրություն

Հաշվի առեք ծառը վերը նշված երկրորդ օրինակում:

Քայլ 1
Ստեղծեք երկու հերթեր q1 և q2:
q1 = null և q2 = null

Քայլ 2
Արմատը մղեք դեպի q1 հերթ
q1 = 1 և q2 = null

Քայլ 3
Կրկնեք 4-րդ և 5-րդ քայլերը, մինչդեռ q1 կամ q2 հերթերից որևէ մեկը դատարկ չէ

Քայլ 4 և 5
q1 = 2 և q2 = null

բազմակրկնություն 1
Տպել 2.
q1 = null և q2 = 2 -> 3
Տպել գծի ընդմիջում:

բազմակրկնություն 2
Տպել 2-ը և 3-ը:
q1 = 4 -> 5 -> 6 և q2 = null
Տպել գծի ընդմիջում:

բազմակրկնություն 3
Տպիր 4, 5 և 6:
q1 = null և q2 = null
Տպել գծի ընդմիջում:

Քանի որ երկու հերթերն էլ դատարկվում են, մենք կանգ ենք առնում այստեղ:

Կոդ

Մակարդակի պատվերի անցման Java կոդ ՝ օգտագործելով երկու հերթ

import java.util.LinkedList;
import java.util.Queue;

class LevelOrderTraversalUsingTwoQueues {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void levelOrderTraversal(Node root) {
        if (root == null) {
            System.out.println();
            return;
        }

        // create two queues q1 and q2
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        // push the root to queue q1
        q1.add(root);
        
        // while either q1 is not empty or q2 is not empty
        while (!q1.isEmpty() || !q2.isEmpty()) {
            // Pop out a level from q1, print it and push next level to q2
            while (!q1.isEmpty()) {
                // remove a node from q1
                Node curr = q1.poll();
                // print the node
                System.out.print(curr.data + " ");
                // add its children to queue q2
                if (curr.left != null)
                    q2.add(curr.left);
                if (curr.right != null)
                    q2.add(curr.right);
            }
            // print line break
            System.out.println();
            
            // Pop out a level from queue q2 and push next level to q1
            while (!q2.isEmpty()) {
                // remove a node from q2
                Node curr = q2.poll();
                // print the node
                System.out.print(curr.data + " ");
                // add its children to queue q2
                if (curr.left != null)
                    q1.add(curr.left);
                if (curr.right != null)
                    q1.add(curr.right);
            }
            // print line break
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(5);
        root1.left = new Node(11);
        root1.right = new Node(42);
        root1.left.left = new Node(7);
        root1.right.left = new Node(9);
        root1.right.right = new Node(8);
        root1.left.left.left = new Node(12);
        root1.left.left.right = new Node(23);
        root1.right.right.left = new Node(52);
        root1.right.right.right = new Node(3);

        levelOrderTraversal(root1);

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);

        levelOrderTraversal(root2);
    }
}
5
11 42
7 9 8
12 23 52 3

1
2 3
4 5 6

Մակարդակի պատվերի անցման համար C ++ կոդ ՝ օգտագործելով երկու հերթ

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

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

void levelOrderTraversal(Node *root) {
    if (root == NULL) {
        cout<<endl;
        return;
    }
    
    // create two queues q1 and q2
    queue<Node *> q1;
    queue<Node *> q2;
    // push the root to queue q1
    q1.push(root);
    
    // while either q1 is not empty or q2 is not empty
    while (!q1.empty() || !q2.empty()) {
        // Pop out a level from q1, print it and push next level to q2
        while (!q1.empty()) {
            // remove a node from q1
            Node *curr = q1.front();
            q1.pop();
            // print the node
            cout<<curr->data<<" ";
            // add its children to queue q2
            if (curr->left != NULL)
                q2.push(curr->left);
            if (curr->right != NULL)
                q2.push(curr->right);
        }
        // print line break
        cout<<endl;
        
        // Pop out a level from queue q2 and push next level to q1
        while (!q2.empty()) {
            // remove a node from q2
            Node *curr = q2.front();
            q2.pop();
            // print the node
            cout<<curr->data<<" ";
            // add its children to queue q2
            if (curr->left != NULL)
                q1.push(curr->left);
            if (curr->right != NULL)
                q1.push(curr->right);
        }
        // print line break
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(5);
    root1->left = newNode(11);
    root1->right = newNode(42);
    root1->left->left = newNode(7);
    root1->right->left = newNode(9);
    root1->right->right = newNode(8);
    root1->left->left->left = newNode(12);
    root1->left->left->right = newNode(23);
    root1->right->right->left = newNode(52);
    root1->right->right->right = newNode(3);

    levelOrderTraversal(root1);

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);

    levelOrderTraversal(root2);
    
    return 0;
}
5
11 42
7 9 8
12 23 52 3

1
2 3
4 5 6

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք անցել ենք ծառի բոլոր հանգույցները: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք անցել ենք ծառի հանգույցների վրայով: Մենք դրանք տեղադրում էինք հերթերի մեջ և, այդպիսով, տիեզերական բարդությունը նույնպես գծային է: