Функционально обхода дерева в C#

Question

Рассмотрим следующий метод расширения в C#, траверс:

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

Этот метод позволяет рекурсию через дерево, как это определено Т и независимо от функции вызывает Т вернуть его подузлов.

Теперь рассмотрим следующую реализацию Т:

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

Моя цель состоит в том, чтобы написать самую короткую функцию, возможно, что будет возвращать IEnumerable , содержащий полные пути для каждого узла в этом дереве. Что-то вроде:

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

Очевидно, что добавление родительского свойства к узлу делает проблему тривиальной. Вместо этого я хотел бы как-то построить мои родительские строки внутри функтора. Я не думаю, что это было бы слишком сложно в C++, но я не вижу, как это сделать на C#. Есть идеи?

Answer 1

Я думаю, что трюк состоит в том, чтобы просто не пропустить тип Node. Вместо этого пройдите вниз Node и это квалифицированный путь. Например

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

Ну я не думаю, что вы можете избежать поиска по дереву, пока не найдете узел, который вы ищете, не сохраняя родительский указатель.

Вы начнете с корня. Проверьте текущий узел на соответствие. Если это совпадение, верните узел или просто имя (в виде списка этого одного элемента). В противном случае, если это листовой узел, верните нуль. Если лист не пересекает его, и если дети возвращают ненулевое значение, добавьте текущий узел в свой список и верните его.

Возврат с оригинального вызова, null означает, что совпадения не найдено. В противном случае у вас будет список узлов по порядку.

Answer 3

ярчайших и наиболее многоразовые решение:

Создать универсальный метод, который перечисляет все возможные пути:

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

Полученное перечисление может быть легко преобразован в вашей строковое представление.

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