Tengo una estructura de datos de árbol con N nodos secundarios de primer nivel que también tienen hijos.Encontrar la profundidad máxima de un árbol
Por ejemplo:
I que está Me gustaría saber cuál de los braches tiene la mayor profundidad. Como en el ejemplo anterior será
nodo 1 - Node11 - Node111 - Node1111
que tiene una profundidad de cuatro niveles.
¿Alguna sugerencia?
Gracias!
Debe verificar todos los nodos. Hace varios meses he implementado este algoritmo de esta manera:
class Node
{
public String Name { get; private set; }
public IList<Node> Childs { get; private set; }
public Node(String name)
{
Name = name;
Childs = new List<Node>();
}
public List<Node> Depth
{
get
{
List<Node> path = new List<Node>();
foreach (Node node in Childs)
{
List<Node> tmp = node.Depth;
if (tmp.Count > path.Count)
path = tmp;
}
path.Insert(0, this);
return path;
}
}
public override string ToString()
{
return Name;
}
}
Ejemplo de prueba:
Node node1111 = new Node("Node1111");
Node node111 = new Node("Node111");
Node node11 = new Node("Node11");
Node node12 = new Node("Node12");
Node node1 = new Node("Node1");
Node root = new Node("Root");
Node node2 = new Node("Node2");
Node node21 = new Node("Node21");
Node node211 = new Node("Node211");
root.Childs.Add(node1);
root.Childs.Add(node2);
node1.Childs.Add(node11);
node1.Childs.Add(node12);
node11.Childs.Add(node111);
node111.Childs.Add(node1111);
node2.Childs.Add(node21);
node21.Childs.Add(node211);
List<Node> path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
Node node2111 = new Node("Node2111");
node2111.Childs.Add(new Node("Node21111"));
node211.Childs.Add(node2111);
path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
consola de salida:
Root - Node1 - Node11 - Node111 - Node1111 -
Root - Node2 - Node21 - Node211 - Node2111 - Node21111 -
Esto es casi de la misma manera que lo hice, pero tuve que implementarlo en C. – WarmWaffles
Buena solución. Dos sugerencias Primero, "Profundidad" está mal nombrado. No devuelve la profundidad. Debería llamarse "PathToDeepestLeaf". En segundo lugar, las propiedades deberían reservarse para (1) cosas que son lógicamente _propiedades_, como el color o la profundidad, cosas complejas no complejas como "ruta a la hoja más baja", (2) cosas que son muy rápidas de calcular, en el mismo orden de velocidad como acceder a un campo. Haría de esto un método, no una propiedad. –
Un desafío para ti: el árbol podría ser muy, muy profundo. Supongamos que tiene mil nodos de profundidad y que tanta recursión hará volar la pila. ¿Puedes hacerlo * sin recursion *? –
El más directo es un algoritmo de fuerza bruta que enumera cada ruta, guarda los punteros a todos los nodos y mide la profundidad. Para cada ruta que sea más larga que una ruta anterior, olvide todas las demás rutas y solo recuerde la más larga.
The deepest branch from a node is:
the longest of the respective deepest branches from each child node
prepended with the current node.
recorrer el árbol de profundidad primero o en amplitud, asignando a cada nodo de su profundidad. Recuerde el nodo con la profundidad más alta.
Navegue recusrivle desde ese nodo hacia la raíz. Esto te da la rama más grande. Puede haber más de una rama con la misma longitud.
Si usted tiene alguna forma de iterador sobre su árbol, entonces puede utilizar un enfoque perfectamente mundano para la profundidad máxima.
Aquí es una tontería de una sola línea que muestra el concepto de la búsqueda de la profundidad máxima alcanzable utilizando el sistema de archivos UNIX find, awk y tr:
find/-depth | tr -dc '/\n' \
| awk '{if (length($0) > max) { max=length($0)}}; END {print max}'
... find es el iterador, tr es una manipulación de datos "traducción" de una conjunto de caracteres en otro (en este caso se usa para -d (eliminar) el complemento (-c) del conjunto de caracteres único que se especifica (/). Por lo tanto, convierte cualquier ruta completa de UNIX en solo/separadores. Acabo de encontrar la línea de entrada más larga ... y ese es mi resultado.
Por supuesto, este enfoque no te ayudará mucho con tu tarea. Pero el concepto debe ser claro. :)
¿Es esta tarea? –
@Moron: ¿Qué quieres decir con la tarea? – Vincenzo
¿Sabes qué tarea es, verdad? –