Knoten beim Query Tree suchen

Question

Ich möchte eine Methode implementieren, die es mir ermöglicht, einen Knoten in einem Baum zu finden. Die Art, wie ich es mache, verwendet rekursiv globale Variablen, um zu wissen, wann ich aufhören soll.

Ich habe die Klasse:

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

Und die Methode, die ich jetzt habe, ist:

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

    } 

und die Art, wie ich die Find-Methode verwenden, ist wie:

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

Also meine Frage ist wie kann ich diese Methode eleganter machen. Ich werde wie die Signatur der Methode aussehen:

public Node FindNode(Node rootNode); 

Ich denke, es ist überflüssig, was soll ich tun, und es ist wahrscheinlich eine bessere Möglichkeit, dieses Verfahren zu schaffen. Oder vielleicht könnte ich die Node-Klasse ändern, so dass ich dasselbe mit einer linq-Abfrage erreichen kann.

Answer 1

Ich würde es auf diese Weise tun:

eine Instanz Methode Schreiben Sie einen Teilbaum eines Knotens zu erzeugen (könnte man es eine Erweiterung machen, wenn Sie die Node Klasse nicht kontrollieren):

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

Dann können Sie nur Knoten mit ein wenig von LINQ finden:

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

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

Answer 2

Überlegen Sie, LINQ-ähnliche API zu machen: Split "Find" und "Act" Teile, um es einfach zu machen. Sie brauchen nicht einmal einen speziellen benutzerdefinierten Code für den "Act" -Teil, das vorhandene LINQ reicht aus.

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

Je nach Bedarf können Sie entweder zu Fuß einmal ganzen Baumes und überprüfen jeden Knoten Wo zu implementieren, oder tut es richtig mit fauler Iteration. Für eine faule Iteration benötigen Sie eine Struktur, die sich an die aktuelle Position erinnert (d. H. Stapel von zu besuchenden Knoten und Index von Kind).

Hinweis: Bitte verwenden Sie keine globalen Variablen. I.e. in Ihrem aktuellen Code, der einfach true/false von der Suchfunktion zurückgibt und die Iteration stoppt, wenn true zurückgegeben wird, wäre eine bessere Annäherung.

Answer 3

Sie eine der anderen Antworten verwenden können, die Linq verwenden, oder Sie können einen Tiefensuchmechanismus rec verwenden 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

Wenn die Linq Antworten verwirren Sie so viel wie ich, hier ist, wie ich es mit einfachen Rekursion tun würde. Beachten Sie, dass es zuerst an der Tiefe liegt. Vielleicht möchten Sie zuerst die Breite ändern, wenn dies für Ihr Modell sinnvoller ist.

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

Sie entweder eine Tiefensuche mit Rekursion verwenden können (keine Notwendigkeit für eine globale Variable wissen, wann zu beenden):

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

Oder, wenn Sie Rekursion vermeiden möchten, können Sie erreichen die gleiche Sache nicht-rekursiv mit einem Stapel:

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

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

Und Telefonvorwahl:

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