funkcjonalnie przechodzenie drzewa C#

Question

Rozważmy następującą metodę wydłużania w C#, wprost:

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

Ta metoda pozwala na przeszukanie przez drzewo określone przez T a co Funkcja powoduje T do powrotu do jego podwęzły.

Teraz rozważmy następujący realizację T:

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

Moim celem jest, aby napisać najkrótszą możliwą funkcję, która zwróci IEnumerable zawierającym w pełni wykwalifikowanych ścieżki dla każdego węzła w tym drzewie. Coś takiego jak:

Oczywiście dodanie właściwości Parent do węzła sprawia, że ​​problem jest banalny. Zamiast tego chciałbym jakoś zbudować moje struny macierzyste wewnątrz funktora. Nie sądzę, byłoby to zbyt trudne w C++, ale nie widzę, jak to zrobić w języku C#. Jakieś pomysły?

Answer 1

Myślę, że sztuką jest po prostu nie przekazywać typu Node. Zamiast tego przepuść Node i jego kwalifikowaną ścieżkę. Na przykład

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

Cóż, nie sądzę, że można uniknąć przeszukiwania drzewa, aż znajdziesz węzeł szukasz bez zapisywania wskaźnik nadrzędnego.

Zaczniesz od korzenia. Przetestuj bieżący węzeł dla dopasowania. Jeśli jest zgodna, zwróć węzeł lub po prostu nazwę (jako listę tego jednego elementu). W przeciwnym razie, jeśli jest to węzeł liścia, zwróć wartość null. Jeśli nie jest liściem, przechodź przez potomka i jeśli dzieci zwracają wartość inną niż null, dodaj bieżący węzeł do listy i zwróć to.

Po powrocie z pierwotnego połączenia wartość null oznacza brak zgodności. W przeciwnym razie uporządkujesz listę węzłów.

Answer 3

najczystszych i najbardziej wielokrotnego użytku rozwiązanie:

Tworzenie metoda rodzajowa, który wylicza wszystkie możliwe Ścieżki edukacyjne:

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

Powstały wyliczenie można łatwo przekształcić w swojej reprezentacji smyczkowy.

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