Elemento más grande en un árbol N-ario

Dado un árbol N-ario que consta de N Nodes, la tarea es encontrar el Node que tiene el mayor valor en el árbol N -ario dado .

Ejemplos:

Aporte:

Salida: 90
Explicación: El Node con el mayor valor en el árbol es 90.

Aporte:

Salida: 95
Explicación: El Node con el mayor valor en el árbol es 95.

Enfoque: El problema dado se puede resolver atravesando el árbol N -ario dado y haciendo un seguimiento del valor máximo de los Nodes que ocurrieron. Después de completar el recorrido, imprima el valor máximo obtenido.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a
// node of N-ary tree
struct Node {
    int key;
    vector<Node*> child;
};
 
// Stores the node with largest value
Node* maximum = NULL;
 
// Function to create a new Node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
 
    // Return the newly created node
    return temp;
}
 
// Function to find the node with
// largest value in N-ary tree
void findlargest(Node* root)
{
    // Base Case
    if (root == NULL)
        return;
 
    // If maximum is NULL, return
    // the value of root node
    if ((maximum) == NULL)
        maximum = root;
 
    // If value of the root is greater
    // than maximum, update the maximum node
    else if (root->key > (maximum)->key) {
        maximum = root;
    }
 
    // Recursively call for all the
    // children of the root node
    for (int i = 0;
         i < root->child.size(); i++) {
        findlargest(root->child[i]);
    }
}
 
// Driver Code
int main()
{
    // Given N-ary tree
    Node* root = newNode(11);
    (root->child).push_back(newNode(21));
    (root->child).push_back(newNode(29));
    (root->child).push_back(newNode(90));
    (root->child[0]->child).push_back(newNode(18));
    (root->child[1]->child).push_back(newNode(10));
    (root->child[1]->child).push_back(newNode(12));
    (root->child[2]->child).push_back(newNode(77));
 
    findlargest(root);
 
    // Print the largest value
    cout << maximum->key;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Structure of a
// node of N-ary tree
static class Node
{
    int key;
    Vector<Node> child = new Vector<>();
};
 
// Stores the node with largest value
static Node maximum = null;
 
// Function to create a new Node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
 
    // Return the newly created node
    return temp;
}
 
// Function to find the node with
// largest value in N-ary tree
static void findlargest(Node root)
{
     
    // Base Case
    if (root == null)
        return;
 
    // If maximum is null, return
    // the value of root node
    if ((maximum) == null)
        maximum = root;
 
    // If value of the root is greater
    // than maximum, update the maximum node
    else if (root.key > (maximum).key)
    {
        maximum = root;
    }
 
    // Recursively call for all the
    // children of the root node
    for(int i = 0;
            i < root.child.size(); i++)
    {
        findlargest(root.child.get(i));
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N-ary tree
    Node root = newNode(11);
    (root.child).add(newNode(21));
    (root.child).add(newNode(29));
    (root.child).add(newNode(90));
    (root.child.get(0).child).add(newNode(18));
    (root.child.get(1).child).add(newNode(10));
    (root.child.get(1).child).add(newNode(12));
    (root.child.get(2).child).add(newNode(77));
 
    findlargest(root);
 
    // Print the largest value
    System.out.print(maximum.key);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach
 
# Structure of a
# node of N-ary tree
class Node:
    # Constructor to set the data of
    # the newly created tree node
    def __init__(self, key):
        self.key = key
        self.child = []
 
# Stores the node with largest value
maximum = None
 
# Function to create a new Node
def newNode(key):
    temp = Node(key)
 
    # Return the newly created node
    return temp
 
# Function to find the node with
# largest value in N-ary tree
def findlargest(root):
    global maximum
    # Base Case
    if (root == None):
        return
 
    # If maximum is null, return
    # the value of root node
    if ((maximum) == None):
        maximum = root
 
    # If value of the root is greater
    # than maximum, update the maximum node
    elif (root.key > (maximum).key):
        maximum = root
 
    # Recursively call for all the
    # children of the root node
    for i in range(len(root.child)):
        findlargest(root.child[i])
 
# Given N-ary tree
root = newNode(11)
(root.child).append(newNode(21))
(root.child).append(newNode(29))
(root.child).append(newNode(90))
(root.child[0].child).append(newNode(18))
(root.child[1].child).append(newNode(10))
(root.child[1].child).append(newNode(12))
(root.child[2].child).append(newNode(77))
 
findlargest(root)
 
# Print the largest value
print(maximum.key)
 
# This code is contributed by decode2207.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Structure of a
// node of N-ary tree
class Node
{
    public int key;
    public List<Node> child = new List<Node>();
};
 
// Stores the node with largest value
static Node maximum = null;
 
// Function to create a new Node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
 
    // Return the newly created node
    return temp;
}
 
// Function to find the node with
// largest value in N-ary tree
static void findlargest(Node root)
{
     
    // Base Case
    if (root == null)
        return;
 
    // If maximum is null, return
    // the value of root node
    if ((maximum) == null)
        maximum = root;
 
    // If value of the root is greater
    // than maximum, update the maximum node
    else if (root.key > (maximum).key)
    {
        maximum = root;
    }
 
    // Recursively call for all the
    // children of the root node
    for(int i = 0;
            i < root.child.Count; i++)
    {
        findlargest(root.child[i]);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N-ary tree
    Node root = newNode(11);
    (root.child).Add(newNode(21));
    (root.child).Add(newNode(29));
    (root.child).Add(newNode(90));
    (root.child[0].child).Add(newNode(18));
    (root.child[1].child).Add(newNode(10));
    (root.child[1].child).Add(newNode(12));
    (root.child[2].child).Add(newNode(77));
 
    findlargest(root);
 
    // Print the largest value
    Console.Write(maximum.key);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
    // Javascript program for the above approach
     
    // Structure of a
    // node of N-ary tree
    class Node
    {
        constructor(key) {
           this.key = key;
           this.child = [];
        }
    }
     
    // Stores the node with largest value
    let maximum = null;
 
    // Function to create a new Node
    function newNode(key)
    {
        let temp = new Node(key);
 
        // Return the newly created node
        return temp;
    }
 
    // Function to find the node with
    // largest value in N-ary tree
    function findlargest(root)
    {
 
        // Base Case
        if (root == null)
            return;
 
        // If maximum is null, return
        // the value of root node
        if ((maximum) == null)
            maximum = root;
 
        // If value of the root is greater
        // than maximum, update the maximum node
        else if (root.key > (maximum).key)
        {
            maximum = root;
        }
 
        // Recursively call for all the
        // children of the root node
        for(let i = 0; i < root.child.length; i++)
        {
            findlargest(root.child[i]);
        }
    }
     
    // Given N-ary tree
    let root = newNode(11);
    (root.child).push(newNode(21));
    (root.child).push(newNode(29));
    (root.child).push(newNode(90));
    (root.child[0].child).push(newNode(18));
    (root.child[1].child).push(newNode(10));
    (root.child[1].child).push(newNode(12));
    (root.child[2].child).push(newNode(77));
  
    findlargest(root);
  
    // Print the largest value
    document.write(maximum.key);
 
// This code is contributed by surehs07.
</script>
Producción: 

90

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por lakshita 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 *