Рубрики

Уровень с максимальным количеством узлов

Найдите уровень в двоичном дереве, в котором есть максимальное количество узлов. Корень находится на уровне 0.

Примеры:

Input : 
       2             
    /     \          
   1        3            
 /   \       \       
4     6        8     
     /                
    5

Output : 2

        2             
     /     \          
    1        3            
  /   \       \       
 4    6        8 [Level with maximum nodes = 3]
     /                
    5

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

C ++

// реализация C ++ для поиска уровня
// имеющий максимальное количество узлов
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель

   слева от ребенка и указатель вправо

   ребенок * /

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

};

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

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

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

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

int maxNodeLevel(Node *root)

{

    if (root == NULL)

        return -1;

  

    queue<Node *> q;

    q.push(root);

  

    // Текущий уровень

    int level = 0;

  

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

    int max = INT_MIN;

  

    // Уровень с максимальным количеством узлов

    int level_no = 0;

  

    while (1)

    {

        // Считаем узлы на уровне

        int NodeCount = q.size();

  

        if (NodeCount == 0)

            break;

  

        // Если это максимум до сих пор

        // Обновление level_no до текущего уровня

        if (NodeCount > max)

        {

            max = NodeCount;

            level_no = level;

        }

  

        // Пройти полный текущий уровень

        while (NodeCount > 0)

        {

            Node *Node = q.front();

            q.pop();

            if (Node->left != NULL)

                q.push(Node->left);

            if (Node->right != NULL)

                q.push(Node->right);

            NodeCount--;

        }

  

        // Приращение для следующего уровня

        level++;

    }

  

    return level_no;

}

  
// Программа драйвера для тестирования выше

int main()

{

    // формирование двоичного дерева

    struct Node *root = newNode(2);      / * 2 * /

    root->left        = newNode(1);      / * / / * /

    root->right       = newNode(3);      / * 1 3 * /

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

    root->left->right = newNode(6);      / * 4 6 8 * /

    root->right->right  = newNode(8);    / * / * /

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

  

    printf("Level having maximum number of Nodes : %d",

            maxNodeLevel(root));

    return 0;

}

Джава

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

import java.util.*;

class GfG { 

  
/ * Узел двоичного дерева содержит данные, указатель
слева от ребенка и указатель вправо
ребенок * /

static class Node 

    int data; 

    Node left; 

    Node right; 

}

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

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = null

    node.right = null

    return(node); 

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

