计算n叉树中各节点子树的叶节点数量分析

原文:https://www . geesforgeks . org/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++ program to print the number of
// leaf nodes of every node
#include
using namespace std;
// Function to insert edges of tree
void insert(int x, int y, vector adjacency[])
{
    adjacency[x].push_back(y);
}
// Function to run DFS on a tree
void dfs(int node, int leaf[], int vis[],
         vector adjacency[])
{
    leaf[node] = 0;
    vis[node] = 1;
    // iterate on all the nodes
    // connected to node
    for (auto it : adjacency[node]) {
        // If not visited
        if (!vis[it]) {
            dfs(it, leaf, vis, adjacency);
            leaf[node] += leaf[it];
        }
    }
    if (!adjacency[node].size())
        leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
void printLeaf(int n, int leaf[])
{
    // Function to print leaf nodes
    for (int i = 1; i <= n; i++) {
        cout <<"The node " <             <    }
}
// Driver Code
int main()
{
    // Given N-ary Tree
    /*     1
         /   \
        2     3
            / | \
            4 5 6 */
    int N = 6; // no of nodes
    vector adjacency[N + 1]; // adjacency list for tree
    insert(1, 2, adjacency);
    insert(1, 3, adjacency);
    insert(3, 4, adjacency);
    insert(3, 5, adjacency);
    insert(3, 6, adjacency);
    int leaf[N + 1]; // Store count of leaf in subtree of i
    int vis[N + 1] = { 0 }; // mark nodes visited
    dfs(1, leaf, vis, adjacency);
    printLeaf(N, leaf);
    return 0;
}


Java 语言(一种计算机语言，尤用于创建网站)

// Java program to print the number of
// leaf nodes of every node
import java.util.*;
class GFG
{
static Vector> adjacency = new
       Vector>();
// Function to insert edges of tree
static void insert(int x, int y)
{
    adjacency.get(x).add(y);
}
// Function to run DFS on a tree
static void dfs(int node, int leaf[], int vis[])
{
    leaf[node] = 0;
    vis[node] = 1;
    // iterate on all the nodes
    // connected to node
    for (int i = 0; i     {
        int it = adjacency.get(node).get(i);
        // If not visited
        if (vis[it] == 0)
        {
            dfs(it, leaf, vis);
            leaf[node] += leaf[it];
        }
    }
    if (adjacency.get(node).size() == 0)
        leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
static void printLeaf(int n, int leaf[])
{
    // Function to print leaf nodes
    for (int i = 1; i <= n; i++)
    {
        System.out.print( "The node " + i + " has " +
                          leaf[i] + " leaf nodes\n");
    }
}
// Driver Code
public static void main(String args[])
{
    // Given N-ary Tree
    /*     1
        / \
        2     3
            / | \
            4 5 6 */
    int N = 6; // no of nodes
    for(int i = 0; i <= N; i++)
    adjacency.add(new Vector());
    insert(1, 2);
    insert(1, 3);
    insert(3, 4);
    insert(3, 5);
    insert(3, 6);
    // Store count of leaf in subtree of i
    int leaf[] = new int[N + 1];
    // mark nodes visited
    int vis[] = new int[N + 1] ;
    dfs(1, leaf, vis);
    printLeaf(N, leaf);
}
}
// This code is contributed by Arnab Kundu


Python 3

# Python3 program to print the number of
# leaf nodes of every node
adjacency = [[] for i in range(100)]
# Function to insert edges of tree
def insert(x, y):
    adjacency[x].append(y)
# Function to run DFS on a tree
def dfs(node, leaf, vis):
    leaf[node] = 0
    vis[node] = 1
    # iterate on all the nodes
    # connected to node
    for it in adjacency[node]:
        # If not visited
        if (vis[it] == False):
            dfs(it, leaf, vis)
            leaf[node] += leaf[it]
    if (len(adjacency[node]) == 0):
        leaf[node] = 1
# Function to prnumber of
# leaf nodes of a node
def printLeaf(n, leaf):
    # Function to prleaf nodes
    for i in range(1, n + 1):
        print("The node", i, "has", 
               leaf[i], "leaf nodes")
# Driver Code
# Given N-ary Tree
'''
/*     1
    / \
    2     3
        / | \
        4 5 6 '''
N = 6 # no of nodes
# adjacency list for tree
insert(1, 2)
insert(1, 3)
insert(3, 4)
insert(3, 5)
insert(3, 6)
# Store count of leaf in subtree of i
leaf = [0 for i in range(N + 1)]
# mark nodes visited
vis = [0 for i in range(N + 1)]
dfs(1, leaf, vis)
printLeaf(N, leaf)
# This code is contributed by Mohit Kumar


C

// C# program to print the number of
// leaf nodes of every node
using System;
using System.Collections.Generic;
class GFG
{
static List> adjacency = new
       List>();
// Function to insert edges of tree
static void insert(int x, int y)
{
    adjacency[x].Add(y);
}
// Function to run DFS on a tree
static void dfs(int node, int []leaf, int []vis)
{
    leaf[node] = 0;
    vis[node] = 1;
    // iterate on all the nodes
    // connected to node
    for (int i = 0; i     {
        int it = adjacency[node][i];
        // If not visited
        if (vis[it] == 0)
        {
            dfs(it, leaf, vis);
            leaf[node] += leaf[it];
        }
    }
    if (adjacency[node].Count == 0)
        leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
static void printLeaf(int n, int []leaf)
{
    // Function to print leaf nodes
    for (int i = 1; i <= n; i++)
    {
        Console.Write( "The node " + i + " has " +
                          leaf[i] + " leaf nodes\n");
    }
}
// Driver Code
public static void Main(String []args)
{
    // Given N-ary Tree
    /*     1
        / \
        2     3
            / | \
            4 5 6 */
    int N = 6; // no of nodes
    for(int i = 0; i <= N; i++)
    adjacency.Add(new List());
    insert(1, 2);
    insert(1, 3);
    insert(3, 4);
    insert(3, 5);
    insert(3, 6);
    // Store count of leaf in subtree of i
    int []leaf = new int[N + 1];
    // mark nodes visited
    int []vis = new int[N + 1] ;
    dfs(1, leaf, vis);
    printLeaf(N, leaf);
}
}
// This code contributed by Rajput-Ji


java 描述语言

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