Рубрики

Печатать уровень обхода заказа построчно | Комплект 1

Деревья

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

Например, рассмотрим следующее дерево

Example 1:

Output for above tree should be
20
8 22
4 12
10 14

Example 2:
          1
       /     \
      2       3
    /   \       \
   4     5       6
        /  \     /
       7    8   9
Output for above tree should be
1
2 3
4 5 6
7 8 9<

Обратите внимание, что это отличается от простого обхода порядка уровней, когда нам нужно печатать все узлы вместе. Здесь нам нужно напечатать узлы разных уровней в разных строках.

Простое решение состоит в том, чтобы напечатать, используя рекурсивную функцию, обсужденную в посте прохождения порядка уровней, и печатать новую строку после каждого вызова printGivenLevel () .

C ++

/ * Функция построчного обхода порядка печати по дереву * /

void printLevelOrder(struct node* root)

{

    int h = height(root);

    int i;

    for (i=1; i<=h; i++)

    {

        printGivenLevel(root, i);

        printf("\n");

    }

}

  
/ * Печать узлов на заданном уровне * /

void printGivenLevel(struct node* root, int level)

{

    if (root == NULL)

        return;

    if (level == 1)

        printf("%d ", root->data);

    else if (level > 1)

    {

        printGivenLevel(root->left, level-1);

        printGivenLevel(root->right, level-1);

    }

}

Джава

/ * Функция построчного обхода порядка печати по дереву * /

static void printLevelOrder(Node root)

{

    int h = height(root);

    int i;

    for (i=1; i<=h; i++)

    {

        printGivenLevel(root, i);

        System.out.println();

    }

}
/ * Печать узлов на заданном уровне * /

void printGivenLevel(Node root, int level)

{

    if (root == null)

        return;

    if (level == 1)

        System.out.println(root.data);

    else if (level > 1)

    {

        printGivenLevel(root.left, level-1);

        printGivenLevel(root.right, level-1);

    }

}

python3

# Python3 программа для вышеуказанного подхода

  

def printlevelorder(root):

    h = height(root)

    for i in range(1, h + 1):

        givenspirallevel(root, i)

  

def printGivenLevel(root, level):

    if root is None:

        return root

      

    if level == 1:

        print(root.val, end = ' ')

    elif level > 1:

        printGivenLevel(root.left, level - 1)

        printGivenLevel(root.right, level - 1)

  
# Этот код предоставлен Правином Кумаром

C #

/ * Печать узлов на заданном уровне * /

static void printGivenLevel(Node root, int level)

{

    if (root == null)

        return;

    if (level == 1)

        Console.WriteLine(root.data);

    else if (level > 1)

    {

        printGivenLevel(root.left, level-1);

        printGivenLevel(root.right, level-1);

    }

}

Временная сложность вышеуказанного решения составляет O (n 2 )

Как изменить итеративный обход порядка уровней (метод 2 этого ) для уровней строка за строкой?
Идея похожа на этот пост. Мы считаем узлы на текущем уровне. И для каждого узла мы ставим его потомков в очередь.

C ++

/ * Итеративная программа для печати уровней построчно * /
#include <iostream> 
#include <queue> 

using namespace std; 

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

struct node 

{ 

    struct node *left; 

    int data; 

    struct node *right; 

}; 

  
// Итеративный метод для прохождения уровня порядка
// построчно

void printLevelOrder(node *root) 

{ 

    // Базовый вариант

    if (root == NULL) return; 

  

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

    queue<node *> q; 

  

    // ставим в очередь Root и инициализируем высоту

    q.push(root); 

  

    while (q.empty() == false) 

    { 

        // nodeCount (размер очереди) указывает число

        // узлов на текущем уровне.

        int nodeCount = q.size(); 

  

        // Выводим из очереди все узлы текущего уровня и

        // ставим в очередь все узлы следующего уровня

        while (nodeCount > 0)

        { 

            node *node = q.front(); 

            cout << node->data << " "; 

            q.pop(); 

            if (node->left != NULL) 

                q.push(node->left); 

            if (node->right != NULL) 

                q.push(node->right); 

            nodeCount--; 

        } 

        cout << endl; 

    } 

} 

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

node* newNode(int data) 

{ 

    node *temp = new node; 

    temp->data = data; 

    temp->left = NULL; 

    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->right = newNode(6); 

  

    printLevelOrder(root); 

    return 0; 

}

Джава

/ * Итеративная Java-программа для печати уровней построчно * /

  

import java.util.LinkedList;

import java.util.Queue;

  

public class LevelOrder 

{

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

    static class Node

    {

        int data;

        Node left;

        Node right;

          

        // конструктор

