Рубрики

Прохождение уровня ордера с изменением направления после каждых двух уровней

Для данного двоичного дерева выведите порядок обхода уровней таким образом, чтобы первые два уровня печатались слева направо, следующие два уровня печатались справа налево, затем следующие два слева направо и так далее. Таким образом, проблема состоит в том, чтобы поменять направление обхода порядка уровней двоичного дерева после каждых двух уровней.

Примеры:

Input: 
            1     
          /   \
        2       3
      /  \     /  \
     4    5    6    7
    / \  / \  / \  / \ 
   8  9 3   1 4  2 7  2
     /     / \    \
    16    17  18   19
Output:
1
2 3
7 6 5 4
2 7 2 4 1 3 9 8
16 17 18 19
In the above example, first two levels
are printed from left to right, next two
levels are printed from right to left,
and then last level is printed from 
left to right.

Подходить:
Мы используем очередь и стек здесь. Очередь используется для выполнения нормального уровня обхода заказа. Стек используется для изменения направления обхода после каждых двух уровней.
При выполнении нормального обхода порядка уровней первые два уровня уровней печатаются в тот момент, когда они выталкиваются из очереди. Для следующих двух уровней мы вместо печати узлов помещаем их в стек. Когда все узлы текущего уровня выдвинуты, мы печатаем узлы в стеке. Таким образом, мы печатаем узлы в порядке справа налево, используя стек. Теперь для следующих двух уровней мы снова выполняем нормальный обход порядка уровней для печати узлов слева направо. Затем для следующих двух узлов мы используем стек для достижения порядка справа налево.
Таким образом, мы добьемся желаемого изменения порядка следования уровней, используя очередь и стек.

C ++

// Программа CPP для печати зигзагообразного обхода
// в группах размером 2.
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

  
// Узел двоичного дерева

struct Node {

    struct Node* left;

    int data;

    struct Node* right;

};

  
/ * Функция для печати порядка уровней

   данное двоичное дерево. Направление печати

   прохождение порядка уровней изменений бинарного дерева

   после каждых двух уровней * /

void modifiedLevelOrder(struct Node* node)

{

    // для нулевого корня

    if (node == NULL)

        return;

  

    if (node->left == NULL && node->right == NULL) {

        cout << node->data;

        return;

    }

  

    // Поддерживаем очередь для нормального уровня обхода заказа

    queue<Node*> myQueue;

  

    / * Поддержка стека для печати узлов в обратном порядке

       заказ после того, как они выскочили из очереди. * /

    stack<Node*> myStack;

  

    struct Node* temp = NULL;

  

    // sz используется для хранения количества узлов на уровне

    int sz;

  

    // Используется для изменения направления обхода ордера уровня

    int ct = 0;

  

    // Используется для изменения направления обхода ордера уровня

    bool rightToLeft = false;

  

    // толкаем корневой узел в очередь

    myQueue.push(node);

  

    // Запускаем цикл while, пока очередь не опустеет

    while (!myQueue.empty()) {

        ct++;

  

        sz = myQueue.size();

  

        // Осуществляем нормальный уровень обхода порядка

        for (int i = 0; i < sz; i++) {

            temp = myQueue.front();

            myQueue.pop();

  

            / * Для печати узлов слева направо,

            просто распечатать узлы в том порядке, в котором

            они выталкиваются из очереди. * /

            if (rightToLeft == false

                cout << temp->data << " ";            

  

            / * Для печати узлов справа налево,

            поместите узлы в стек вместо их печати. * /

            else 

                myStack.push(temp);            

  

            if (temp->left)

                myQueue.push(temp->left);

  

            if (temp->right)

                myQueue.push(temp->right);

        }

  

        if (rightToLeft == true) {

  

            // для печати узлов по порядку

            // справа налево

            while (!myStack.empty()) {

                temp = myStack.top();

                myStack.pop();

  

                cout << temp->data << " ";

            }

        }

  

        / * Изменить направление печати

        узлы после каждых двух уровней. * /

        if (ct == 2) {

            rightToLeft = !rightToLeft;

            ct = 0;

        }

  

        cout << "\n";

    }

}

  
// Сервисная функция для создания нового узла дерева

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим бинарное дерево

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->left->left->left = newNode(8);

    root->left->left->right = newNode(9);

    root->left->right->left = newNode(3);

    root->left->right->right = newNode(1);

    root->right->left->left = newNode(4);

    root->right->left->right = newNode(2);

    root->right->right->left = newNode(7);

    root->right->right->right = newNode(2);

    root->left->right->left->left = newNode(16);

    root->left->right->left->right = newNode(17);

    root->right->left->right->left = newNode(18);

    root->right->right->left->right = newNode(19);

  

    modifiedLevelOrder(root);

  

    return 0;

}

Джава

// Java-программа для печати зигзагообразного обхода
// в группах размером 2.

import java.util.*;

  

class GFG 

{

  
// Узел двоичного дерева

static class Node 

{

    Node left;

    int data;

