Рубрики

Максимальная ширина бинарного дерева

Для данного двоичного дерева напишите функцию, чтобы получить максимальную ширину данного дерева. Ширина дерева — это максимальная ширина всех уровней.

Давайте рассмотрим приведенное ниже дерево примеров.

         1
        /  \
       2    3
     /  \     \
    4    5     8 
              /  \
             6    7

Для приведенного выше дерева,
ширина уровня 1 равна 1,
ширина уровня 2 равна 2,
ширина уровня 3 — 3
Ширина уровня 4 равна 2.

Таким образом, максимальная ширина дерева составляет 3.

Метод 1 (Использование уровня обхода порядка)
Этот метод в основном включает две функции. Одним из них является подсчет узлов на заданном уровне (getWidth), а другим — получение максимальной ширины дерева (getMaxWidth). getMaxWidth () использует getWidth (), чтобы получить ширину всех уровней, начиная с корня.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
  width =   getWidth(tree, i);
  if(width > maxWdth) 
      maxWdth  = width
return maxWidth
/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;  
else if level greater than 1, then
    return getWidth(tree->left, level-1) + 
    getWidth(tree->right, level-1);

C ++

// C ++ программа для вычисления ширины двоичного дерева
#include <bits/stdc++.h>

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Прототипы функций * /

int getWidth(node* root, int level); 

int height(node* node); 

node* newNode(int data); 

  
/ * Функция для получения максимальной ширины бинарного дерева * /

int getMaxWidth(node* root) 

    int maxWidth = 0; 

    int width; 

    int h = height(root); 

    int i; 

          

    / * Получить ширину каждого уровня и сравнить

        ширина с максимальной шириной до сих пор * /

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

    

        width = getWidth(root, i); 

        if(width > maxWidth) 

        maxWidth = width; 

    

          

    return maxWidth; 

  
/ * Получить ширину заданного уровня * /

int getWidth(node* root, int level) 

      

    if(root == NULL) 

        return 0; 

          

    if(level == 1) 

        return 1; 

                  

    else if (level > 1) 

        return getWidth(root->left, level - 1) + 

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

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

int height(node* node) 

    if (node == NULL) 

        return 0; 

    else

    

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

        int lHeight = height(node->left); 

        int rHeight = height(node->right); 

        / * использовать больший * /

          

        return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1); 

    

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

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

  
/ * Код водителя * /

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(8); 

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

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

      

    / *

    Построенное бунарное дерево это:

            1

            / /

        2 3

        ///

        4 5 8

                / /

                6 7

    * /

    cout<<"Maximum width is "<< getMaxWidth(root)<<endl; 

    return 0; 

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

С

#include <stdio.h>
#include <stdlib.h>

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

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Прототипы функций * /

int getWidth(struct node* root, int level);

int height(struct node* node);

struct node* newNode(int data);

  
/ * Функция для получения максимальной ширины бинарного дерева * /

int getMaxWidth(struct node* root)

{

  int maxWidth = 0;   

  int width;

  int h = height(root);

  int i;

    

  / * Получить ширину каждого уровня и сравнить

     ширина с максимальной шириной до сих пор * /

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

  {

    width = getWidth(root, i);

    if(width > maxWidth)

      maxWidth = width;

  }     

    

  return maxWidth;

}

  
/ * Получить ширину заданного уровня * /

int getWidth(struct node* root, int level)

{

      

  if(root == NULL)

    return 0;

    

  if(level == 1)

    return 1;

              

  else if (level > 1)

    return getWidth(root->left, level-1) + 

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

}

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

int height(struct node* node)

