Обхождане на реда на ниво с помощта на две Опашки


Ниво на трудност M
Често задавани в Амазонка Екскурзия Microsoft Morgan Stanley
Двоично дърво Широчина Първо търсене Опашка Дърво Обръщане на дърво

Декларация за проблема

Проблемът „Обхождане на реда на ниво с помощта на две опашки“ гласи, че ви се дава двоично дърво, отпечатайте го обръщане на нареждане на ниво ред по ред.

Примери

Вход

Обхождане на реда на ниво с помощта на две Опашки

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 = нула и q2 = нула

Стъпка 2
Натиснете корена на опашка q1
q1 = 1 и q2 = нула

Стъпка 3
Повторете стъпки 4 и 5, докато някоя от опашките q1 или q2 не е празна

Стъпка 4 и 5
q1 = 2 и q2 = нула

Итерация 1
Печат 2.
q1 = нула и q2 = 2 -> 3
Прекъсване на реда за печат.

Итерация 2
Отпечатайте 2 и 3.
q1 = 4 -> 5 -> 6 и q2 = нула
Прекъсване на реда за печат.

Итерация 3
Отпечатайте 4, 5 и 6.
q1 = нула и q2 = нула
Прекъсване на реда за печат.

Тъй като и двете опашки се изпразват, така че спираме до тук.

код

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

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

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

НА), тъй като сме преминали през всички възли в дървото. По този начин сложността на времето е линейна.

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

НА), както сме преминали през възлите в дървото. Вмъквахме ги и в опашките и по този начин космическата сложност също е линейна.