Funzionalmente attraversare un albero in C#

Question

Si consideri il seguente metodo di estensione in C#, Traverse:

IEnumerable<T> Traverse<T>(this IEnumerable<T> source, 
           Func<T, IEnumerable<T>> fnRecurse); 

Questo metodo permette la ricorsione attraverso un albero, come definito da T e qualsiasi funzione causa T per tornare i suoi sottonodi.

Consideriamo ora il seguente implementazione di T:

class Node 
{ 
    public string Name; 
    public List<Node> Children; 
} 

Il mio obiettivo è quello di scrivere la più breve possibile funzione che restituirà un IEnumerable contenente i percorsi completi per ogni nodo in questo albero. Qualcosa di simile:

var node = GetParentNode(); 
return node.Traverse(node => node.Children) 
      .Select(node => GetParentName(node) + ":" + node.Name); 

Ovviamente, l'aggiunta di una proprietà Parent al nodo rende il problema banale. Invece mi piacerebbe costruire le mie stringhe madri all'interno di un functor in qualche modo. Non penso che sarebbe troppo difficile in C++, ma non vedo come farlo in C#. Qualche idea?

Answer 1

Penso che il trucco sia semplicemente non passare un tipo Node. Passa invece allo Node ed è percorso qualificato. Per esempio

var node = GetTheStartNode(); 
var start = new { Path = node.Name; Node = node }; 
var paths = 
    start 
    .Traverse(x => x.Node.Children.Select(
     c => new { .Path = x.Path + ":" c.Name; .Node=c)) 
    .Select(x => x.Path); 

Answer 2

Beh non credo che si può evitare di cercare l'albero fino a trovare il nodo che stai cercando senza memorizzare un puntatore genitore.

Inizierete dalla radice. Testare il nodo corrente per una corrispondenza. Se è una corrispondenza, restituisce il nodo o solo il nome (come elenco di questo elemento). Altrimenti, se questo è un nodo foglia, restituisce null. Se non è una foglia, attraversa i suoi figli e se i figli restituiscono un valore non nullo, antepongono il nodo corrente al tuo elenco e lo restituiscono.

Ritorno dalla chiamata originale, null significa nessuna corrispondenza trovata. Altrimenti avrai la tua lista di nodi in ordine.

Answer 3

più chiara e soluzione riutilizzabile:

Creare un metodo generico che enumera tutti i possibili sentieri:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) { 
    yield return new[] { Root }; 
    foreach (var Child in Children(Root)) 
     foreach (var ChildPath in ComputePaths(Child, Children)) 
      yield return new[] { Root }.Concat(ChildPath);    
} 

L'enumerazione risultante può essere facilmente trasformato nella vostra rappresentazione di stringa.

// All paths 
    var Paths = ComputePaths(Test, x => x.Children); 

    // Compute string representation 
    var StrPaths = from p in Paths select string.Join(":", p.Select(t => t.Name).ToArray()); 

    foreach(var p in StrPaths) 
     Console.WriteLine(p);