recherche d'arbres récursifs non binaires, non triés en utilisant C# lambas

Question

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


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

1) Comment voulez-vous écrire l'expression lambda récursive pour revenir TreeNode avec une valeur particulière (ou null si elle est introuvable) en supposant que les valeurs sont uniques? Bien sûr, # 1 peut être répondu en utilisant # 2, mais j'imagine qu'il pourrait y avoir un moyen plus efficace si vous savez qu'il n'y a pas de doublons.

2) En supposant que les valeurs ne sont pas uniques et retournent maintenant une liste de correspondances à la place?

Answer 1

Modifier: J'ai corrigé le code, j'ai effectivement compilé et testé les deux parties du code, mais j'ai dû coller dans les versions avant de les corriger dans VS. Désolé pour ça.

J'ai ajouté un dépôt Subversion avec le code, y compris les tests unitaires, pour m'assurer qu'il fonctionne maintenant comme prévu, est here, connectez-vous avec le nom d'utilisateur et mot de passe à la fois comme «invité», sans les guillemets.

---

Comme ceci:

: Trouvez d'abord

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

Notez que le piège est que pour un lambda ou un délégué récursive, vous devez déclarer la variable d'abord, avec une valeur connue, avant de lui affecter le délégué réel. Sinon, le compilateur se plaindra que vous utilisez une variable avant d'avoir reçu une valeur.

: Trouver tous

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

L'astuce ici est juste rassembler les noeuds sur chaque niveau, et regrouper vers le haut.

Answer 2

Que diriez-vous ce ..

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

Voici le code d'appel:

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