Рубрики

Количество листовых узлов в поддереве каждого узла n-арного дерева

Для данного N-арного дерева выведите количество листовых узлов в поддереве каждого узла.

Примеры :

Input:      
            1 
          /    \
         2      3
             /  |   \
            4   5    6
Output:
The node 1 has 4 leaf nodes
The node 2 has 1 leaf nodes
The node 3 has 3 leaf nodes
The node 4 has 1 leaf nodes
The node 5 has 1 leaf nodes
The node 6 has 1 leaf nodes

Подход : Идея состоит в том, чтобы выполнить обход DFS для данного дерева и для каждого узла сохранить массив листьев [], чтобы хранить количество листовых узлов в поддереве под ним.

Теперь, при повторении вниз по дереву, если найден листовой узел, установите его значение leaf [i] равным 1 и верните обратно в восходящем направлении. Теперь, каждый раз при возврате из вызова функции вверх, добавляйте листовые узлы узла под ним.

После завершения обхода DFS у нас будет количество листовых узлов в листе массива [].

Ниже приведена реализация вышеуказанного подхода:

C ++

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

using namespace std;

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

void insert(int x, int y, vector<int> adjacency[])

{

    adjacency[x].push_back(y);

}

  
// Функция для запуска DFS на дереве

void dfs(int node, int leaf[], int vis[],

         vector<int> adjacency[])

{

    leaf[node] = 0;

    vis[node] = 1;

  

    // перебираем все узлы

    // подключен к узлу

    for (auto it : adjacency[node]) {

  

        // Если не посещали

        if (!vis[it]) {

            dfs(it, leaf, vis, adjacency);

            leaf[node] += leaf[it];

        }

    }

  

    if (!adjacency[node].size())

        leaf[node] = 1;

}

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

void printLeaf(int n, int leaf[])

{

    // Функция для печати листовых узлов

    for (int i = 1; i <= n; i++) {

        cout << "The node " << i << " has "

             << leaf[i] << " leaf nodes\n";

    }

}

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

int main()

{

    // дано N-арное дерево

  

    / * 1

         / /

        2 3

            / | /

            4 5 6 * /

  

    int N = 6; // нет узлов

    vector<int> adjacency[N + 1]; // список смежности для дерева

  

    insert(1, 2, adjacency);

    insert(1, 3, adjacency);

    insert(3, 4, adjacency);

    insert(3, 5, adjacency);

    insert(3, 6, adjacency);

  

    int leaf[N + 1]; // Сохранить количество листьев в поддереве i

    int vis[N + 1] = { 0 }; // отметить посещенные узлы

  

    dfs(1, leaf, vis, adjacency);

  

    printLeaf(N, leaf);

  

    return 0;

}

Джава

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

import java.util.*;

class GFG

{

static Vector<Vector<Integer>> adjacency = new

       Vector<Vector<Integer>>();

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

static void insert(int x, int y)

{

    adjacency.get(x).add(y);

}

  
// Функция для запуска DFS на дереве

static void dfs(int node, int leaf[], int vis[])

{

    leaf[node] = 0;

    vis[node] = 1;

  

    // перебираем все узлы

    // подключен к узлу

    for (int i = 0; i < adjacency.get(node).size(); i++)

    {

        int it = adjacency.get(node).get(i);

          

        // Если не посещали

        if (vis[it] == 0

        {

            dfs(it, leaf, vis);

            leaf[node] += leaf[it];

        }

    }

  

    if (adjacency.get(node).size() == 0)

        leaf[node] = 1;

}

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

static void printLeaf(int n, int leaf[])

{

    // Функция для печати листовых узлов

    for (int i = 1; i <= n; i++) 

    {

        System.out.print( "The node " + i + " has "

                          leaf[i] + " leaf nodes\n");

    }

}

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

public static void main(String args[])

{

    // дано N-арное дерево

  

    / * 1

        / /

        2 3

            / | /

            4 5 6 * /

  

    int N = 6; // нет узлов

      

    for(int i = 0; i <= N; i++)

    adjacency.add(new Vector<Integer>());

      

    insert(1, 2);

    insert(1, 3);

    insert(3, 4);

    insert(3, 5);

    insert(3, 6);

  

    // Сохранить количество листьев в поддереве i

    int leaf[] = new int[N + 1]; 

      

    // отметить посещенные узлы

    int vis[] = new int[N + 1] ; 

  

    dfs(1, leaf, vis);

  

    printLeaf(N, leaf);

}
}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для вывода номера
# листовые узлы каждого узла

adjacency = [[] for i in range(100)]

  
# Функция для вставки краев дерева

def insert(x, y):

    adjacency[x].append(y)

  
# Функция для запуска DFS на дереве

def dfs(node, leaf, vis):

  

    leaf[node] = 0

    vis[node] = 1

  

    # итерировать на всех узлах

    # подключен к узлу

    for it in adjacency[node]:

  

        # Если не посещали

        if (vis[it] == False):

            dfs(it, leaf, vis)

            leaf[node] += leaf[it]

  

    if (len(adjacency[node]) == 0):

        leaf[node] = 1

  
# Функция для указания номера
# листовые узлы узла

def printLeaf(n, leaf):

      

    # Функция для вывода узлов

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

        print("The node", i, "has",  

               leaf[i], "leaf nodes")

  
Код водителя

  
# Дано N-арное дерево
«»»
/ * 1

    / /

    2 3

        / | /

        4 5 6 '' '

  

N = 6 # количество узлов

# список смежности для дерева

  

insert(1, 2)

insert(1, 3)

insert(3, 4)

insert(3, 5)

insert(3, 6)

  
# Хранить количество листьев в поддереве i

leaf = [0 for i in range(N + 1)] 

  
# отметка посещенных узлов

vis = [0 for i in range(N + 1)] 

  

dfs(1, leaf, vis)

  
printLeaf(N, leaf)

  
# Этот код предоставлен Мохитом Кумаром

Выход:

The node 1 has 4 leaf nodes
The node 2 has 1 leaf nodes
The node 3 has 3 leaf nodes
The node 4 has 1 leaf nodes
The node 5 has 1 leaf nodes
The node 6 has 1 leaf nodes

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

Количество листовых узлов в поддереве каждого узла n-арного дерева

0.00 (0%) 0 votes