Dado un árbol, con N Nodes y E aristas (cada arista se denota con dos números enteros, X, Y indicando que X es el padre de Y), la tarea es imprimir todos los Nodes con sus hermanos correctos en líneas separadas.
Si no hay un hermano correcto para un Node en particular, imprima -1 en su lugar.
Ejemplos:
En la imagen que se muestra arriba, los Nodes 3, 5, 6, 7 son los hermanos derechos de los Nodes 2, 4, 5, 6 respectivamente y los Nodes 1, 3 y 7 no tienen hermanos derechos.
Entrada: N = 7, E = 6
aristas[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7 }}
Salida: 1 -1
2 3
3 -1
4 5
5 6
6 7
7 -1Entrada: N = 5, E = 4
aristas[][] = {{7, 8}, {7, 10}, {7, 15}, {10, 3}}
Salida: 7 -1
8 10
10 15
15 -1
3 -1
Enfoque: La idea principal es utilizar un recorrido transversal primero en amplitud .
- Inicialmente, el Node raíz y el valor ‘-1’ se colocarán en la cola. Después de que cada Node de un nivel en particular en el árbol haya sido enviado a la cola, se debe presionar ‘-1’ para asegurarse de que el último Node en el nivel no tenga un hermano correcto.
- Después de sacar cada Node de la cola, el Node al frente de la cola siempre será el hermano derecho del Node sacado.
- Si el Node extraído tiene el valor ‘-1’, significa que se ha visitado el nivel actual y si la cola no está vacía, significa que los Nodes anteriores de este nivel tienen al menos un hijo que no se ha visitado.
- Repita los pasos anteriores mientras la cola no esté vacía.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print right siblings
// of all the nodes in a tree
#include <bits/stdc++.h>
using namespace std;
void PrintSiblings(int root, int N, int E, vector<int> adj[])
{
// boolean array to mark the visited nodes
vector<bool> vis(N+1, false);
// queue data structure to implement bfs
queue<int> q;
q.push(root);
q.push(-1);
vis[root] = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == -1) {
// if queue is empty then
// the popped node is the last node
// no need to push -1.
if (!q.empty())
q.push(-1);
continue;
}
// node and its right sibling
cout << node << " " << q.front() << "\n";
for (auto s : adj[node]) {
if (!vis[s]) {
vis[s] = 1;
q.push(s);
}
}
}
}
// Driver code
int main()
{
// nodes and edges
int N = 7, E = 6;
vector<int> adj[N+1];
// The tree is represented in the form of
// an adjacency list as there can be
// multiple children of a node
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[3].push_back(6);
adj[3].push_back(7);
int root = 1;
PrintSiblings(root, N, E, adj);
return 0;
}
Java
// Java program to print right siblings
// of all the nodes in a tree
import java.util.*;
class GFG
{
static void PrintSiblings(int root, int N,
int E, Vector<Integer> adj[])
{
// boolean array to mark the visited nodes
boolean []vis = new boolean[N + 1];
// queue data structure to implement bfs
Queue<Integer> q = new LinkedList<>();
q.add(root);
q.add(-1);
vis[root] = true;
while (!q.isEmpty())
{
int node = q.peek();
q.remove();
if (node == -1)
{
// if queue is empty then
// the popped node is the last node
// no need to push -1.
if (!q.isEmpty())
q.add(-1);
continue;
}
// node and its right sibling
System.out.print(node + " " +
q.peek() + "\n");
for (Integer s : adj[node])
{
if (!vis[s])
{
vis[s] = true;
q.add(s);
}
}
}
}
// Driver code
public static void main(String[] args)
{
// nodes and edges
int N = 7, E = 6;
Vector<Integer> []adj = new Vector[N + 1];
for(int i = 0; i < N + 1; i++)
adj[i] = new Vector<Integer>();
// The tree is represented in the form of
// an adjacency list as there can be
// multiple children of a node
adj[1].add(2);
adj[1].add(3);
adj[2].add(4);
adj[2].add(5);
adj[3].add(6);
adj[3].add(7);
int root = 1;
PrintSiblings(root, N, E, adj);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to print right # siblings of all the nodes in # a tree def PrintSiblings(root, N, E, adj): # Boolean array to mark the # visited nodes vis = [False for i in range(N + 1)] # queue data structure to # implement bfs q = [] q.append(root) q.append(-1) vis[root] = 1 while (len(q) != 0): node = q[0] q.pop(0) if (node == -1): # If queue is empty then the # popped node is the last node # no need to append -1. if (len(q) != 0): q.append(-1) continue # Node and its right sibling print(str(node) + " " + str(q[0])) for s in adj[node]: if (not vis[s]): vis[s] = True q.append(s) # Driver code if __name__=='__main__': # Nodes and edges N = 7 E = 6 adj = [[] for i in range(N + 1)] # The tree is represented in the # form of an adjacency list as # there can be multiple children # of a node adj[1].append(2) adj[1].append(3) adj[2].append(4) adj[2].append(5) adj[3].append(6) adj[3].append(7) root = 1 PrintSiblings(root, N, E, adj) # This code is contributed by rutvik_56
C#
// C# program to print right siblings
// of all the nodes in a tree
using System;
using System.Collections.Generic;
class GFG
{
static void PrintSiblings(int root, int N,
int E, List<int> []adj)
{
// bool array to mark the visited nodes
bool []vis = new bool[N + 1];
// queue data structure to implement bfs
Queue<int> q = new Queue<int>();
q.Enqueue(root);
q.Enqueue(-1);
vis[root] = true;
while (q.Count != 0)
{
int node = q.Peek();
q.Dequeue();
if (node == -1)
{
// if queue is empty then
// the popped node is the last node
// no need to push -1.
if (q.Count != 0)
q.Enqueue(-1);
continue;
}
// node and its right sibling
Console.Write(node + " " +
q.Peek() + "\n");
foreach (int s in adj[node])
{
if (!vis[s])
{
vis[s] = true;
q.Enqueue(s);
}
}
}
}
// Driver code
public static void Main(String[] args)
{
// nodes and edges
int N = 7, E = 6;
List<int> []adj = new List<int>[N + 1];
for(int i = 0; i < N + 1; i++)
adj[i] = new List<int>();
// The tree is represented in the form of
// an adjacency list as there can be
// multiple children of a node
adj[1].Add(2);
adj[1].Add(3);
adj[2].Add(4);
adj[2].Add(5);
adj[3].Add(6);
adj[3].Add(7);
int root = 1;
PrintSiblings(root, N, E, adj);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print right siblings
// of all the nodes in a tree
function PrintSiblings(root, N, E, adj)
{
// boolean array to mark the visited nodes
let vis = new Array(N + 1);
// queue data structure to implement bfs
let q = [];
q.push(root);
q.push(-1);
vis[root] = true;
while (q.length > 0)
{
let node = q[0];
q.shift();
if (node == -1)
{
// if queue is empty then
// the popped node is the last node
// no need to push -1.
if (q.length > 0)
q.push(-1);
continue;
}
// node and its right sibling
document.write(node + " " + q[0] + "</br>");
for (let s = 0; s < adj[node].length; s++)
{
if (!vis[adj[node][s]])
{
vis[adj[node][s]] = true;
q.push(adj[node][s]);
}
}
}
}
// nodes and edges
let N = 7, E = 6;
let adj = new Array(N + 1);
for(let i = 0; i < N + 1; i++)
adj[i] = [];
// The tree is represented in the form of
// an adjacency list as there can be
// multiple children of a node
adj[1].push(2);
adj[1].push(3);
adj[2].push(4);
adj[2].push(5);
adj[3].push(6);
adj[3].push(7);
let root = 1;
PrintSiblings(root, N, E, adj);
// This code is contributed by decode2207.
</script>
Producción:
1 -1 2 3 3 -1 4 5 5 6 6 7 7 -1