{

   if (node==NULL)

     return 0;

   else

   {

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

     int lHeight = height(node->left);

     int rHeight = height(node->right);

     / * использовать больший * /

     

     return (lHeight > rHeight)? (lHeight+1): (rHeight+1);

   }

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

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

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  return(node);

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

int main()

{

  struct 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(8);    

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

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

  

  / *

   Построенное бунарное дерево это:

          1

        / /

       2 3

     ///

    4 5 8

              / /

             6 7

  * /  

  printf("Maximum width is %d \n", getMaxWidth(root));  

  getchar();

  return 0;

}

Джава

// Java-программа для расчета ширины бинарного дерева

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

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Функция для получения максимальной ширины бинарного дерева * /

    int getMaxWidth(Node node) 

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

   

        / * Получить ширину каждого уровня и сравнить

           ширина с максимальной шириной до сих пор * /

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

        {

            width = getWidth(node, i);

            if (width > maxWidth)

                maxWidth = width;

        }

   

        return maxWidth;

    }

   

    / * Получить ширину заданного уровня * /

    int getWidth(Node node, int level) 

    {

        if (node == null)

            return 0;

   

        if (level == 1)

            return 1;

        else if (level > 1)

            return getWidth(node.left, level - 1)

                    + getWidth(node.right, level - 1);

        return 0;

    }

   

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

      

    / * Вычислить «высоту» дерева - количество

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

     вплоть до самого дальнего листового узла. * /

    int height(Node node) 

    {

        if (node == null)

            return 0;

        else

        {

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

            int lHeight = height(node.left);

            int rHeight = height(node.right);

               

            / * использовать больший * /

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

        / *

        Построенное бунарное дерево это:

              1

            / /

           2 3

         ///

        4 5 8

                 / /

                6 7

         * /

        tree.root = new Node(1);

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

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

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

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

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

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

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

   

        System.out.println("Maximum width is " + tree.getMaxWidth(tree.root));

    }

}

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

питон

# Программа Python, чтобы найти максимальную ширину
# бинарное дерево с использованием Level Order Traversal.

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

class Node:

      

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Функция для получения максимальной ширины бинарного дерева

def getMaxWidth(root):

    maxWidth = 0

    h = height(root)

    # Получить ширину каждого уровня и сравнить

    # ширина с максимальной шириной

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

        width = getWidth(root, i)

        if (width > maxWidth):

            maxWidth = width

    return maxWidth

  
# Получить ширину заданного уровня

def getWidth(root,level):

    if root is None:

        return 0

    if level == 1:

        return 1

    elif level > 1:

        return (getWidth(root.left,level-1) + 

                getWidth(root.right,level-1))

  
# ПОЛЕЗНЫЕ ФУНКЦИИ
# Вычислить «высоту» дерева - количество
# узлы вдоль самого длинного пути от корневого узла
# до самого дальнего листового узла.

def height(node):

    if node is None:

        return 0

    else:

  

        # вычислить высоту каждого поддерева

        lHeight = height(node.left)

        rHeight = height(node.right)

  

        # используйте больший

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

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