static int maxNodeLevel(Node root) 

    if (root == null

        return -1

  

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

    q.add(root); 

  

    // Текущий уровень

    int level = 0

  

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

    int max = Integer.MIN_VALUE; 

  

    // Уровень с максимальным количеством узлов

    int level_no = 0

  

    while (true

    

        // Считаем узлы на уровне

        int NodeCount = q.size(); 

  

        if (NodeCount == 0

            break

  

        // Если это максимум до сих пор

        // Обновление level_no до текущего уровня

        if (NodeCount > max) 

        

            max = NodeCount; 

            level_no = level; 

        

  

        // Пройти полный текущий уровень

        while (NodeCount > 0

        

            Node Node = q.peek(); 

            q.remove(); 

            if (Node.left != null

                q.add(Node.left); 

            if (Node.right != null

                q.add(Node.right); 

            NodeCount--; 

        

  

        // Приращение для следующего уровня

        level++; 

    

  

    return level_no; 

  
// Программа драйвера для тестирования выше

public static void main(String[] args) 

    // формирование двоичного дерева

     Node root = newNode(2);     / * 2 * /

    root.left     = newNode(1);     / * / / * /

    root.right     = newNode(3);     / * 1 3 * /

    root.left.left = newNode(4);     / * / / / * /

    root.left.right = newNode(6);     / * 4 6 8 * /

    root.right.right = newNode(8); / * / * /

    root.left.right.left = newNode(5);/ * 5 * /

  

    System.out.println("Level having maximum number of Nodes : " + maxNodeLevel(root)); 

}

python3

# Реализация Python3 для поиска
# уровень, имеющий максимальное количество узлов

  
# Импорт очереди

from queue import Queue 

  
# Вспомогательный класс, который выделяет новый
# узел с заданными данными и None
# левый и правый указатели.

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# функция, чтобы найти уровень
# Максимальное количество узлов

def maxNodeLevel(root):

    if (root == None): 

        return -1

  

    q = Queue() 

    q.put(root) 

  

    # Текущий уровень

    level = 0

  

    # Максимальное количество узлов на одном уровне

    Max = -999999999999

  

    # Уровень с максимальным количеством узлов

    level_no = 0

  

    while (1):

          

        Количество узлов на уровне

        NodeCount = q.qsize() 

  

        if (NodeCount == 0):

            break

  

        # Если это максимум до сих пор

        # Обновить level_no до текущего уровня

        if (NodeCount > Max):

            Max = NodeCount 

            level_no = level

  

        # Поп закончить текущий уровень

        while (NodeCount > 0):

            Node = q.queue[0

            q.get()

            if (Node.left != None):

                q.put(Node.left) 

            if (Node.right != None): 

                q.put(Node.right) 

            NodeCount -= 1

  

        # Приращение для следующего уровня

        level += 1

  

    return level_no

  
Код водителя

if __name__ == '__main__':

      

    # формирование двоичного дерева

    root = newNode(2)     № 2

    root.left     = newNode(1)     # / /

    root.right     = newNode(3)     # 1 3

    root.left.left = newNode(4)     # / / /

    root.left.right = newNode(6)     # 4 6 8

    root.right.right = newNode(8) # /

    root.left.right.left = newNode(5)№ 5

  

    print("Level having Maximum number of Nodes : "

                                 maxNodeLevel(root))

  
# Этот код предоставлен Pranchalk

C #

using System;

using System.Collections.Generic;

  
// реализация C # для поиска уровня
// имеющий максимальное количество узлов

public class GfG

{

  
/ * Узел двоичного дерева содержит данные, указатель
слева от ребенка и указатель вправо
ребенок * /

public class Node

{

    public int data;

    public Node left;

    public Node right;

}

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

public static Node newNode(int data)

{

    Node node = new Node();

    node.data = data;

    node.left = null;

    node.right = null;

    return (node);

}

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

public static int maxNodeLevel(Node root)

{

    if (root == null)

    {

        return -1;

    }

  

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

    q.AddLast(root);

  

    // Текущий уровень

    int level = 0;

  

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

    int max = int.MinValue;

  

    // Уровень с максимальным количеством узлов

    int level_no = 0;

  

    while (true)

    {

        // Считаем узлы на уровне

        int NodeCount = q.Count;

  

        if (NodeCount == 0)

        {

            break;

        }

  

        // Если это максимум до сих пор

        // Обновление level_no до текущего уровня

        if (NodeCount > max)

        {

            max = NodeCount;

            level_no = level;

        }

  

        // Пройти полный текущий уровень

        while (NodeCount > 0)

        {

            Node Node = q.First.Value;

            q.RemoveFirst();

            if (Node.left != null)

            {

                q.AddLast(Node.left);

            }

            if (Node.right != null)

            {

                q.AddLast(Node.right);

            }

            NodeCount--;

        }

  

        // Приращение для следующего уровня

        level++;

    }

  

    return level_no;

}

  
// Программа драйвера для тестирования выше

public static void Main(string[] args)

{

    // формирование двоичного дерева

     Node root = newNode(2); // 2

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

    root.right = newNode(3); // 1 3

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

    root.left.right = newNode(6); // 4 6 8

    root.right.right = newNode(8); // /

    root.left.right.left = newNode(5); // 5

  

    Console.WriteLine("Level having maximum number of Nodes : " + maxNodeLevel(root));

}
}

  

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


Выход:

Level having maximum number of nodes : 2 

Сложность времени: O (n)

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Уровень с максимальным количеством узлов

0.00 (0%) 0 votes