Imprimir hermanos de un Node dado en N-ary Tree

Posted on by Rudeus Greyrat

Dado un árbol N-ario y un elemento X , la tarea es imprimir los hermanos del Node con valor X.

Se considera que dos Nodes son hermanos si están presentes en el mismo nivel y tienen el mismo padre. 
 

Ejemplos:

Entrada: X = 100 
 

Salida: 90 110
Explicación: Los Nodes con valor 90, 100 y 110 tienen el mismo padre, es decir, el Node con valor 40. Por lo tanto, los Nodes 90 y 110 son hermanos del Node dado X( = 100).

Entrada: X = 30 
 

Salida: 20 40
Explicación: Los Nodes con valor 20, 30 y 40 tienen el mismo padre, es decir, el Node con valor 10. Por lo tanto, los Nodes 20 y 40 son hermanos del Node dado X( = 30).

Enfoque: siga los pasos que se indican a continuación para resolver el problema:

  1. Realice un recorrido de orden de nivel en el árbol N -ario dado.
  2. Inicialice una cola q para el cruce de orden de nivel.
  3. Por cada Node encontrado, inserte todos sus hijos en la cola .
  4. Mientras empuja a los hijos del Node actual a la cola, verifique: si alguno de estos hijos es igual al valor dado X o no. Si se determina que es cierto, imprima todos los Nodes excepto X , que son hijos del actual como la respuesta requerida.
  5. De lo contrario, continúe atravesando el árbol .

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;
};
 
// Function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    return temp;
}
 
// Function to find the siblings
// of the node value
void Siblings(Node* root, int value)
{
    int flag = 0;
 
    if (root == NULL)
        return;
 
    // Stores nodes level wise
    queue<Node*> q;
 
    // Push the root
    q.push(root);
 
    // Continue until all levels
    // are traversed
    while (!q.empty()) {
 
        // Stores current node
        Node* temp = q.front();
        q.pop();
 
        // Enqueue all children of the current node
        for (int i = 0; i < temp->child.size(); i++) {
 
            // If node value is found
            if (temp->child[i]->key == value) {
 
                flag = 1;
 
                // Print all children of current node
                // except value as the answer
                for (int j = 0; j < temp->child.size();
                     j++) {
 
                    if (value
                        != temp->child[j]->key)
                        cout << temp->child[j]->key
                             << " ";
                }
                break;
            }
 
            // Push the child nodes
            // of temp into the queue
            q.push(temp->child[i]);
        }
    }
 
    if (flag == 0)
        cout << "No siblings!!";
}
 
Node* constructTree()
{
    Node* root = newNode(10);
    (root->child).push_back(newNode(20));
 
    (root->child).push_back(newNode(30));
 
    (root->child).push_back(newNode(40));
 
    (root->child[0]->child).push_back(newNode(50));
 
    (root->child[0]->child).push_back(newNode(60));
 
    (root->child[1]->child).push_back(newNode(70));
 
    (root->child[1]->child).push_back(newNode(80));
 
    (root->child[2]->child).push_back(newNode(90));
 
    (root->child[2]->child).push_back(newNode(100));
 
    (root->child[2]->child).push_back(newNode(110));
 
    return root;
}
 
// Driver Code
int main()
{
 
    // Stores root of the
    // constructed tree
    Node* root = constructTree();
 
    int X = 30;
    // Print siblings of Node X
    Siblings(root, X);
 
    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<>();
};
 
// Function to create a
// new node
static Node newNode(int key)
{
  Node temp = new Node();
  temp.key = key;
  return temp;
}
 
// Function to find the
// siblings of the node
/// value
static void Siblings(Node root,
                     int value)
{
  int flag = 0;
 
  if (root == null)
    return;
 
  // Stores nodes level wise
  Queue<Node> q =
    new LinkedList<>();
 
  // Push the root
  q.add(root);
 
  // Continue until all
  // levels are traversed
  while (!q.isEmpty())
  {
    // Stores current node
    Node temp = q.peek();
    q.remove();
 
    // Enqueue all children
    // of the current node
    for (int i = 0;
         i < temp.child.size();
         i++)
    {
      // If node value is found
      if (temp.child.get(i).key ==
          value)
      {
        flag = 1;
 
        // Print all children of current
        // node
        // except value as the answer
        for (int j = 0;
             j < temp.child.size();
             j++)
        {
          if (value !=
              temp.child.get(j).key)
            System.out.print(
            temp.child.get(j).key + " ");
        }
        break;
      }
 
      // Push the child nodes
      // of temp into the queue
      q.add(temp.child.get(i));
    }
  }
 
  if (flag == 0)
    System.out.print("No siblings!!");
}
 
