Отфильтруйте список иерархии и сохраните путь

В С#, как я могу выполнить поиск в списке иерархии, а также сохранить путь в конце. Например:

Объект

public class Node
{
    public IEnumerable<Node> Children { get; set; }

    public string Id { get; set; }
}

Результат

  • a
    • aa
      • aaa
      • ааб
  • b
    • ba
    • bb
      • bba

Что я хочу

Если я ищу в этом списке слово «aab», я хотел бы показать этот результат клиенту:

  • a
    • aa
      • aab

Одна реализация, которую я нашел для поиска в списке иерархии, взята там https://stackoverflow.com/a/30907231/316759 но проблема в том, что он возвращает только найденные конечные узлы без сохранения иерархической структуры.

public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match) where T : class
{
    Stack<T> stack = new Stack<T>();
    stack.Push(node);

    while (stack.Count > 0)
    {
        T thisNode = stack.Pop();

        if (Match(thisNode))
        {
            return thisNode;
        }

        if (ChildsProperty(thisNode) != null)
        {
            foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse())
            {
                stack.Push(child);
            }
        }
    }

    return null;
}

Что мне нужно, так это найти листовые узлы и сохранить их родителей в корне.


c# hierarchy depth-first-search
person Alexandre Jobin    schedule 24.07.2015    source источник
comment
Что именно не работало с поиском по дереву LINQ? Есть код?   -  person Vlad    schedule 24.07.2015
comment
DFS и keep path — довольно стандартный вопрос на собеседовании. Пока не ясно, с чем у вас проблема и какое решение вы хотите, чтобы кто-то написал для вас (вероятно, одна строка LINQ с SlectMany будет слишком сложной, а рекурсия неинтересной)...   -  person Alexei Levenkov    schedule 24.07.2015
comment
@ Влад, они только находят узлы и сглаживают результат, не сохраняя иерархическую структуру.   -  person Alexandre Jobin    schedule 24.07.2015
comment
@AlexeiLevenkov, я обновил свой вопрос. Я также пытался найти больше о DFS, но я не нашел ни одного примера, который сохранил бы путь к корню.   -  person Alexandre Jobin    schedule 25.07.2015
comment
@AlexandreJobin Я думаю, что ваш код слишком оптимизирован для начальной попытки ... Из базовой рекурсивной DFS гораздо проще получить путь (см. Примерный код в моем посте). В вашем коде вы либо сохраняете пары (родительский, дочерний) в стеке, либо имеете Node.Parent для сбора обратного пути.   -  person Alexei Levenkov    schedule 25.07.2015

Ответы (2)


arrow_upward
0
arrow_downward

Вот краткий пример, который позволит вам пометить нужные узлы, как показано:

public bool NodeOrChildrenMatch(Node n)
{
    if (IsMatch(n))
    {
        Show(n);
        return true;
    }
    else
    {
        if (n.Children.Any(NodeOrChildrenMatch))
        {
            Show(n);
            return true;
        }
        return false;
    }
}
person 31eee384    schedule 24.07.2015

arrow_upward
0
arrow_downward

Приблизительный код - собирать "путь" при рекурсивном спуске и очищать последний элемент при подъеме:

Stack<T> path = new Stack<T>();
public static bool DepthFirstSearch(T node, Stack<T> path, Predicate<T> Match) 
{
    path.Push(node);

    if (Match(node))
        return true;

    foreach (T child in (thisNode.Children)
    {
         if (DepthFirstSearch(child, stack, Match))
              return true;
    }

    stack.Pop();
    return false;
}
person Alexei Levenkov    schedule 24.07.2015