Znajdź węzeł podczas przemieszczania drzewa

Question

Chcę zaimplementować metodę, która pozwoli mi znaleźć węzeł w drzewie. Sposób, w jaki to robię, rekursywnie używa zmiennych globalnych, aby wiedzieć, kiedy przestać.

mam klasę:

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

a sposób mam teraz jest:

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

    } 

i sposób używam metoda Find jest jak:

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

Moje pytanie brzmi:, jak mogę uczynić tę metodę bardziej elegancką. będzie tak jak podpis metody wyglądać:

public Node FindNode(Node rootNode); 

myślę, że jest redundantny co robię i nie ma chyba lepszego sposobu tworzenia tej metody. A może mógłbym zmienić klasę węzła, aby osiągnąć to samo z zapytaniem linq.

Answer 1

chciałbym zrobić to w ten sposób:

napisać metodę instancji wygenerować poddrzewo węzła (można zrobić to rozszerzenie, jeśli nie kontrolują klasę Node):

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

Następnie można po prostu znaleźć węzły z odrobiną LINQ:

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

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

Answer 2

Rozważ stworzenie interfejsu API podobnego do LINQ: podziel części "Znajdź" i "Ustaw", aby było prostsze. Możesz nawet nie potrzebować specjalnego niestandardowego kodu dla części "Act", wystarczy istniejący LINQ.

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

W zależności od potrzeb można albo chodzić całe drzewo raz i sprawdzić każdy węzeł wdrożyć przypadku, czy to prawidłowo z leniwej iteracji. Do leniwej iteracji potrzebujesz jakiejś struktury, która zapamiętuje aktualną pozycję (np. Stos węzłów do odwiedzenia i indeks dziecka).

Uwaga: proszę unikać używania zmiennych globalnych. To znaczy. w twoim aktualnym kodzie po prostu zwracanie wartości true/false z funkcji Find i zatrzymywanie iteracji, gdy zwracana jest wartość true, byłoby lepszym rozwiązaniem.

Answer 3

można użyć jednej z pozostałych odpowiedzi, które używać LINQ, można też wykorzystać do głębokości pierwszego mechanizmu przeszukiwania za pomocą rec urs:

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

Jeśli odpowiedzi linq dezorientują Cię tak samo jak ja, oto jak zrobiłbym to z prostą rekurencją. Zauważ, że najpierw jest głębia, możesz najpierw zmienić ją na szerokość, jeśli ma to więcej sensu dla Twojego modelu.

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

Można też użyć przeszukiwanie w głąb za pomocą rekurencji (nie potrzeba do zmiennej globalnej wiedzieć kiedy zakończyć):

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

Albo, jeśli chcesz uniknąć rekursji, można osiągnąć to samo bez rekurencyjnie ze stosu:

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

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

I Telefoniczny kod:

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