static Node constructTree()
{
  Node root = newNode(10);
   
  (root.child).add(newNode(20));
  (root.child).add(newNode(30));
  (root.child).add(newNode(40));
  (root.child.get(0).child).add(newNode(50));
  (root.child.get(0).child).add(newNode(60));
  (root.child.get(1).child).add(newNode(70));
  (root.child.get(1).child).add(newNode(80));
  (root.child.get(2).child).add(newNode(90));
  (root.child.get(2).child).add(newNode(100));
  (root.child.get(2).child).add(newNode(110));
 
  return root;
}
 
// Driver Code
public static void main(String[] args)
{
  // Stores root of the
  // constructed tree
  Node root = constructTree();
 
  int X = 30;
  // Print siblings of Node X
  Siblings(root, X);
}
}
 
// This code is contributed by Rajput-Ji

C#

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Structure of a node
// of N-ary tree
public class Node
{
  public int key;
  public List<Node> child =
         new List<Node>();
};
 
// Function to create a
// new node
static Node newNode(int key)
{
  Node temp = new Node();
  temp.key = key;
  return temp;
}
 
// Function to find the
// siblings of the node
/// value
static void Siblings(Node root,
                     int value)
{
  int flag = 0;
 
  if (root == null)
    return;
 
  // Stores nodes level
  // wise
  Queue<Node> q =
        new Queue<Node>();
 
  // Push the root
  q.Enqueue(root);
 
  // Continue until all
  // levels are traversed
  while (q.Count != 0)
  {
    // Stores current node
    Node temp = q.Peek();
    q.Dequeue();
 
    // Enqueue all children
    // of the current node
    for (int i = 0;
             i < temp.child.Count; i++)
    {
      // If node value is found
      if (temp.child[i].key == value)
      {
        flag = 1;
 
        // Print all children of
        // current node except value
        // as the answer
        for (int j = 0;
             j < temp.child.Count; j++)
        {
          if (value != temp.child[j].key)
            Console.Write(temp.child[j].key + " ");
        }
        break;
      }
 
      // Push the child nodes
      // of temp into the queue
      q.Enqueue(temp.child[i]);
    }
  }
 
  if (flag == 0)
    Console.Write("No siblings!!");
}
 
static Node constructTree()
{
  Node root = newNode(10);
 
  (root.child).Add(newNode(20));
  (root.child).Add(newNode(30));
  (root.child).Add(newNode(40));
  (root.child[0].child).Add(newNode(50));
  (root.child[0].child).Add(newNode(60));
  (root.child[1].child).Add(newNode(70));
  (root.child[1].child).Add(newNode(80));
  (root.child[2].child).Add(newNode(90));
  (root.child[2].child).Add(newNode(100));
  (root.child[2].child).Add(newNode(110));
 
  return root;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Stores root of the
  // constructed tree
  Node root = constructTree();
 
  int X = 30;
   
  // Print siblings of Node X
  Siblings(root, X);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program for the above approach
 
// Structure of a node of N-ary tree
class Node
{
    constructor(key)
    {
        this.child = [];
        this.key = key;
    }
}
 
// Function to create a
// new node
function newNode(key)
{
    let temp = new Node(key);
    return temp;
}
 
// Function to find the
// siblings of the node
/// value
function Siblings(root, value)
{
    let flag = 0;
     
    if (root == null)
        return;
     
    // Stores nodes level wise
    let q = [];
     
    // Push the root
    q.push(root);
     
    // Continue until all
    // levels are traversed
    while (q.length > 0)
    {
         
        // Stores current node
        let temp = q[0];
        q.shift();
         
        // Enqueue all children
        // of the current node
        for(let i = 0; i < temp.child.length; i++)
        {
             
            // If node value is found
            if (temp.child[i].key == value)
            {
                flag = 1;
                 
                // Print all children of current
                // node
                // except value as the answer
                for(let j = 0;
                        j < temp.child.length;
                        j++)
                {
                    if (value != temp.child[j].key)
                        document.write(temp.child[j].key + " ");
                }
                break;
            }
             
            // Push the child nodes
            // of temp into the queue
            q.push(temp.child[i]);
        }
    }
     
    if (flag == 0)
    document.write("No siblings!!");
}
 
function constructTree()
{
    let root = newNode(10);
     
    (root.child).push(newNode(20));
    (root.child).push(newNode(30));
    (root.child).push(newNode(40));
    (root.child[0].child).push(newNode(50));
    (root.child[0].child).push(newNode(60));
    (root.child[1].child).push(newNode(70));
    (root.child[1].child).push(newNode(80));
    (root.child[2].child).push(newNode(90));
    (root.child[2].child).push(newNode(100));
    (root.child[2].child).push(newNode(110));
     
    return root;
}
 
// Driver code
 
// Stores root of the
// constructed tree
let root = constructTree();
 
let X = 30;
 
// Print siblings of Node X
Siblings(root, X);
 
// This code is contributed by divyeshrabadiya07
 
</script>
Producción: 

20 40

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

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 *