        Node(int data){

            this.data = data;

            left = null;

            right =null;

        }

    }

      

    // Итеративный метод для прохождения уровня по порядку построчно

    static void printLevelOrder(Node root)

    {

        // Базовый вариант

        if(root == null)

            return;

          

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

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

          

        // ставим в очередь Root и инициализируем высоту

        q.add(root);

          

          

        while(true)

        {

              

            // nodeCount (размер очереди) указывает количество узлов

            // на текущем уровне.

            int nodeCount = q.size();

            if(nodeCount == 0)

                break;

              

            // Удалить все узлы текущего уровня и поставить все в очередь

            // узлы следующего уровня

            while(nodeCount > 0)

            {

                Node node = q.peek();

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

                q.remove();

                if(node.left != null)

                    q.add(node.left);

                if(node.right != null)

                    q.add(node.right);

                nodeCount--;

            }

            System.out.println();

        }

    }

      

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

    public static void main(String[] args) 

    {

        // Давайте создадим двоичное дерево, показанное на диаграмме выше

       / * 1

                   / /

                  2 3

                ///

               4 5 6

        * /

          

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

        root.left.left = new Node(4);

        root.left.right = new Node(5);

        root.right.right = new Node(6);

          

        printLevelOrder(root);

  

    }

  
}
// Этот код предоставлен Sumit Ghosh

python3

# Python3 программа для вышеуказанного подхода

class newNode:

    def __init__(self, data):

        self.val = data 

        self.left = None

        self.right = None

          
# Итеративный метод для прохождения уровня порядка
# построчно

def printLevelOrder(root):

      

    # Базовый вариант

    if root is None:

        return

    # Создать пустую очередь для прохождения порядка уровней

    q = []

      

    # Ставить в корень и инициализировать высоту

    q.append(root)

          

    while q:

      

        # nodeCount (размер очереди) указывает число

        # узлов на текущем уровне.

        count = len(q)

          

        # Отключить все узлы текущего уровня и

        # Поставить в очередь все узлы следующего уровня

        while count > 0:

            temp = q.pop(0)

            print(temp.val, end = ' ')

            if temp.left:

                q.append(temp.left)

            if temp.right:

                q.append(temp.right)

  

            count -= 1

        print(' ')

          
Код водителя

root = newNode(1); 

root.left = newNode(2); 

root.right = newNode(3); 

root.left.left = newNode(4); 

root.left.right = newNode(5); 

root.right.right = newNode(6); 

  
printLevelOrder(root);

  
# Этот код предоставлен Правином Кумаром

C #

/ * Итеративная программа на C # для печати
уровни построчно * /

using System;

using System.Collections.Generic;

  

public class LevelOrder 

{ 

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

    class Node 

    { 

        public int data; 

        public Node left; 

        public Node right; 

          

        // конструктор

        public Node(int data)

        { 

            this.data = data; 

            left = null; 

            right =null; 

        } 

    } 

      

    // Итеративный метод, чтобы сделать порядок уровней

    // обход за строкой

    static void printLevelOrder(Node root) 

    { 

        // Базовый вариант

        if(root == null) 

            return; 

          

        // Создать пустую очередь для уровня

        // заказываем tarversal

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

          

        // ставим в очередь Root и инициализируем высоту

        q.Enqueue(root); 

          

        while(true) 

        { 

              

            // nodeCount (размер очереди) указывает

            // количество узлов на текущем уровне.

            int nodeCount = q.Count; 

            if(nodeCount == 0) 

                break; 

              

            // Удаление всех узлов текущего уровня

            // и ставим в очередь все узлы следующего уровня

            while(nodeCount > 0) 

            { 

                Node node = q.Peek(); 

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

                q.Dequeue(); 

                if(node.left != null) 

                    q.Enqueue(node.left); 

                if(node.right != null) 

                    q.Enqueue(node.right); 

                nodeCount--; 

            } 

            Console.WriteLine(); 

        } 

    } 

      

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

    public static void Main(String[] args) 

    { 

        // Давайте создадим двоичное дерево, показанное

        // на схеме выше

        / * 1

                    / /

                    2 3

                    ///

                4 5 6

            * /

        Node root = new Node(1); 

        root.left = new Node(2); 

        root.right = new Node(3); 

        root.left.left = new Node(4); 

        root.left.right = new Node(5); 

        root.right.right = new Node(6); 

          

        printLevelOrder(root); 

    } 

} 

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


Выход:

1
2 3
4 5 6

Временная сложность этого метода составляет O (n), где n — количество узлов в данном двоичном дереве.

Уровень прохождения заказа строка за строкой | Набор 2 (с использованием двух очередей)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Печатать уровень обхода заказа построчно | Комплект 1

0.00 (0%) 0 votes