root.right.right.right = Node(7

  
«»»
Построенное бунарное дерево это:

    1

    / /

    2 3

    ///

4 5 8

        / /

        6 7

«»»

  

print "Maximum width is %d" %(getMaxWidth(root))

  
# Этот код предоставлен Навином Айли

C #

using System;

  
// 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 int getMaxWidth(Node node)

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

  

        / * Получить ширину каждого уровня и сравнить

        ширина с максимальной шириной до сих пор * /

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

        {

            width = getWidth(node, i);

            if (width > maxWidth)

            {

                maxWidth = width;

            }

        }

  

        return maxWidth;

    }

  

    / * Получить ширину заданного уровня * /

    public virtual int getWidth(Node node, int level)

    {

        if (node == null)

        {

            return 0;

        }

  

        if (level == 1)

        {

            return 1;

        }

        else if (level > 1)

        {

            return getWidth(node.left, level - 1) 

                  + getWidth(node.right, level - 1);

        }

        return 0;

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

  

    / * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

    public virtual int height(Node node)

    {

        if (node == null)

        {

            return 0;

        }

        else

        {

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

            int lHeight = height(node.left);

            int rHeight = height(node.right);

  

            / * использовать больший * /

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / *

        Построенное бунарное дерево это:

            1

            / /

        2 3

        ///

        4 5 8

                / /

                6 7

        * /

        tree.root = new Node(1);

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

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

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

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

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

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

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

  

        Console.WriteLine("Maximum width is " + tree.getMaxWidth(tree.root));

    }

}

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


Выход:

Maximum width is 3

Сложность времени: O (n ^ 2) в худшем случае.

Мы можем использовать основанный на очереди обход порядка для оптимизации временной сложности этого метода. Обход порядка очереди на основе очередей займет в худшем случае время O (n). Благодаря Nitish , DivyaC и tech.login.id2 для предлагая эту оптимизацию. Смотрите их комментарии для реализации с использованием обхода на основе очереди.

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

C ++

// Программа C ++ на основе очереди, чтобы найти максимальную ширину
// бинарного дерева
#include<bits/stdc++.h>

using namespace std ;

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

   и указатель на правого ребенка * /

struct Node

{

    int data ;

    struct Node * left ;

    struct Node * right ;

};

  
// Функция для определения максимальной ширины дерева
// используя обход уровня

int maxWidth(struct Node * root)

{

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

    if (root == NULL)

        return 0;

  

    // Инициализировать результат

    int result = 0;

  

    // Делаем ли вы прохождение ордера, отслеживая число

    // узлов на каждом уровне.

    queue<Node*> q;

    q.push(root);

    while (!q.empty())

    {

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

        // обход одного уровня

        int count = q.size() ;

  

        // Обновляем максимальное количество узлов

        result = max(count, result);

  

        // Итерация для всех узлов в очереди в настоящее время

        while (count--)

        {

            // Выводим узел из очереди

            Node *temp = q.front();

            q.pop();

  

            // ставим в очередь левых и правых потомков

            // удаленный узел

            if (temp->left != NULL)

                q.push(temp->left);

            if (temp->right != NULL)

                q.push(temp->right);

        }

    }

  

    return result;

}

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

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

struct Node * newNode(int data)

{

    struct Node * node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

  

int main()

{

    struct 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(8);

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

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

  

    / * Построенное двоичное дерево это:

                 1

               / /

             2 3

           ///

          4 5 8

                    / /

                   6 7 * /

    cout << "Maximum width is "

         << maxWidth(root) << endl;

    return 0;

}

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

Джава

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

import java.util.LinkedList;

import java.util.Queue;

  

public class maxwidthusingqueue 

{

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

       левый ребенок и указатель на правый ребенок * /

    static class node 

    {

        int data;

        node left, right;

  

        public node(int data) 

        {

            this.data = data;

        }

    }

  

    // Функция для определения максимальной ширины

    // дерево, использующее обход уровня порядка

    static int maxwidth(node root) 

    {

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

        if (root == null)

            return 0;

          

        // Инициализировать результат

        int maxwidth = 0;

          

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

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

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

        q.add(root);

        while (!q.isEmpty()) 

        {

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

            // обход одного уровня

            int count = q.size();

              

            // Обновляем максимальное количество узлов

            maxwidth = Math.max(maxwidth, count);

              

            // Итерация для всех узлов в

            // очередь в данный момент

            while (count-- > 0

            {

                // Выводим узел из очереди

                node temp = q.remove();

              

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

                // удаленного узла

                if (temp.left != null

                {

                    q.add(temp.left);

                }

                if (temp.right != null

                {

                    q.add(temp.right);

                }

            }

        }

        return maxwidth;

    }

  

    public static void main(String[] args) 

    {

        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(8);

        root.right.right.left = new node(6);

        root.right.right.right = new node(7);

  

                / * Построенное двоичное дерево это:

                1

              / /

            2 3

          ///

         4 5 8

                   / /

                  6 7 * /

                    

        System.out.println("Maximum width = " + maxwidth(root));

    }

}

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

питон

# Python программа для поиска максимальной ширины бинарника
# дерево с использованием Level Order Traversal с очередью.

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

class Node:

      

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Функция для получения максимальной ширины бинарного дерева

def getMaxWidth(root):

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

    if root is None:

        return 0

    q = []

    maxWidth = 0

      

    q.insert(0,root)

      

    while (q != []):

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

        # Обход одного уровня

        count = len(q)

          

        # Обновить значение максимального количества узлов

        maxWidth = max(count,maxWidth)

          

        while (count is not 0):

            count = count-1

            temp = q[-1]  

            q.pop() ;

            if temp.left is not None:

                q.insert(0,temp.left)

   

            if temp.right is not None:

                q.insert(0,temp.right)

  

    return maxWidth

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

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

root.right.right.right = Node(7

  
«»»
Построенное бунарное дерево это:

       1

      / /

     2 3

    ///

   4 5 8

          / /

         6 7

«»»

  

print "Maximum width is %d" %(getMaxWidth(root))

  
# Этот код предоставлен Навином Айли

C #

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

using System;

using System.Collections.Generic; 

  

public class maxwidthusingqueue 

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

    левый ребенок и указатель на правый ребенок * /

    public class node 

    

        public int data; 

        public node left, right; 

  

        public node(int data) 

        

            this.data = data; 

        

    

  

    // Функция для определения максимальной ширины

    // дерево, использующее обход уровня порядка

    static int maxwidth(node root) 

    

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

        if (root == null

            return 0; 

          

        // Инициализировать результат

        int maxwidth = 0; 

          

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

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

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

        q.Enqueue(root); 

        while (q.Count!=0) 

        

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

            // обход одного уровня

            int count = q.Count; 

              

            // Обновляем максимальное количество узлов

            maxwidth = Math.Max(maxwidth, count); 

              

            // Итерация для всех узлов в

            // очередь в данный момент

            while (count-- > 0) 

            

                // Выводим узел из очереди

                node temp = q.Dequeue(); 

              

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

                // удаленного узла

                if (temp.left != null

                

                    q.Enqueue(temp.left); 

                

                if (temp.right != null

                

                    q.Enqueue(temp.right); 

                

            

        

        return maxwidth; 

    

  

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

    public static void Main(String[] args) 

    

        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(8); 

        root.right.right.left = new node(6); 

        root.right.right.right = new node(7); 

  

                / * Построенное двоичное дерево это:

                1

            / /

            2 3

        ///

        4 5 8

                / /

                6 7 * /

                      

        Console.WriteLine("Maximum width = " + maxwidth(root)); 

    

  
// Этот код предоставлен Принчи Сингхом


Выход:

Maximum width is 3

Метод 3 (с использованием обхода предзаказа)
В этом методе мы создаем временный массив count [] размером, равным высоте дерева. Мы инициализируем все значения в count как 0. Мы проходим по дереву с помощью обхода предварительного заказа и заполняем записи в count так, чтобы массив count содержал количество узлов на каждом уровне в Binary Tree.

C ++

#include <bits/stdc++.h>

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
// Полезная функция для получения
// высота бинарного дерева

int height(node* node); 

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

node* newNode(int data); 

  
// Вспомогательная функция, которая возвращает
// максимальное значение в arr [] размера n

int getMax(int arr[], int n); 

  
// Функция, которая заполняет массив count
// с количеством узлов на каждом
// уровень заданного бинарного дерева

void getMaxWidthRecur(node *root, int count[], int level); 

  

  
/ * Функция, чтобы получить максимум
ширина двоичного дерева * /

int getMaxWidth(node* root) 

    int width; 

    int h = height(root); 

  

    // Создать массив, который будет

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

    int *count = new int[h];

  

    int level = 0; 

  

    // Заполняем массив count, используя предварительный обход

    getMaxWidthRecur(root, count, level); 

  

    // Возвращаем максимальное значение из массива count

    return getMax(count, h); 

  
// Функция, которая заполняет массив count
// с количеством узлов на каждом
// уровень заданного бинарного дерева

void getMaxWidthRecur(node *root, int count[], int level) 

    if(root) 

    

        count[level]++; 

        getMaxWidthRecur(root->left, count, level + 1); 

        getMaxWidthRecur(root->right, count, level + 1); 

    

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

int height(node* node) 

    if (node==NULL) 

        return 0; 

    else

    

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

        int lHeight = height(node->left); 

        int rHeight = height(node->right); 

        / * использовать больший * /

  

        return (lHeight > rHeight)? (lHeight+1): (rHeight+1); 

    

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

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

  
// Возвращаем максимальное значение из массива count

int getMax(int arr[], int n) 

    int max = arr[0]; 

    int i; 

    for (i = 0; i < n; i++) 

    

        if (arr[i] > max) 

            max = arr[i]; 

    

    return max; 

  
/ * Код водителя * /

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(8); 

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

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

  

    / *

    Построенное бунарное дерево это:

            1

            / /

            2 3

            ///

            4 5 8

            / /

            6 7

    * /

    cout << "Maximum width is " << getMaxWidth(root) << endl; 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>
#include <stdlib.h>

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

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

int height(struct node* node);

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

struct node* newNode(int data);

  
// Вспомогательная функция, которая возвращает максимальное значение в arr [] размера n

int getMax(int arr[], int n);

  
// Функция, которая заполняет массив count количеством узлов в каждом
// уровень заданного бинарного дерева

void getMaxWidthRecur(struct node *root, int count[], int level);

  

  
/ * Функция для получения максимальной ширины бинарного дерева * /

int getMaxWidth(struct node* root)

{

  int width;

  int h = height(root);

  

  // Создать массив, который будет хранить количество узлов на каждом уровне

  int *count = (int *)calloc(sizeof(int), h);

  

  int level = 0;

  

  // Заполняем массив count, используя предварительный обход

  getMaxWidthRecur(root, count, level);

  

  // Возвращаем максимальное значение из массива count

  return getMax(count, h);

}

  
// Функция, которая заполняет массив count количеством узлов в каждом
// уровень заданного бинарного дерева

void getMaxWidthRecur(struct node *root, int count[], int level)

{

  if(root)

  {

    count[level]++;

    getMaxWidthRecur(root->left, count, level+1);

    getMaxWidthRecur(root->right, count, level+1);

  }

}

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

int height(struct node* node)

{

   if (node==NULL)

     return 0;

   else

   {

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

     int lHeight = height(node->left);

     int rHeight = height(node->right);

     / * использовать больший * /

  

     return (lHeight > rHeight)? (lHeight+1): (rHeight+1);

   }

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

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

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  return(node);

}

  
// Возвращаем максимальное значение из массива count

int getMax(int arr[], int n)

{

   int max = arr[0];

   int i;

   for (i = 0; i < n; i++)

   {

       if (arr[i] > max)

          max = arr[i];

   }

   return max;

}

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

int main()

{

  struct 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(8);

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

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

  

  / *

   Построенное бунарное дерево это:

          1

        / /

       2 3

     ///

    4 5 8

              / /

             6 7

  * /

  printf("Maximum width is %d \n", getMaxWidth(root));

  getchar();

  return 0;

}

Джава

// Java-программа для расчета ширины бинарного дерева

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

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Функция для получения максимальной ширины бинарного дерева * /

    int getMaxWidth(Node node) 

    {

        int width;

        int h = height(node);

   

        // Создать массив, который будет хранить количество узлов на каждом уровне

        int count[] = new int[10];

   

        int level = 0;

   

        // Заполняем массив count, используя предварительный обход

        getMaxWidthRecur(node, count, level);

   

        // Возвращаем максимальное значение из массива count

        return getMax(count, h);

    }

   

    // Функция, которая заполняет массив count количеством узлов в каждом

    // уровень заданного бинарного дерева

    void getMaxWidthRecur(Node node, int count[], int level) 

    {

        if (node != null

        {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

   

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

      

    / * Вычислить «высоту» дерева - количество

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

     вплоть до самого дальнего листового узла. * /

    int height(Node node) 

    {

        if (node == null

            return 0;

        else 

        {

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

            int lHeight = height(node.left);

            int rHeight = height(node.right);

               

            / * использовать больший * /

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

       

    // Возвращаем максимальное значение из массива count

    int getMax(int arr[], int n) 

    {

        int max = arr[0];

        int i;

        for (i = 0; i < n; i++) 

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

        / *

        Построенное бунарное дерево это:

              1

            / /

           2 3

          ///

         4 5 8

                 / /

                6 7 * /

        tree.root = new Node(1);

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

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

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

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

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

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

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

   

        System.out.println("Maximum width is "

                           tree.getMaxWidth(tree.root));

    }

}

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

питон

# Программа Python для определения максимальной ширины бинарного дерева с использованием Preorder Traversal.

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

class Node:

      

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Функция для получения максимальной ширины бинарного дерева

def getMaxWidth(root):

    h = height(root)

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

    count = [0] * h

      

    level = 0

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

    getMaxWidthRecur(root, count, level)

      

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

    return getMax(count,h)

  
# Функция, которая заполняет массив count количеством узлов в каждом
# уровень заданного двоичного дерева

def getMaxWidthRecur(root, count, level):

    if root is not None:

        count[level] += 1

        getMaxWidthRecur(root.left, count, level+1)

        getMaxWidthRecur(root.right, count, level+1)

  
# ПОЛЕЗНЫЕ ФУНКЦИИ
# Вычислить «высоту» дерева - количество
# узлы вдоль самого длинного пути от корневого узла
# до самого дальнего листового узла.

def height(node):

    if node is None:

        return 0

    else:

        # вычислить высоту каждого поддерева

        lHeight = height(node.left)

        rHeight = height(node.right)

        # используйте больший

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

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

def getMax(count, n):

    max = count[0]

    for i in range (1,n):

        if (count[i] > max):

            max = count[i]

    return max

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

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

root.right.right.right = Node(7

  
«»»
Построенное бунарное дерево это:

       1

      / /

     2 3

    ///

   4 5 8

          / /

         6 7

«»»

  

print "Maximum width is %d" %(getMaxWidth(root))

  
# Этот код предоставлен Навином Айли

C #

// C # программа для расчета ширины двоичного дерева

using System;

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

public class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree 

{

    Node root;

  

    / * Функция, чтобы получить максимум

    ширина двоичного дерева * /

    int getMaxWidth(Node node) 

    {

        int width;

        int h = height(node);

  

        // Создать массив, который будет хранить

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

        int []count = new int[10];

  

        int level = 0;

  

        // Заполняем массив count, используя предварительный обход

        getMaxWidthRecur(node, count, level);

  

        // Возвращаем максимальное значение из массива count

        return getMax(count, h);

    }

  

    // Функция, которая заполняет счет

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

    // уровень заданного бинарного дерева

    void getMaxWidthRecur(Node node, int []count, int level) 

    {

        if (node != null

        {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

      

    / * Вычислить «высоту» дерева - количество

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

    вплоть до самого дальнего листового узла. * /

    int height(Node node) 

    {

        if (node == null

            return 0;

        else

        {

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

            int lHeight = height(node.left);

            int rHeight = height(node.right);

              

            / * использовать больший * /

            return (lHeight > rHeight) ? 

                    (lHeight + 1) : (rHeight + 1);

        }

    }

      

    // Возвращаем максимальное значение из массива count

    int getMax(int []arr, int n) 

    {

        int max = arr[0];

        int i;

        for (i = 0; i < n; i++) 

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

  

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

    public static void Main(String []args) 

    {

        BinaryTree tree = new BinaryTree();

          

        / *

        Построенное бунарное дерево это:

            1

            / /

        2 3

        ///

        4 5 8

                / /

                6 7 * /

        tree.root = new Node(1);

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

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

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

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

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

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

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

  

        Console.WriteLine("Maximum width is "

                        tree.getMaxWidth(tree.root));

    }

}

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


Выход:

Maximum width is 3

Спасибо Радже и Джагдишу за предложение этого метода.

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

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

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

Максимальная ширина бинарного дерева

0.00 (0%) 0 votes