Buscar nodo cuando se cruza el árbol

Question

Quiero implementar un método que me permita encontrar un nodo en un árbol. La forma en que lo hago es recursivamente usando variables globales para saber cuándo parar.

tengo la clase:

class Node // represents a node in the tree 
{ 
    // constructor 
    public Node() { 
      Children = new List<Node>(); 
    } 

    public List<Node> Children; 
    public string Name; 
    public string Content;    
} 

Y el método que tengo ahora es:

private bool IsNodeFound = false; // global variable that I use to decide when to stop 

    // method to find a particular node in the tree 
    private void Find(Node node, string stringToFind, Action<Node> foundNode) 
    { 
     if(IsNodeFound) 
      return; 

     if (node.Content.Contains(stringToFind)){ 
      foundNode(node); 
      IsNodeFound =true;    
     } 

     foreach (var child in node.Children) 
     { 
      if (child.Content.Contains(stringToFind)){ 
       foundNode(node); 
       IsNodeFound =true;    
      } 

      Find(child, stringToFind, foundNode); 
     } 

    } 

y la forma en que uso el método Find es como:

// root is a node that contain children and those children also contain children 
    // root is the "root" of the tree 
    IsNodeFound =false; 
    Node nodeToFind = null; 
    Find(root, "some string to look for", (x)=> nodeToFind=x); 

Así que mi pregunta es cómo puedo hacer que este método sea más elegante. Me gustaría la firma del método para que parezca:

public Node FindNode(Node rootNode); 

Creo que es redundante a lo que estoy haciendo y es probable que haya una mejor manera de crear ese método. O quizás podría alterar la clase Node para que pueda lograr lo mismo con una consulta linq.

Answer 1

lo haría de esta manera:

Escribir un método de instancia para generar un subárbol de un nodo (que podría hacer una extensión si no se controla la clase Node):

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy 
{ 
    return new[] { this } 
      .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));  
} 

a continuación, puedes encontrar nodos con un poco de LINQ:

var foundNode = rootNode.GetNodeAndDescendants() 
         .FirstOrDefault(node => node.Content.Contains(stringToFind)); 

if(foundNode != null) 
{ 
    DoSomething(foundNode); 
} 

Answer 2

Considere crear API tipo LINQ: divida las partes "Buscar" y "Actuar" para que resulte sencillo. Es posible que ni siquiera necesite ningún código personalizado especial para la parte "Actuar", lo hará LINQ existente.

public IEnumerable<Node> Where(Func<Node, bool> condition); 

Dependiendo de sus necesidades usted puede caminar todo el árbol una vez y comprobar cada nodo para implementar Dónde, o hacerlo correctamente con iteración perezoso. Para la iteración diferida necesitarás algún tipo de estructura que recuerde la posición actual (es decir, la pila de nodos para visitar e índice del niño).

Nota: evite el uso de variables globales. Es decir. en su código actual, simplemente devolver true/false de la función Buscar y detener la iteración cuando se devuelve verdadero sería un mejor enfoque.

Answer 3

usted puede utilizar una de las otras respuestas que utilizan LINQ, o puede utilizar un mecanismo de búsqueda en profundidad utilizando rec ursion:

public Node Find(string stringToFind) 
{ 
    // find the string, starting with the current instance 
    return Find(this, stringToFind); 
} 

// Search for a string in the specified node and all of its children 
public Node Find(Node node, string stringToFind) 
{ 
    if (node.Content.Contains(stringToFind)) 
     return node; 

    foreach (var child in node.Children) 
    { 
     var result = Find(child, stringToFind); 
     if (result != null) 
      return result; 
    } 

    return null; 
} 

Answer 4

Si las respuestas LINQ se confunden tanto como yo, así es como lo haría con una simple recursividad. Tenga en cuenta que primero es la profundidad, es posible que desee cambiarla a amplitud primero si eso tiene más sentido para su modelo.

public Node FindNode(Node rootNode) 
{ 
    if (rootNode.Content.Contains(stringToFind)) 
     return rootNode; 

    foreach (Node node in rootNode.Children) 
    { 
     if (node.Content.Contains(stringToFind)) 
      return node; 
     else 
      return FindNode(node); 
    } 

    return null; 
} 

Answer 5

Puede utilizar una búsqueda en profundidad utilizando la recursividad (sin necesidad de una variable global para saber cuándo terminar):

Node FindNode1(Node rootNode, string stringToFind) { 
    if(rootNode.Content == stringToFind) return rootNode; 
    foreach(var child in rootNode.Children) { 
     var n = FindNode1(child, stringToFind); 
     if(n != null) return n; 
    } 
    return null; 
} 

O, si se desea evitar la repetición, se puede lograr lo mismo no recursiva con una pila:

Node FindNode2(Node rootNode, string stringToFind) { 
    var stack = new Stack<Node>(new[] { rootNode }); 
    while(stack.Any()) { 
     var n = stack.Pop(); 
     if(n.Content == stringToFind) return n; 
     foreach(var child in n.Children) stack.Push(child); 
    } 
    return null; 
} 

Answer 6

recursividad, y PLINQ

private Node Find(Node node, Func<Node, bool> predicate) 
    { 
     if (predicate(node)) 
      return node; 

     foreach (var n in node.Children.AsParallel()) 
     { 
      var found = Find(n, predicate); 
      if (found != default(Node)) 
       return found; 
     } 
     return default(Node); 
    } 

Y Código de llamada:

 var found = Find(root, (n) => n.Content.Contains("3")); 
    if (found != default(Node)) 
     Console.Write("found '{0}'", found.Name); 
    else Console.Write("not found");