Прелазак редоследа нивоа помоћу два реда  


Ниво тешкоће Средњи
Често питани у амазонка Пешачење мицрософт Морган Стенли
Бинарно дрво Претрага у ширину Ред Дрво Прелазак дрвета

Изјава о проблему  

Проблем „Прелазак редоследа нивоа помоћу два реда чекања“ наводи да вам је дато бинарно стабло, испишите га прелазак редоследа нивоа линију по линију.

Примери  

Улазни

Прелазак редоследа нивоа помоћу два редаПин

5
11 42
7 9 8
12 23 52 3

Улазни
Прелазак редоследа нивоа помоћу два редаПин

1
2 3
4 5 6

Алгоритам за прелазак редоследа нивоа помоћу два реда  

Да бисмо исписали заокрет редоследа нивоа помоћу два реда, прво гурнемо први ниво (корен) у први ред, док искачемо ниво из првог реда, следећи ниво гурнемо у други ред и док искачемо ниво из другог реда, гурните следећи ниво у први ред. Понављајте овај поступак док било који од два реда није празан.

  1. Направите две репови к1 и к2.
  2. Гурните корен до к1.
  3. Иако к1 није празан или к2 није празан, поновите кораке 4 и 5.
  4. Иако к1 није празан, један по један уклањајте елементе из реда, одштампајте га и потискујте његову децу у к2. Одштампајте нови ред након што се ред испразни.
  5. Иако к2 није празан, један по један уклањајте елементе из реда, одштампајте га и потискујте његову децу у к1. Одштампајте нови ред након што се ред испразни.

Објашњење

Размотрите стабло у другом примеру горе.

Корак КСНУМКС
Направите два реда к1 и к2.
к1 = нула и к2 = нула

Види такође
Пронађите највећи вишекратник од 3

Корак КСНУМКС
Гурните корен у ред к1
к1 = 1 и к2 = нула

Корак КСНУМКС
Поновите кораке 4 и 5 док било који од редова к1 или к2 није празан

Корак 4 и 5
к1 = 2 и к2 = нула

понављање КСНУМКС
Принт 2.
к1 = нула и к2 = 2 -> 3
Прекид линије за испис.

понављање КСНУМКС
Штампај 2 и 3.
к1 = 4 -> 5 -> 6 и к2 = нула
Прекид линије за испис.

понављање КСНУМКС
Штампај 4, 5 и 6.
к1 = нула и к2 = нула
Прекид линије за испис.

Како се оба реда празне, тако се и овде заустављамо.

код  

Јава код за прелазак редоследа нивоа помоћу два реда

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

Ц ++ код за прелазак редоследа нивоа помоћу два реда

#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

Анализа сложености  

Сложеност времена

НА), пошто смо прешли преко свих чворова у дрвету. Стога је временска сложеност линеарна.

Види такође
Броји парове чији производи постоје у низу

Сложеност простора

НА), као што смо прешли преко чворова на дрвету. Такође смо их убацивали у редове и самим тим сложеност простора је такође линеарна.