Trova nodo quando si attraversa l'albero

Question

Desidero implementare un metodo che mi consenta di trovare un nodo in un albero. Il modo in cui lo faccio è ricorsivamente utilizzando le variabili globali per sapere quando fermarsi.

ho la classe:

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;    
} 

E il metodo che ho adesso è:

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); 
     } 

    } 

e il modo in cui io uso il metodo Find è come:

// 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); 

Quindi la mia domanda è come posso rendere questo metodo più elegante. Mi piacerà la firma del metodo per assomigliare:

public Node FindNode(Node rootNode); 

Credo che sia ridondanti cosa sto facendo e non v'è probabilmente un modo migliore di creare quel metodo. O forse potrei modificare la classe Node in modo che io possa ottenere la stessa cosa con una query linq.

Answer 1

vorrei fare in questo modo:

Scrivi un metodo di istanza per generare una sottostruttura di un nodo (si potrebbe fare un'estensione se non si controlla la classe Node):

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

allora si può solo trovare i nodi con un po 'di LINQ:

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

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

Answer 2

Considera di creare API LINQ-like: dividere le parti "Trova" e "Agisci" per renderlo più semplice. Potrebbe non essere necessario alcun codice personalizzato speciale per la parte "Act", LINQ esistente funzionerà.

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

A seconda delle necessità si può proseguire a piedi tutto l'albero una volta e verificare ogni nodo per implementare Dove, o farlo correttamente con l'iterazione pigro. Per l'iterazione pigra avrai bisogno di una sorta di struttura che ricordi la posizione corrente (cioè la pila di nodi da visitare e l'indice del bambino).

Nota: evitare l'uso di variabili globali. Cioè nel codice corrente semplicemente restituendo true/false dalla funzione Trova e interrompendo l'iterazione quando viene restituito true sarebbe un approccio migliore.

Answer 3

è possibile utilizzare una delle altre risposte che utilizzano LINQ, oppure è possibile utilizzare un meccanismo di ricerca in profondità con 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

Se le risposte LINQ si confondono tanto quanto me, ecco come lo farei con una semplice ricorsione. Notate prima la profondità, potreste volerla cambiare prima in larghezza se questo ha più senso per il vostro modello.

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

È possibile utilizzare una ricerca in profondità utilizzando la ricorsione (senza bisogno di una variabile globale per sapere quando terminare):

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, se si vuole evitare la ricorsione, è possibile ottenere la stessa cosa non ricorsivo 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

ricorsione, e 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); 
    } 

E il codice chiama:

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