Dados n Nodes de un árbol y sus conexiones, imprima los Nodes de subárbol de cada Node.
El subárbol de un Node se define como un árbol que es hijo de un Node. El nombre enfatiza que todo lo que es descendiente de un Node de árbol también es un árbol y es un subconjunto del árbol más grande.
Ejemplos:
Input: N = 5 0 1 1 2 0 3 3 4 Output: Subtree of node 0 is 1 2 3 4 Subtree of node 1 is 2 Subtree of node 3 is 4 Input: N = 7 0 1 1 2 2 3 0 4 4 5 4 6 Output: Subtree of node 0 is 1 2 3 4 5 6 Subtree of node 1 is 2 3 Subtree of node 4 is 5 6
Enfoque: realice un recorrido DFS para cada Node e imprima todos los Nodes a los que se puede acceder desde un Node en particular.
Explicación del siguiente código:
- Cuando se llama a la función dfs(0, 0), start[0] = 0, dfs_order.push_back(0),visited[0] = 1 para realizar un seguimiento del orden de dfs.
- Ahora, considere la lista de adyacencia (adj[100001]) considerando que los elementos de ruta direccional conectados al Node 0 estarán en la lista de adyacencia correspondiente al Node 0.
- Ahora, llame recursivamente a la función dfs hasta que todos los elementos atraviesen adj[0].
- Ahora, se llama a dfs(1, 2), ahora start[1] = 1, dfs_order.push_back(1), visited[1] = 1 después de atravesar los elementos adj[1].
- Ahora se atraviesa adj [1], que contiene solo el Node 2 cuando se atraviesa adj[2], no contiene ningún elemento, se romperá y terminará [1]=2.
- De manera similar, todos los Nodes recorridos y almacenan dfs_order en una array para encontrar el subárbol de Nodes.
C++
// C++ code to print subtree of all nodes
#include<bits/stdc++.h>
using namespace std;
// arrays for keeping position
// at each dfs traversal for each node
int start[100001];
int end[100001];
// Storing dfs order
vector<int>dfs_order;
vector<int>adj[100001];
int visited[100001];
// Recursive function for dfs
// traversal dfsUtil()
void dfs(int a,int &b)
{
// keep track of node visited
visited[a]=1;
b++;
start[a]=b;
dfs_order.push_back(a);
for(vector<int>:: iterator it=adj[a].begin();
it!=adj[a].end();it++)
{
if(!visited[*it])
{
dfs(*it,b);
}
}
endd[a]=b;
}
// Function to print the subtree nodes
void Print(int n)
{
for(int i = 0; i < n; i++)
{
// if node is leaf node
// start[i] is equals to endd[i]
if(start[i]!=endd[i])
{
cout<<"subtree of node "<<i<<" is ";
for(int j=start[i]+1;j<=endd[i];j++)
{
cout<<dfs_order[j-1]<<" ";
}
cout<<endl;
}
}
}
// Driver code
int main()
{
// No of nodes n = 10
int n =10, c = 0;
adj[0].push_back(1);
adj[0].push_back(2);
adj[0].push_back(3);
adj[1].push_back(4);
adj[1].push_back(5);
adj[4].push_back(7);
adj[4].push_back(8);
adj[2].push_back(6);
adj[6].push_back(9);
// Calling dfs for node 0
// Considering root node at 0
dfs(0, c);
// Print child nodes
Print(n);
return 0;
}
Java
// Java code to print subtree of all nodes
import java.util.*;
public class Main
{
// arrays for keeping position
// at each dfs traversal for each node
static int[] start = new int[100001];
static int[] end = new int[100001];
// Storing dfs order
static Vector<Integer> dfs_order = new Vector<Integer>();
static Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>();
static boolean[] visited = new boolean[100001];
// Recursive function for dfs traversal dfsUtil()
static int dfs(int a, int b)
{
// keep track of node visited
visited[a] = true;
b += 1;
start[a] = b;
dfs_order.add(a);
for(int it = 0; it < adj.get(a).size(); it++)
{
if(!visited[adj.get(a).get(it)])
b = dfs(adj.get(a).get(it), b);
}
endd[a] = b;
return b;
}
// Function to print the subtree nodes
static void Print(int n)
{
for(int i = 0; i < n; i++)
{
// If node is leaf node
// start[i] is equals to endd[i]
if(start[i] != endd[i])
{
System.out.print("subtree of node "+ i + " is ");
for(int j = start[i]+1; j < endd[i]+1; j++)
{
System.out.print(dfs_order.get(j-1) + " ");
}
System.out.println();
}
}
}
public static void main(String[] args) {
// No of nodes n = 10
int n =10, c = 0;
for(int i = 0; i < 100001; i++)
{
adj.add(new Vector<Integer>());
}
adj.get(0).add(1);
adj.get(0).add(2);
adj.get(0).add(3);
adj.get(1).add(4);
adj.get(1).add(5);
adj.get(4).add(7);
adj.get(4).add(8);
adj.get(2).add(6);
adj.get(6).add(9);
// Calling dfs for node 0
// Considering root node at 0
dfs(0, c);
// Print child nodes
Print(n);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 code to print subtree of all nodes
# arrays for keeping position at
# each dfs traversal for each node
start = [None] * 100001
end = [None] * 100001
# Storing dfs order
dfs_order = []
adj = [[] for i in range(100001)]
visited = [False] * 100001
# Recursive function for dfs traversal dfsUtil()
def dfs(a, b):
# keep track of node visited
visited[a] = 1
b += 1
start[a] = b
dfs_order.append(a)
for it in adj[a]:
if not visited[it]:
b = dfs(it, b)
endd[a] = b
return b
# Function to print the subtree nodes
def Print(n):
for i in range(0, n):
# If node is leaf node
# start[i] is equals to endd[i]
if start[i] != endd[i]:
print("subtree of node", i, "is", end = " ")
for j in range(start[i]+1, endd[i]+1):
print(dfs_order[j-1], end = " ")
print()
# Driver code
if __name__ == "__main__":
# No of nodes n = 10
n, c = 10, 0
adj[0].append(1)
adj[0].append(2)
adj[0].append(3)
adj[1].append(4)
adj[1].append(5)
adj[4].append(7)
adj[4].append(8)
adj[2].append(6)
adj[6].append(9)
# Calling dfs for node 0
# Considering root node at 0
dfs(0, c)
# Print child nodes
Print(n)
# This code is contributed by Rituraj Jain
C#
// C# code to print subtree of all nodes
using System;
using System.Collections.Generic;
class GFG {
// arrays for keeping position
// at each dfs traversal for each node
static int[] start = new int[100001];
static int[] end = new int[100001];
// Storing dfs order
static List<int> dfs_order = new List<int>();
static List<List<int>> adj = new List<List<int>>();
static bool[] visited = new bool[100001];
// Recursive function for dfs traversal dfsUtil()
static int dfs(int a, int b)
{
// keep track of node visited
visited[a] = true;
b += 1;
start[a] = b;
dfs_order.Add(a);
for(int it = 0; it < adj[a].Count; it++)
{
if(!visited[adj[a][it]])
b = dfs(adj[a][it], b);
}
endd[a] = b;
return b;
}
// Function to print the subtree nodes
static void Print(int n)
{
for(int i = 0; i < n; i++)
{
// If node is leaf node
// start[i] is equals to endd[i]
if(start[i] != endd[i])
{
Console.Write("subtree of node "+ i + " is ");
for(int j = start[i]+1; j < endd[i]+1; j++)
{
Console.Write(dfs_order[j-1] + " ");
}
Console.WriteLine();
}
}
}
static void Main() {
// No of nodes n = 10
int n =10, c = 0;
for(int i = 0; i < 100001; i++)
{
adj.Add(new List<int>());
}
adj[0].Add(1);
adj[0].Add(2);
adj[0].Add(3);
adj[1].Add(4);
adj[1].Add(5);
adj[4].Add(7);
adj[4].Add(8);
adj[2].Add(6);
adj[6].Add(9);
// Calling dfs for node 0
// Considering root node at 0
dfs(0, c);
// Print child nodes
Print(n);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript code to print subtree of all nodes
// arrays for keeping position
// at each dfs traversal for each node
let start = new Array(100001);
let end = new Array(100001);
// Storing dfs order
let dfs_order = [];
let adj = [];
for(let i = 0; i < 100001; i++)
{
adj.push([]);
}
let visited = new Array(100001);
visited.fill(false);
// Recursive function for dfs traversal dfsUtil()
function dfs(a, b)
{
// keep track of node visited
visited[a] = true;
b += 1;
start[a] = b;
dfs_order.push(a);
for(let it = 0; it < adj[a].length; it++)
{
if(!visited[adj[a][it]])
b = dfs(adj[a][it], b);
}
endd[a] = b;
return b;
}
// Function to print the subtree nodes
function Print(n)
{
for(let i = 0; i < n; i++)
{
// If node is leaf node
// start[i] is equals to endd[i]
if(start[i] != endd[i])
{
document.write("subtree of node "+ i + " is ");
for(let j = start[i]+1; j < endd[i]+1; j++)
{
document.write(dfs_order[j-1] + " ");
}
document.write("</br>");
}
}
}
// No of nodes n = 10
let n = 10, c = 0;
adj[0].push(1);
adj[0].push(2);
adj[0].push(3);
adj[1].push(4);
adj[1].push(5);
adj[4].push(7);
adj[4].push(8);
adj[2].push(6);
adj[6].push(9);
// Calling dfs for node 0
// Considering root node at 0
dfs(0, c);
// Print child nodes
Print(n);
// This code is contributed by suresh07.
</script>
Producción:
subtree of node 0 is 1 4 7 8 5 2 6 9 3 subtree of node 1 is 4 7 8 5 subtree of node 2 is 6 9 subtree of node 4 is 7 8 subtree of node 6 is 9
Complejidad temporal: O(N ^ 2)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por garg_ak0109 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA