Абход парадку ўзроўню з выкарыстаннем двух чэргаў


Узровень складанасці серада
Часта пытаюцца ў амазонка Паход 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

Аналіз складанасці

Складанасць часу

O (N), бо мы прайшлі па ўсіх вузлах дрэва. Такім чынам, складанасць часу лінейная.

Касмічная складанасць

O (N), як мы прайшлі праз вузлы ў дрэве. Мы таксама ўстаўлялі іх у чэргі, і, такім чынам, касмічная складанасць таксама лінейная.