Número de Nodes mayor que un valor dado en el árbol n-ario

Dado un árbol n-ario y un número x , encuentre y devuelva el número de Nodes que son mayores que x. 

Ejemplo: 

C++

// C++ program to find number of nodes
// greater than x
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node of n-ary tree
struct Node {
    int key;
    vector<Node*> child;
};
 
// Utility function to create
// a new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    return temp;
}
 
// Function to find number of nodes
// greater than x
int nodesGreaterThanX(Node* root, int x)
{
    if (root == NULL)
        return 0;
 
    int count = 0;
 
    // if current root is greater
    // than x increment count
    if (root->key > x)
        count++;
 
    // Number of children of root
    int numChildren = root->child.size();
 
    // recursively calling for every child
    for (int i = 0; i < numChildren; i++) {
        Node* child = root->child[i];
        count += nodesGreaterThanX(child, x);
    }
 
    // return the count
    return count;
}
 
// Driver program
int main()
{
    /* Let us create below tree
*         5
*         / | \
*     1 2 3
*     / / \ \
*     15 4 5 6
*/
 
    Node* root = newNode(5);
    (root->child).push_back(newNode(1));
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child[0]->child).push_back(newNode(15));
    (root->child[1]->child).push_back(newNode(4));
    (root->child[1]->child).push_back(newNode(5));
    (root->child[2]->child).push_back(newNode(6));
 
    int x = 5;
 
    cout << "Number of nodes greater than "
        << x << " are ";
    cout << nodesGreaterThanX(root, x)
        << endl;
 
    return 0;
}

Java

// Java program to find number of nodes
// greater than x
import java.util.*;
 
// Class representing a Node of an N-ary tree
class Node{
     
    int key;
    ArrayList<Node> child;
 
    // Constructor to create a Node
    Node(int val)
    {
        key = val;
        child = new ArrayList<>();
    }
}
 
class GFG{
 
// Recursive function to find number
// of nodes greater than x
public static int nodesGreaterThanX(Node root, int x)
{
    if (root == null)
        return 0;
 
    int count = 0;
 
    // If current root is greater
    // than x increment count
    if (root.key > x)
        count++;
 
    // Recursively calling for every
    // child of current root
    for(Node child : root.child)
    {
        count += nodesGreaterThanX(child, x);
    }
 
    // Return the count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
     
    /* Let us create below tree
            5
        / | \
        1 2 3
        / / \ \
    15 4 5 6
    */
     
    Node root = new Node(5);
     
    root.child.add(new Node(1));
    root.child.add(new Node(2));
    root.child.add(new Node(3));
     
    root.child.get(0).child.add(new Node(15));
    root.child.get(1).child.add(new Node(4));
    root.child.get(1).child.add(new Node(5));
    root.child.get(2).child.add(new Node(6));
 
    int x = 5;
 
    System.out.print("Number of nodes greater than " +
                    x + " are ");
    System.out.println(nodesGreaterThanX(root, x));
}
}
 
// This code is contributed by jrishabh99

Python3

# Python3 program to find number of nodes
# greater than x
 
# Structure of a node of n-ary tree
class Node:
    def __init__(self, data):
        self.key = data
        self.child = []
 
# Function to find number of nodes
# greater than x
def nodesGreaterThanX(root: Node, x: int) -> int:
    if root is None:
        return 0
 
    count = 0
 
    # if current root is greater
    # than x increment count
    if root.key > x:
        count += 1
 
    # Number of children of root
    numChildren = len(root.child)
 
    # recursively calling for every child
    for i in range(numChildren):
        child = root.child[i]
        count += nodesGreaterThanX(child, x)
 
    # return the count
    return count
 
# Driver Code
if __name__ == "__main__":
 
    ans = 0
    k = 25
 
    # Let us create below tree
    # 5
    #         / | \
    # 1 2 3
    #     / / \ \
    # 15 4 5 6
 
    root = Node(5)
    (root.child).append(Node(1))
    (root.child).append(Node(2))
    (root.child).append(Node(3))
    (root.child[0].child).append(Node(15))
    (root.child[1].child).append(Node(4))
    (root.child[1].child).append(Node(5))
    (root.child[2].child).append(Node(6))
 
    x = 5
 
    print("Number of nodes greater than % d are % d" %
        (x, nodesGreaterThanX(root, x)))
 
# This code is contributed by
# sanjeev2552

C#

// C# program to find number of nodes
// greater than x
using System;
using System.Collections.Generic;
  
// Class representing a Node of an N-ary tree
public class Node
{
    public int key;
    public List<Node> child;
     
    // Constructor to create a Node
    public Node(int val)
    {
        key = val;
        child = new List<Node>();
    }
}
 
class GFG{
 
// Recursive function to find number
// of nodes greater than x
public static int nodesGreaterThanX(Node root, int x)
{
    if (root == null)
        return 0;
 
    int count = 0;
 
    // If current root is greater
    // than x increment count
    if (root.key > x)
        count++;
 
    // Recursively calling for every
    // child of current root
    foreach(Node child in root.child)
    {
        count += nodesGreaterThanX(child, x);
    }
 
    // Return the count
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
     
    /* Let us create below tree
          5
        / | \
       1  2  3
      /  / \  \
    15  4   5  6
    */
    Node root = new Node(5);
     
    root.child.Add(new Node(1));
    root.child.Add(new Node(2));
    root.child.Add(new Node(3));
     
    root.child[0].child.Add(new Node(15));
    root.child[1].child.Add(new Node(4));
    root.child[1].child.Add(new Node(5));
    root.child[2].child.Add(new Node(6));
 
    int x = 5;
 
    Console.Write("Number of nodes greater than " +
                  x + " are ");
    Console.WriteLine(nodesGreaterThanX(root, x));
}
}
 
// This code is contributed by Amit Katiyar

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *