Un árbol n-ario en informática es una colección de Nodes normalmente representados jerárquicamente de la siguiente manera.
- El árbol comienza en el Node raíz.
- Cada Node del árbol contiene una lista de referencias a sus Nodes secundarios.
- El número de hijos que tiene un Node es menor o igual que n.
Una representación típica del árbol n-ario utiliza una array de n referencias (o punteros) para almacenar elementos secundarios (tenga en cuenta que n es un límite superior en el número de elementos secundarios). ¿Podemos hacerlo mejor? la idea de la representación Izquierda-Hijo Derecha-Hermano es almacenar solo dos punteros en cada Node.
Es una representación diferente de un árbol n-ario donde en lugar de contener una referencia a todos y cada uno de los Nodes secundarios, un Node contiene solo dos referencias, primero una referencia a su primer hijo y la otra a su siguiente hermano inmediato. Esta nueva transformación no solo elimina la necesidad de conocer por adelantado el número de hijos que tiene un Node, sino que también limita el número de referencias a un máximo de dos, lo que facilita mucho la codificación. Una cosa a tener en cuenta es que en la representación anterior, un enlace entre dos Nodes denotaba una relación padre-hijo, mientras que en esta representación un enlace entre dos Nodes puede denotar una relación padre-hijo o una relación hermano-hermano.
Ventajas:
1. Esta representación ahorra memoria al limitar a dos el número máximo de referencias requeridas por Node.
2. Es más fácil codificar.
Desventajas:
1. Las operaciones básicas como buscar/insertar/eliminar tienden a llevar más tiempo porque para encontrar la posición adecuada tendríamos que atravesar todos los hermanos del Node que se busca/inserta/elimina (en el peor de los casos ).
La imagen de la izquierda es la representación normal de un árbol de 6 arios y la de la derecha es su representación correspondiente del hijo izquierdo y el hermano derecho.
Fuente de la imagen: https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree
Un problema de ejemplo:
ahora veamos un problema e intentemos resolverlo usando las dos representaciones discutidas para mayor claridad.
Dado un árbol genealógico. Encuentre el k-ésimo hijo de algún miembro X en el árbol.
El usuario ingresa dos cosas.
1. Un carácter P (que representa al padre cuyo hijo se va a encontrar)
2. Un número entero k (que representa el número del hijo)
El problema en sí parece bastante sencillo. El único problema aquí es que no se especifica el número máximo de hijos que puede tener un Node, lo que hace que sea bastante complicado construir el árbol.
Ejemplo:
Considere el siguiente árbol genealógico.
Input : A 2 Output : C In this case, the user wishes to know A's second child which according to the figure is C. Input : F 3 Output : K Similar to the first case, the user wishes to know F's third child which is K.
En este método, asumimos el número máximo de hijos que puede tener un Node y seguimos adelante. El único problema (obvio) con este método es el límite superior del número de hijos. Si el valor es demasiado bajo, el código fallará en ciertos casos y si el valor es demasiado alto, se desperdiciará innecesariamente una gran cantidad de memoria.
Si el programador conoce de antemano la estructura del árbol, entonces el límite superior se puede establecer en el número máximo de hijos que tiene un Node en esa estructura en particular. Pero incluso en ese caso, habrá algún desperdicio de memoria (es posible que no todos los Nodes tengan necesariamente el mismo número de hijos, algunos incluso pueden tener menos. Ejemplo: los Nodes hoja no tienen hijos ).
C++
// C++ program to find k-th child of a given
// node using typical representation that uses
// an array of pointers.
#include <iostream>
using namespace std;
// Maximum number of children
const int N = 10;
class Node
{
public:
char val;
Node * child[N];
Node(char P)
{
val = P;
for (int i=0; i<MAX; i++)
child[i] = NULL;
}
};
// Traverses given n-ary tree to find K-th
// child of P.
void printKthChild(Node *root, char P, int k)
{
// If P is current root
if (root->val == P)
{
if (root->child[k-1] == NULL)
cout << "Error : Does not exist\n";
else
cout << root->child[k-1]->val << endl;
}
// If P lies in a subtree
for (int i=0; i<N; i++)
if (root->child[i] != NULL)
printKthChild(root->child[i], P, k);
}
// Driver code
int main()
{
Node *root = new Node('A');
root->child[0] = new Node('B');
root->child[1] = new Node('C');
root->child[2] = new Node('D');
root->child[3] = new Node('E');
root->child[0]->child[0] = new Node('F');
root->child[0]->child[1] = new Node('G');
root->child[2]->child[0] = new Node('H');
root->child[0]->child[0]->child[0] = new Node('I');
root->child[0]->child[0]->child[1] = new Node('J');
root->child[0]->child[0]->child[2] = new Node('K');
root->child[2]->child[0]->child[0] = new Node('L');
root->child[2]->child[0]->child[1] = new Node('M');
// Print F's 2nd child
char P = 'F';
cout << "F's second child is : ";
printKthChild(root, P, 2);
P = 'A';
cout << "A's seventh child is : ";
printKthChild(root, P, 7);
return 0;
}
Java
// Java program to find k-th child
// of a given node using typical
// representation that uses
// an array of pointers.
class GFG
{
// Maximum number of children
static int N = 10;
static class Node
{
char val;
Node[] child = new Node[N];
Node(char P)
{
val = P;
for (int i = 0; i < N; i++)
child[i] = null;
}
};
// Traverses given n-ary tree to
// find K-th child of P.
static void printKthChild(Node root,
char P, int k)
{
// If P is current root
if (root.val == P)
{
if (root.child[k - 1] == null)
System.out.print("Error : Does not exist\n");
else
System.out.print(root.child[k - 1].val + "\n");
}
// If P lies in a subtree
for (int i = 0; i < N; i++)
if (root.child[i] != null)
printKthChild(root.child[i], P, k);
}
// Driver code
public static void main(String[] args)
{
Node root = new Node('A');
root.child[0] = new Node('B');
root.child[1] = new Node('C');
root.child[2] = new Node('D');
root.child[3] = new Node('E');
root.child[0].child[0] = new Node('F');
root.child[0].child[1] = new Node('G');
root.child[2].child[0] = new Node('H');
root.child[0].child[0].child[0] = new Node('I');
root.child[0].child[0].child[1] = new Node('J');
root.child[0].child[0].child[2] = new Node('K');
root.child[2].child[0].child[0] = new Node('L');
root.child[2].child[0].child[1] = new Node('M');
// Print F's 2nd child
char P = 'F';
System.out.print("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
System.out.print("A's seventh child is : ");
printKthChild(root, P, 7);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find k-th child of a given
# node using typical representation that uses
# an array of pointers.
# Maximum number of children
N = 10
class Node:
def __init__(self , P):
self.val = P
self.child = []
for i in range(10):
self.child.append(None)
# Traverses given n-ary tree to find K-th
# child of P.
def printKthChild(root, P, k):
# If P is current root
if (root.val == P):
if (root.child[k - 1] == None):
print("Error : Does not exist")
else:
print( root.child[k - 1].val )
# If P lies in a subtree
for i in range(N) :
if (root.child[i] != None):
printKthChild(root.child[i], P, k)
# Driver code
root = Node('A')
root.child[0] = Node('B')
root.child[1] = Node('C')
root.child[2] = Node('D')
root.child[3] = Node('E')
root.child[0].child[0] = Node('F')
root.child[0].child[1] = Node('G')
root.child[2].child[0] = Node('H')
root.child[0].child[0].child[0] = Node('I')
root.child[0].child[0].child[1] = Node('J')
root.child[0].child[0].child[2] = Node('K')
root.child[2].child[0].child[0] = Node('L')
root.child[2].child[0].child[1] = Node('M')
# Print F's 2nd child
P = 'F'
print( "F's second child is : ")
printKthChild(root, P, 2)
P = 'A'
print( "A's seventh child is : ")
printKthChild(root, P, 7)
# This code is contributed by Arnab Kundu
C#
// C# program to find k-th child
// of a given node using typical
// representation that uses
// an array of pointers.
using System;
class GFG
{
// Maximum number of children
static int N = 10;
class Node
{
public char val;
public Node[] child = new Node[N];
public Node(char P)
{
val = P;
for (int i = 0; i < N; i++)
child[i] = null;
}
};
// Traverses given n-ary tree to
// find K-th child of P.
static void printKthChild(Node root,
char P, int k)
{
// If P is current root
if (root.val == P)
{
if (root.child[k - 1] == null)
Console.Write("Error : Does not exist\n");
else
Console.Write(root.child[k - 1].val + "\n");
}
// If P lies in a subtree
for (int i = 0; i < N; i++)
if (root.child[i] != null)
printKthChild(root.child[i], P, k);
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node('A');
root.child[0] = new Node('B');
root.child[1] = new Node('C');
root.child[2] = new Node('D');
root.child[3] = new Node('E');
root.child[0].child[0] = new Node('F');
root.child[0].child[1] = new Node('G');
root.child[2].child[0] = new Node('H');
root.child[0].child[0].child[0] = new Node('I');
root.child[0].child[0].child[1] = new Node('J');
root.child[0].child[0].child[2] = new Node('K');
root.child[2].child[0].child[0] = new Node('L');
root.child[2].child[0].child[1] = new Node('M');
// Print F's 2nd child
char P = 'F';
Console.Write("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
Console.Write("A's seventh child is : ");
printKthChild(root, P, 7);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find k-th child of a
// given node using typical representation that
// uses an array of pointers.Maximum number of children
var N = 10;
class Node
{
constructor(P)
{
this.val = P;
this.child = Array(N).fill(null);
}
};
// Traverses given n-ary tree to
// find K-th child of P.
function printKthChild(root, P, k)
{
// If P is current root
if (root.val == P)
{
if (root.child[k - 1] == null)
document.write("Error : Does not exist<br>");
else
document.write(root.child[k - 1].val + "<br>");
}
// If P lies in a subtree
for(var i = 0; i < N; i++)
if (root.child[i] != null)
printKthChild(root.child[i], P, k);
}
// Driver code
var root = new Node('A');
root.child[0] = new Node('B');
root.child[1] = new Node('C');
root.child[2] = new Node('D');
root.child[3] = new Node('E');
root.child[0].child[0] = new Node('F');
root.child[0].child[1] = new Node('G');
root.child[2].child[0] = new Node('H');
root.child[0].child[0].child[0] = new Node('I');
root.child[0].child[0].child[1] = new Node('J');
root.child[0].child[0].child[2] = new Node('K');
root.child[2].child[0].child[0] = new Node('L');
root.child[2].child[0].child[1] = new Node('M');
// Print F's 2nd child
var P = 'F';
document.write("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
document.write("A's seventh child is : ");
printKthChild(root, P, 7);
// This code is contributed by noob2000
</script>
Producción:
F's second child is : J A's seventh child is : Error : Does not exist
En el árbol anterior, si hubiera habido un Node que tuviera, digamos, 15 hijos, entonces este código habría dado una falla de segmentación.
En este método, cambiamos la estructura del árbol genealógico. En el árbol estándar, cada Node padre está conectado a todos sus hijos. Aquí, como se discutió anteriormente, en lugar de que cada Node almacene punteros a todos sus elementos secundarios, un Node almacenará el puntero a solo uno de sus elementos secundarios. Aparte de esto, el Node también almacenará un puntero a su hermano derecho inmediato.
La imagen de abajo es el equivalente de Left-Child Right-Sibling del ejemplo usado arriba.
C++
// C++ program to find k-th child of a given
// Node using typical representation that uses
// an array of pointers.
#include <iostream>
using namespace std;
// A Node to represent left child right sibling
// representation.
class Node
{
public:
char val;
Node *child;
Node *next;
Node(char P)
{
val = P;
child = NULL;
next = NULL;
}
};
// Traverses given n-ary tree to find K-th
// child of P.
void printKthChild(Node *root, char P, int k)
{
if (root == NULL)
return;
// If P is present at root itself
if (root->val == P)
{
// Traverse children of root starting
// from left child
Node *t = root->child;
int i = 1;
while (t != NULL && i < k)
{
t = t->next;
i++;
}
if (t == NULL)
cout << "Error : Does not exist\n";
else
cout << t->val << " " << endl;
return;
}
printKthChild(root->child, P, k);
printKthChild(root->next, P, k);
}
// Driver code
int main()
{
Node *root = new Node('A');
root->child = new Node('B');
root->child->next = new Node('C');
root->child->next->next = new Node('D');
root->child->next->next->next = new Node('E');
root->child->child = new Node('F');
root->child->child->next = new Node('G');
root->child->next->next->child = new Node('H');
root->child->next->next->child->child = new Node('L');
root->child->next->next->child->child->next = new Node('M');
root->child->child->child = new Node('I');
root->child->child->child->next = new Node('J');
root->child->child->child->next->next = new Node('K');
// Print F's 2nd child
char P = 'F';
cout << "F's second child is : ";
printKthChild(root, P, 2);
P = 'A';
cout << "A's seventh child is : ";
printKthChild(root, P, 7);
return 0;
}
Java
// Java program to find k-th child of a given
// Node using typical representation that uses
// an array of pointers.
class GFG
{
// A Node to represent left child
// right sibling representation.
static class Node
{
char val;
Node child;
Node next;
Node(char P)
{
val = P;
child = null;
next = null;
}
};
// Traverses given n-ary tree to find K-th
// child of P.
static void printKthChild(Node root, char P, int k)
{
if (root == null)
return;
// If P is present at root itself
if (root.val == P)
{
// Traverse children of root starting
// from left child
Node t = root.child;
int i = 1;
while (t != null && i < k)
{
t = t.next;
i++;
}
if (t == null)
System.out.print("Error : Does not exist\n");
else
System.out.print(t.val + " " + "\n");
return;
}
printKthChild(root.child, P, k);
printKthChild(root.next, P, k);
}
// Driver code
public static void main(String[] args)
{
Node root = new Node('A');
root.child = new Node('B');
root.child.next = new Node('C');
root.child.next.next = new Node('D');
root.child.next.next.next = new Node('E');
root.child.child = new Node('F');
root.child.child.next = new Node('G');
root.child.next.next.child = new Node('H');
root.child.next.next.child.child = new Node('L');
root.child.next.next.child.child.next = new Node('M');
root.child.child.child = new Node('I');
root.child.child.child.next = new Node('J');
root.child.child.child.next.next = new Node('K');
// Print F's 2nd child
char P = 'F';
System.out.print("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
System.out.print("A's seventh child is : ");
printKthChild(root, P, 7);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to find k-th child of a given
# Node using typical representation that uses
# an array of pointers.
# A Node to represent left child
# right sibling representation.
class Node:
def __init__(self,P):
self.val = P
self.child = None
self.next = None
# Traverses given n-ary tree to find K-th
# child of P.
def printKthChild(root, P, k):
if (root == None):
return
# If P is present at root itself
if (root.val == P):
# Traverse children of root starting
# from left child
t = root.child
i = 1
while (t != None and i < k):
t = t.next
i += 1
if (t == None):
print("Error : Does not exist")
else:
print(t.val)
return
printKthChild(root.child, P, k)
printKthChild(root.next, P, k)
# Driver code
root = Node('A')
root.child = Node('B')
root.child.next = Node('C')
root.child.next.next = Node('D')
root.child.next.next.next = Node('E')
root.child.child = Node('F')
root.child.child.next = Node('G')
root.child.next.next.child = Node('H')
root.child.next.next.child.child = Node('L')
root.child.next.next.child.child.next = Node('M')
root.child.child.child = Node('I')
root.child.child.child.next = Node('J')
root.child.child.child.next.next = Node('K')
# Print F's 2nd child
P = 'F'
print("F's second child is :",end=" ")
printKthChild(root, P, 2)
P = 'A'
print("A's seventh child is :",end=" ")
printKthChild(root, P, 7)
# this code is contributed by shinjanpatra
C#
// C# program to find k-th child of a given
// Node using typical representation that uses
// an array of pointers.
using System;
class GFG
{
// A Node to represent left child
// right sibling representation.
public class Node
{
public char val;
public Node child;
public Node next;
public Node(char P)
{
val = P;
child = null;
next = null;
}
};
// Traverses given n-ary tree to find K-th
// child of P.
static void printKthChild(Node root,
char P, int k)
{
if (root == null)
return;
// If P is present at root itself
if (root.val == P)
{
// Traverse children of root starting
// from left child
Node t = root.child;
int i = 1;
while (t != null && i < k)
{
t = t.next;
i++;
}
if (t == null)
Console.Write("Error : Does not exist\n");
else
Console.Write(t.val + " " + "\n");
return;
}
printKthChild(root.child, P, k);
printKthChild(root.next, P, k);
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node('A');
root.child = new Node('B');
root.child.next = new Node('C');
root.child.next.next = new Node('D');
root.child.next.next.next = new Node('E');
root.child.child = new Node('F');
root.child.child.next = new Node('G');
root.child.next.next.child = new Node('H');
root.child.next.next.child.child = new Node('L');
root.child.next.next.child.child.next = new Node('M');
root.child.child.child = new Node('I');
root.child.child.child.next = new Node('J');
root.child.child.child.next.next = new Node('K');
// Print F's 2nd child
char P = 'F';
Console.Write("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
Console.Write("A's seventh child is : ");
printKthChild(root, P, 7);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find k-th child of a given
// Node using typical representation that uses
// an array of pointers.
// A Node to represent left child
// right sibling representation.
class Node
{
constructor(P)
{
this.val = P;
this.child = null;
this.next = null;
}
}
// Traverses given n-ary tree to find K-th
// child of P.
function printKthChild(root, P, k)
{
if (root == null)
return;
// If P is present at root itself
if (root.val == P)
{
// Traverse children of root starting
// from left child
let t = root.child;
let i = 1;
while (t != null && i < k)
{
t = t.next;
i++;
}
if (t == null)
document.write("Error : Does not exist<br>");
else
document.write(t.val + " " + "<br>");
return;
}
printKthChild(root.child, P, k);
printKthChild(root.next, P, k);
}
// Driver code
let root = new Node('A');
root.child = new Node('B');
root.child.next = new Node('C');
root.child.next.next = new Node('D');
root.child.next.next.next = new Node('E');
root.child.child = new Node('F');
root.child.child.next = new Node('G');
root.child.next.next.child = new Node('H');
root.child.next.next.child.child = new Node('L');
root.child.next.next.child.child.next = new Node('M');
root.child.child.child = new Node('I');
root.child.child.child.next = new Node('J');
root.child.child.child.next.next = new Node('K');
// Print F's 2nd child
let P = 'F';
document.write("F's second child is : ");
printKthChild(root, P, 2);
P = 'A';
document.write("A's seventh child is : ");
printKthChild(root, P, 7);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
F's second child is : J A's seventh child is : Error : Does not exist
Artículo relacionado:
Creación de un árbol con representación de hijo izquierdo-hermano derecho
Este artículo es una contribución de Akhil Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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