Rekursive nicht binäre, nicht sortierte Baumsuche mit C# lambas

Question

class TreeNode 
{ 
    public string Value { get; set;} 
    public Collection<TreeNode> Nodes { get; set;} 


    public TreeNode() 
    { 
     Nodes = new Collection<TreeNode>(); 
    } 
} 

1) Wie würden Sie den rekursiven Lambda-Ausdruck schreiben, um den TreeNode mit einem bestimmten Wert zurückzugeben (oder null, falls nicht gefunden), vorausgesetzt, die Werte sind eindeutig? Natürlich kann # 1 mit # 2 beantwortet werden, aber ich denke, es könnte einen effizienteren Weg geben, wenn du weißt, dass es keine Duplikate gibt.

2) Angenommen, Werte sind nicht eindeutig und geben stattdessen eine Liste von Übereinstimmungen zurück?

Answer 1

Bearbeiten: Korrigiert den Code, ich habe in der Tat beide Teile des Codes kompilieren und testen, aber ich muss eingefügt haben in Versionen, bevor ich sie in VS behoben. Das tut mir leid.

Ich habe ein Subversion Repository mit dem Code, einschließlich Komponententests hinzugefügt, um sicherzustellen, dass es jetzt wie erwartet funktioniert, ist here, mit Benutzernamen und Passwort als 'Gast', ohne die Anführungszeichen einloggen.

---

So:

: Finden Sie zuerst

Func<TreeNode, String, TreeNode> findNode = null; // satisfy recursion re-use 
findNode = (n, value) => 
{ 
    if (n == null) return n; 
    if (n.Value == value) return n; 
    foreach (var subNode in n.Nodes) 
    { 
     TreeNode foundNode = findNode(subNode, value); 
     if (foundNode != null) return foundNode; 
    } 
    return null; 
}; 

Beachten Sie, dass die hier Falle ist, dass für eine Lambda oder Delegierter rekursiv zu sein, müssen Sie die Variable deklarieren Zuerst mit einem bekannten Wert, bevor Sie ihm den tatsächlichen Delegierten zuweisen. Andernfalls wird der Compiler beschweren, dass Sie eine Variable verwenden, bevor Sie einen Wert erhalten haben.

: Hier finden Sie alle

Func<TreeNode, String, List<TreeNode>> findNodes = null; 
findNodes = (n, value) => 
{ 
    var result = new List<TreeNode>(); 
    if (n == null) return result; 
    if (n.Value == value) result.Add(n); 
    foreach (var subNode in n.Nodes) 
    { 
     result.AddRange(findNodes(subNode, value)); 
    } 
    return result; 
}; 

Der Trick hier ist nur die Knoten auf jeder Ebene zu sammeln und aggregieren nach oben.

Answer 2

Wie wäre es damit ..

public class Node<T> where T:IComparable 
{ 
    public T Value { get; set; } 

    public IList<Node<T>> Children { get; set; } 

    public override string ToString() 
    { 
     return Value.ToString(); 
    } 

    public static Func<T, Node<T>, Node<T>> GetFindFirstFunc() 
    { 
     Func<T, Node<T>,Node<T>> func = null; 
     func = (value,currentNode) => 
      { 
       if (currentNode.Value.CompareTo(value) == 0) 
       { 
        return currentNode; 
       } 
       if (currentNode.Children != null) 
       { 
        foreach (var child in currentNode.Children) 
        {        
         var result = func(value, child); 
         if (result != null) 
         { 
          //found the first match, pass that out as the return value as the call stack unwinds 
          return result; 
         } 
        } 
       } 
       return null; 
      }; 
     return func; 
    } 

    public static Func<T, Node<T>, IEnumerable<Node<T>>> GetFindAllFunc() 
    { 
     Func<T, Node<T>, IEnumerable<Node<T>>> func = null; 
     List<Node<T>> matches = new List<Node<T>>(); 
     func = (value, currentNode) => 
     { 
      //capture the matches List<Node<T>> in a closure so that we don't re-create it recursively every time. 
      if (currentNode.Value.CompareTo(value) == 0) 
      { 
       matches.Add(currentNode); 
      } 
      if (currentNode.Children != null) 
      { 
       //process all nodes 
       foreach (var child in currentNode.Children) 
       { 
        func(value, child); 
       } 
      } 
      return matches; 
     }; 
     return func; 
    }  
} 

Hier wird die Telefonvorwahl ist:

static void Main(string[] args) 
    { 
     Node<int> rootNode = new Node<int> 
     { 
      Value = 1, 
      Children = new List<Node<int>> 
      { 
       new Node<int> 
       { Value = 2, 
           Children = new List<Node<int>> 
           { 
            new Node<int>{ Value = 7}, 
            new Node<int>{ Value = 4}                
           } 
       }, 
       new Node<int> 
       { Value = 5, 
           Children = new List<Node<int>> 
           { 
            new Node<int>{ Value = 6}, 
            new Node<int>{ Value = 7}                
           } 
       } 
      } 
     }; 


     Func<int, Node<int>, Node<int>> findFirst = Node<int>.GetFindFirstFunc(); 
     var firstValue = findFirst(7, rootNode);   



     Func<int, Node<int>, IEnumerable<Node<int>>> findAll = Node<int>.GetFindAllFunc(); 
     var allvalues = findAll(7, rootNode);   
    }