Рубрики

Диаметр н-арного дерева

Диаметр N-арного дерева — это самый длинный путь между любыми двумя узлами дерева. Эти два узла должны быть двумя листовыми узлами. Следующие примеры имеют самый длинный путь [диаметр] заштрихованы.

Пример 1:

Пример 2:

Условие: диаметр бинарного дерева .

Путь может начинаться с одного из узлов и подниматься до одного из LCA этих узлов и снова доходить до самого глубокого узла некоторого другого поддерева или может существовать как диаметр одного из дочерних элементов текущего узла.
Решение будет существовать в любом из этих:
I] Диаметр одного из дочерних элементов текущего узла
II] Сумма высоты двух старших поддеревьев + 1

C ++

// C ++ программа для поиска высоты N-ары
// дерево
#include <bits/stdc++.h>

using namespace std;

  
// Структура узла n-арного дерева

struct Node

{

    char key;

    vector<Node *> child;

};

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

Node *newNode(int key)

{

    Node *temp = new Node;

    temp->key = key;

    return temp;

}

  
// Сервисная функция, которая будет возвращать глубину
// дерева

int depthOfTree(struct Node *ptr)

{

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

    if (!ptr)

        return 0;

  

    int maxdepth = 0;

  

    // Проверить всех детей и найти

    // максимальная глубина

    for (vector<Node*>::iterator it = ptr->child.begin();

                           it != ptr->child.end(); it++)

  

        maxdepth = max(maxdepth , depthOfTree(*it));

  

    return maxdepth + 1;

}

  
// Функция для расчета диаметра
// дерева

int diameter(struct Node *ptr)

{

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

    if (!ptr)

        return 0;

  

    // Найти двух лучших детей

    int max1 = 0, max2 = 0;

    for (vector<Node*>::iterator it = ptr->child.begin();

                          it != ptr->child.end(); it++)

    {

        int h = depthOfTree(*it);

        if (h > max1)

           max2 = max1, max1 = h;

        else if (h > max2)

           max2 = h;

    }

  

    // Перебираем каждого потомка по диаметру

    int maxChildDia = 0;

    for (vector<Node*>::iterator it = ptr->child.begin();

                           it != ptr->child.end(); it++)

        maxChildDia = max(maxChildDia, diameter(*it));

  

    return max(maxChildDia, max1 + max2 + 1);

}

  
// Драйвер программы

int main()

{

    / * Давайте создадим под деревом

    * А

    * / / / /

    * B F D E

    * / / | / | /

    * K J G CHI

    * // /

    * Н М Л

    * /

  

    Node *root = newNode('A');

    (root->child).push_back(newNode('B'));

    (root->child).push_back(newNode('F'));

    (root->child).push_back(newNode('D'));

    (root->child).push_back(newNode('E'));

    (root->child[0]->child).push_back(newNode('K'));

    (root->child[0]->child).push_back(newNode('J'));

    (root->child[2]->child).push_back(newNode('G'));

    (root->child[3]->child).push_back(newNode('C'));

    (root->child[3]->child).push_back(newNode('H'));

    (root->child[3]->child).push_back(newNode('I'));

    (root->child[0]->child[0]->child).push_back(newNode('N'));

    (root->child[0]->child[0]->child).push_back(newNode('M'));

    (root->child[3]->child[2]->child).push_back(newNode('L'));

  

    cout << diameter(root) << endl;

  

    return 0;

}

Джава

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

import java.util.*;

class GFG

{

  
// Структура узла n-арного дерева

static class Node

{

    char key;

    Vector<Node> child;

};

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

static Node newNode(int key)

{

    Node temp = new Node();

    temp.key = (char) key;

    temp.child = new Vector<Node>();

    return temp;

}

  
// Сервисная функция, которая будет возвращать глубину
// дерева

static int depthOfTree(Node ptr)

{

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

    if (ptr == null)

        return 0;

  

    int maxdepth = 0;

  

    // Проверить всех детей и найти

    // максимальная глубина

    for (Node it : ptr.child)

  

        maxdepth = Math.max(maxdepth,

                            depthOfTree(it));

  

    return maxdepth + 1;

}

  
// Функция для расчета диаметра
// дерева

static int diameter(Node ptr)

{

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

    if (ptr == null)

        return 0;

  

    // Найти двух лучших детей

    int max1 = 0, max2 = 0;

    for (Node it : ptr.child)

    {

        int h = depthOfTree(it);

        if (h > max1)

        {

            max2 = max1;

            max1 = h;

        }

        else if (h > max2)

        max2 = h;

    }

  

    // Перебираем каждого потомка по диаметру

    int maxChildDia = 0;

    for (Node it : ptr.child)

        maxChildDia = Math.max(maxChildDia, 

                               diameter(it));

  

    return Math.max(maxChildDia, max1 + max2 + 1);

}

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

public static void main(String[] args)

{

    / * Давайте создадим под деревом

    * А

    * / / / /

    * BFDE

    * / / | / | /

    * KJGCHI

    * // /

    * NM L

    * /

    Node root = newNode('A');

    (root.child).add(newNode('B'));

    (root.child).add(newNode('F'));

    (root.child).add(newNode('D'));

    (root.child).add(newNode('E'));

    (root.child.get(0).child).add(newNode('K'));

    (root.child.get(0).child).add(newNode('J'));

    (root.child.get(2).child).add(newNode('G'));

    (root.child.get(3).child).add(newNode('C'));

    (root.child.get(3).child).add(newNode('H'));

    (root.child.get(3).child).add(newNode('I'));

    (root.child.get(0).child.get(0).child).add(newNode('N'));

    (root.child.get(0).child.get(0).child).add(newNode('M'));

    (root.child.get(3).child.get(2).child).add(newNode('L'));

  

    System.out.print(diameter(root) + "\n");

}
}

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

Выход:

7

Оптимизация по вышеуказанному решению:
Мы можем создать хеш-таблицу для хранения высот всех узлов. Если мы предварительно вычислим эти высоты, нам не нужно вызывать deepOfTree () для каждого узла.

Другое оптимизированное решение:
Самый длинный путь в неориентированном дереве

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

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

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

Диаметр н-арного дерева

0.00 (0%) 0 votes