Рубрики

Глубина N-арного дерева

По заданному N-арному дереву найдите глубину дерева. N-арное дерево — это дерево, в котором узлы могут иметь не более N дочерних элементов.

Примеры:
Пример 1:

Пример 2:

Дерево N-Ary можно пройти как обычное дерево. Нам просто нужно рассмотреть все дочерние элементы данного узла и рекурсивно вызвать эту функцию на каждом узле.

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 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 << depthOfTree(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 ;

}

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

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(depthOfTree(root) + "\n");

}
}

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

Выход:

4

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

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

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

Глубина N-арного дерева

0.00 (0%) 0 votes