Рубрики

Вывести узлы между двумя заданными номерами уровней двоичного дерева

Деревья

Учитывая двоичное дерево и два уровня уровня «низкий» и «высокий», печатать узлы от низкого уровня до высокого уровня. 

For example consider the binary tree given in below diagram. 

Input: Root of below tree, low = 2, high = 4

Output:
8 22
4 12
10 14

Простой метод — сначала написать рекурсивную функцию, которая печатает узлы с заданным номером уровня. Затем вызовите рекурсивную функцию в цикле от низкого до высокого. Временная сложность этого метода составляет O (n 2 )
Мы можем напечатать узлы за O (n) времени, используя итеративный обход порядка на основе очередей. Идея состоит в том, чтобы сделать простой обход порядка порядка на основе очереди. Выполняя обход Inorder, добавьте маркерный узел в конце. Всякий раз, когда мы видим узел маркера, мы увеличиваем номер уровня. Если номер уровня находится между низким и высоким, то выведите узлы.

Ниже приведена реализация вышеприведенной идеи.

C ++

// Программа на C ++ для печати уровня узлов по уровням между заданными двумя уровнями.
#include <iostream>
#include <queue>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, указатель на левого и правого потомков * /

struct Node

{

    int key;

    struct Node* left, *right;

};

  
/ * Учитывая двоичное дерево, печатать узлы от номера уровня 'низкий' до уровня

   число "высокий" * /

void printLevels(Node* root, int low, int high)

{

    queue <Node *> Q;

  

    Node *marker = new Node; // Узел маркера для обозначения конца уровня

  

    int level = 1;   // Инициализируем номер уровня

  

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

    Q.push(root);

    Q.push(marker);

  

    // Простой цикл прохождения порядка уровней

    while (Q.empty() == false)

    {

        // Удалить передний элемент из очереди

        Node *n = Q.front();

        Q.pop();

  

        // Проверяем, достигнут ли конец уровня

        if (n == marker)

        {

            // выводим новую строку и номер уровня приращения

            cout << endl;

            level++;

  

            // Проверка, был ли маркерный узел последним в очереди или

            // номер уровня выходит за заданный верхний предел

            if (Q.empty() == true || level > high) break;

  

            // ставим маркер в конец следующего уровня

            Q.push(marker);

  

            // Если это маркер, то нам не нужно его печатать

            // и ставим в очередь своих детей

            continue;

        }

  

        // Если уровень равен или больше заданного нижнего уровня,

        // распечатать

        if (level >= low)

            cout << n->key << " ";

  

        // ставим в очередь потомки немаркерного узла

        if (n->left != NULL)  Q.push(n->left);

        if (n->right != NULL) Q.push(n->right);

    }

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данный ключ и NULL левый и правый указатели. * /

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

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

    return (temp);

}

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

int main()

{

    // Давайте построим BST, показанный на рисунке выше

    struct Node *root        = newNode(20);

    root->left               = newNode(8);

    root->right              = newNode(22);

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

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

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

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

  

    cout << "Level Order traversal between given two levels is";

    printLevels(root, 2, 3);

  

    return 0;

}

Джава

// Java-программа для печати узлов по уровням между заданными двумя уровнями

import java.util.LinkedList;

import java.util.Queue;

   
/ * Узел двоичного дерева имеет ключ, указатель на левого и правого потомков * /

class Node 

{

    int data;

    Node left, right;

   

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Учитывая двоичное дерево, печатать узлы от номера уровня 'низкий' до уровня

       число "высокий" * /

    void printLevels(Node node, int low, int high) 