    Node right;

};

  
/ * Функция для печати порядка уровней
данное двоичное дерево. Направление печати
прохождение порядка уровней изменений бинарного дерева
после каждых двух уровней * /

static void modifiedLevelOrder(Node node)

{

    // для нулевого корня

    if (node == null)

        return;

  

    if (node.left == null && node.right == null

    {

        System.out.print(node.data);

        return;

    }

  

    // Поддерживаем очередь для нормального уровня обхода заказа

    Queue<Node> myQueue = new LinkedList<>();

  

    / * Поддержка стека для печати узлов в обратном порядке

    заказ после того, как они выскочили из очереди. * /

    Stack<Node> myStack = new Stack<>();

  

    Node temp = null;

  

    // sz используется для хранения

    // количество узлов в уровне

    int sz;

  

    // Используется для изменения направления

    // прохождения уровня порядка

    int ct = 0;

  

    // Используется для изменения направления

    // прохождения уровня порядка

    boolean rightToLeft = false;

  

    // толкаем корневой узел в очередь

    myQueue.add(node);

  

    // Запускаем цикл while, пока очередь не опустеет

    while (!myQueue.isEmpty()) 

    {

        ct++;

  

        sz = myQueue.size();

  

        // Осуществляем нормальный уровень обхода порядка

        for (int i = 0; i < sz; i++)

        {

            temp = myQueue.peek();

            myQueue.remove();

  

            / * Для печати узлов слева направо,

            просто распечатать узлы в том порядке, в котором

            они выталкиваются из очереди. * /

            if (rightToLeft == false

                System.out.print(temp.data + " ");         

  

            / * Для печати узлов справа налево,

            поместите узлы в стек вместо их печати. * /

            else

                myStack.push(temp);         

  

            if (temp.left != null)

                myQueue.add(temp.left);

  

            if (temp.right != null)

                myQueue.add(temp.right);

        }

  

        if (rightToLeft == true

        {

  

            // для печати узлов по порядку

            // справа налево

            while (!myStack.isEmpty()) 

            {

                temp = myStack.peek();

                myStack.pop();

  

                System.out.print(temp.data + " ");

            }

        }

  

        / * Изменить направление печати

        узлы после каждых двух уровней. * /

        if (ct == 2

        {

            rightToLeft = !rightToLeft;

            ct = 0;

        }

  

        System.out.print("\n");

    }

}

  
// Сервисная функция для создания нового узла дерева

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

  
// Код драйвера

public static void main(String[] args) 

{

    // Давайте создадим бинарное дерево

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(6);

    root.right.right = newNode(7);

    root.left.left.left = newNode(8);

    root.left.left.right = newNode(9);

    root.left.right.left = newNode(3);

    root.left.right.right = newNode(1);

    root.right.left.left = newNode(4);

    root.right.left.right = newNode(2);

    root.right.right.left = newNode(7);

    root.right.right.right = newNode(2);

    root.left.right.left.left = newNode(16);

    root.left.right.left.right = newNode(17);

    root.right.left.right.left = newNode(18);

    root.right.right.left.right = newNode(19);

  

    modifiedLevelOrder(root);

}
}

  
// Этот код предоставлен 29AjayKumar

C #

// C # программа для печати зигзагообразного обхода
// в группах размером 2.

using System;

using System.Collections.Generic;

      

class GFG 

{

  
// Узел двоичного дерева

public class Node 

{

    public Node left;

    public int data;

    public Node right;

};

  
/ * Функция для печати порядка уровней
данное двоичное дерево. Направление печати
прохождение порядка уровней изменений бинарного дерева
после каждых двух уровней * /

static void modifiedLevelOrder(Node node)

{

    // для нулевого корня

    if (node == null)

        return;

  

    if (node.left == null && 

        node.right == null

    {

        Console.Write(node.data);

        return;

    }

  

    // Поддерживать очередь для

    // обход нормального уровня

    Queue<Node> myQueue = new Queue<Node>();

  

    / * Поддерживать стек для печати узлов

    в обратном порядке после того, как они

    выскочил из очереди. * /

    Stack<Node> myStack = new Stack<Node>();

  

    Node temp = null;

  

    // sz используется для хранения

    // количество узлов в уровне

    int sz;

  

    // Используется для изменения направления

    // прохождения уровня порядка

    int ct = 0;

  

    // Используется для изменения направления

    // прохождения уровня порядка

    bool rightToLeft = false;

  

    // толкаем корневой узел в очередь

    myQueue.Enqueue(node);

  

    // Запускаем цикл while

    // пока очередь не опустела

    while (myQueue.Count != 0) 

    {

        ct++;

  

        sz = myQueue.Count;

  

        // Осуществляем нормальный уровень обхода порядка

        for (int i = 0; i < sz; i++)

        {

            temp = myQueue.Peek();

            myQueue.Dequeue();

  

            / * Для печати узлов слева направо,

            просто распечатать узлы в том порядке, в котором

            они выталкиваются из очереди. * /

            if (rightToLeft == false

                Console.Write(temp.data + " ");         

  

            / * Для печати узлов справа налево,

               толкать узлы в стек вместо

               печать их. * /

            else

                myStack.Push(temp);         

  

            if (temp.left != null)

                myQueue.Enqueue(temp.left);

  

            if (temp.right != null)

                myQueue.Enqueue(temp.right);

        }

  

        if (rightToLeft == true

        {

  

            // для печати узлов по порядку

            // справа налево

            while (myStack.Count != 0) 

            {

                temp = myStack.Peek();

                myStack.Pop();

  

                Console.Write(temp.data + " ");

            }

        }

  

        / * Изменить направление печати

        узлы после каждых двух уровней. * /

        if (ct == 2) 

        {

            rightToLeft = !rightToLeft;

            ct = 0;

        }

        Console.Write("\n");

    }

}

  
// Сервисная функция для создания нового узла дерева

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

  
// Код драйвера

public static void Main(String[] args) 

{

    // Давайте создадим бинарное дерево

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(6);

    root.right.right = newNode(7);

    root.left.left.left = newNode(8);

    root.left.left.right = newNode(9);

    root.left.right.left = newNode(3);

    root.left.right.right = newNode(1);

    root.right.left.left = newNode(4);

    root.right.left.right = newNode(2);

    root.right.right.left = newNode(7);

    root.right.right.right = newNode(2);

    root.left.right.left.left = newNode(16);

    root.left.right.left.right = newNode(17);

    root.right.left.right.left = newNode(18);

    root.right.right.left.right = newNode(19);

  

    modifiedLevelOrder(root);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

1 
2 3 
7 6 5 4 
2 7 2 4 1 3 9 8 
16 17 18 19

Сложность времени: каждый узел обходится не более двух раз при выполнении обхода уровня, поэтому сложность времени будет O (n).

Подход 2:
Мы используем очередь и стек здесь, но по-другому. Использование макросов #define ChangeDirection (Dir) ((Dir) = 1 — (Dir)). В следующей реализации указывается порядок операций push как в очереди, так и в стеке.
Таким образом, мы добьемся желаемого изменения порядка следования уровней, используя очередь и стек.

// Программа CPP для печати зигзагообразного обхода
// в группах размером 2.
#include <iostream>
#include <stack>
#include <queue>

  

using namespace std;

  
#define LEFT 0
#define RIGHT 1
#define ChangeDirection(Dir) ((Dir) = 1 - (Dir))

  
// Узел двоичного дерева

struct node 

{

    int data;

    struct node *left, *right;

};

  
// Сервисная функция для создания нового узла дерева

node* newNode(int data) 

    node* temp = new node; 

    temp->data = data; 

    temp->left = temp->right = NULL; 

    return temp; 

  
/ * Функция для печати порядка уровней

   данное двоичное дерево. Направление печати

   прохождение порядка уровней изменений бинарного дерева

   после каждых двух уровней * /

void modifiedLevelOrder(struct node *root)

{

    if (!root)

        return ;

      

    int dir = LEFT;

    struct node *temp;

    queue <struct node *> Q;

    stack <struct node *> S;

  

    S.push(root);

      

    // Запускаем цикл while, пока очередь не опустеет

    while (!Q.empty() || !S.empty())

    {

        while (!S.empty())

        {

            temp = S.top();

            S.pop();

            cout << temp->data << " ";

              

            if (dir == LEFT) {

                if (temp->left)

                    Q.push(temp->left);

                if (temp->right)

                    Q.push(temp->right);

            

            / * Для печати узлов справа налево,

            поместите узлы в стек вместо их печати. * /

            else {

                if (temp->right)

                    Q.push(temp->right);

                if (temp->left)

                    Q.push(temp->left);

            }

        }

          

        cout << endl;

          

            // для печати узлов по порядку

            // справа налево

        while (!Q.empty())

        {

            temp = Q.front();

            Q.pop();

            cout << temp->data << " ";

              

            if (dir == LEFT) {

                if (temp->left)

                    S.push(temp->left);

                if (temp->right)

                    S.push(temp->right);

            } else {

                if (temp->right)

                    S.push(temp->right);

                if (temp->left)

                    S.push(temp->left);

            }

        }

        cout << endl;

  

        // Изменить направление обхода.

        ChangeDirection(dir);

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

    // Давайте создадим бинарное дерево

    node* root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

    root->left->left = newNode(4); 

    root->left->right = newNode(5); 

    root->right->left = newNode(6); 

    root->right->right = newNode(7); 

    root->left->left->left = newNode(8); 

    root->left->left->right = newNode(9); 

    root->left->right->left = newNode(3); 

    root->left->right->right = newNode(1); 

    root->right->left->left = newNode(4); 

    root->right->left->right = newNode(2); 

    root->right->right->left = newNode(7); 

    root->right->right->right = newNode(2); 

    root->left->right->left->left = newNode(16); 

    root->left->right->left->right = newNode(17); 

    root->right->left->right->left = newNode(18); 

    root->right->right->left->right = newNode(19); 

  

    modifiedLevelOrder(root); 

  

    return 0; 

}

Выход:

1 
2 3 
7 6 5 4 
2 7 2 4 1 3 9 8 
16 17 18 19

Сложность времени: каждый узел также пройден дважды. Там сложность времени все еще O (n).

Рекомендуемые посты:

Прохождение уровня ордера с изменением направления после каждых двух уровней

0.00 (0%) 0 votes