    {

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

   

        Node  marker = new Node(4); // Узел маркера для обозначения конца уровня

   

        int level = 1;   // Инициализируем номер уровня

   

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

        Q.add(node);

        Q.add(marker);

   

        // Простой цикл прохождения порядка уровней

        while (Q.isEmpty() == false) 

        {

            // Удалить передний элемент из очереди

            Node  n = Q.peek();

            Q.remove();

   

            // Проверяем, достигнут ли конец уровня

            if (n == marker) 

            {

                // выводим новую строку и номер уровня приращения

                System.out.println("");

                level++;

   

                // Проверка, был ли маркерный узел последним в очереди или

                // номер уровня выходит за заданный верхний предел

                if (Q.isEmpty() == true || level > high)

                    break;

   

                // ставим маркер в конец следующего уровня

                Q.add(marker);

                   

                // Если это маркер, то нам не нужно его печатать

                // и ставим в очередь своих детей

                continue;

            }

   

            // Если уровень равен или больше заданного нижнего уровня,

            // распечатать

            if (level >= low)

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

  

            // ставим в очередь потомки немаркерного узла

            if (n.left != null)

                Q.add(n.left);

              

            if (n.right != null) 

                Q.add(n.right);

              

        }

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

   

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

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

   

        System.out.print("Level Order traversal between given two levels is ");

        tree.printLevels(tree.root, 2, 3);

   

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python для печати узлов по уровням между
# дано два уровня

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

class Node:

    # Конструктор для создания нового узла

    def __init__(self, key):

        self.key = key 

        self.left = None

        self.right = None

      
# Учитывая двоичное дерево, узлы печати формируют номер уровня 'low'
# до уровня номер «высокий»

  

def printLevels(root, low, high):

    Q = [] 

      

    marker  = Node(11114) # Маркерный узел для обозначения конца уровня

      

    level = 1 # Инициализировать номер уровня

  

    # Поставить в очередь единственный узел первого уровня и узел маркера для

    # конец уровня

    Q.append(root)

    Q.append(marker)

      

    #print Q

    # Простой цикл прохождения порядка уровней

    while(len(Q) >0):

        # Удалить передний элемент из очереди

        n = Q[0]

        Q.pop(0)

        #print Q

        # Проверьте, достигнут ли конец уровня

        if n == marker:

            # печатать новую строку и номер уровня приращения

            print 

            level += 1

          

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

            # или уровень нумера находится за заданным верхним пределом

            if len(Q) == 0 or level > high:

                break

              

            # Поставить маркер в конец следующего уровня

            Q.append(marker)

              

            # Если это маркер, то нам не нужно его печатать

            # и ставить своих детей

            continue

        if level >= low:

                print n.key,

              

        # Ставить в очередь потомки немаркерного узла

        if n.left is not None:

            Q.append(n.left)

            Q.append(n.right)

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

root = Node(20)

root.left = Node(8)

root.right = Node(22)

root.left.left = Node(4)

root.left.right = Node(12)

root.left.right.left = Node(10)

root.left.right.right = Node(14)

  

print "Level Order Traversal between given two levels is",

printLevels(root,2,3)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

using System.Collections.Generic;

  
// c # программа для печати уровня узлов по уровням между заданными двумя уровнями

  
/ * Узел двоичного дерева имеет ключ, указатель на левого и правого потомков * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    / * Учитывая двоичное дерево, печатать узлы от номера уровня 'низкий' до уровня

       число "высокий" * /

    public virtual void printLevels(Node node, int low, int high)

    {

        LinkedList<Node> Q = new LinkedList<Node>();

  

        Node marker = new Node(4); // Узел маркера для обозначения конца уровня

  

        int level = 1; // Инициализируем номер уровня

  

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

        Q.AddLast(node);

        Q.AddLast(marker);

  

        // Простой цикл прохождения порядка уровней

        while (Q.Count > 0)

        {

            // Удалить передний элемент из очереди

            Node n = Q.First.Value;

            Q.RemoveFirst();

  

            // Проверяем, достигнут ли конец уровня

            if (n == marker)

            {

                // выводим новую строку и номер уровня приращения

                Console.WriteLine("");

                level++;

  

                // Проверка, был ли маркерный узел последним в очереди или

                // номер уровня выходит за заданный верхний предел

                if (Q.Count == 0 || level > high)

                {

                    break;

                }

  

                // ставим маркер в конец следующего уровня

                Q.AddLast(marker);

  

                // Если это маркер, то нам не нужно его печатать

                // и ставим в очередь своих детей

                continue;

            }

  

            // Если уровень равен или больше заданного нижнего уровня,

            // распечатать

            if (level >= low)

            {

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

            }

  

            // ставим в очередь потомки немаркерного узла

            if (n.left != null)

            {

                Q.AddLast(n.left);

            }

  

            if (n.right != null)

            {

                Q.AddLast(n.right);

            }

  

        }

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

  

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

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

  

        Console.Write("Level Order traversal between given two levels is ");

        tree.printLevels(tree.root, 2, 3);

  

    }

}

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


Выход

Level Order traversal between given two levels is
8 22
4 12

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

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

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

Вывести узлы между двумя заданными номерами уровней двоичного дерева

0.00 (0%) 0 votes