Блог

Возьмите вложенный рекурсивный фрагмент JSON, подобный этому, который может продолжаться на любую глубину:

 {
   "Id": null,
   "Foos": [
      {
         "FooId": 1,
         "FooName": "ABC",
         "Foos": [
            {
               "FooId": 2,
               "FooName": "DEF",
               "Foos": null
            },
            {
               "FooId": 3,
               "FooName": "GHI",
               "Foos": [
                  {
                     "FooId": 4,
                     "FooName": "JKL",
                     "Foos": null
                  },
                  {
                     "FooId": 5,
                     "FooName": "MNO",
                     "Foos": [
                        {
                           "FooId": 6,
                           "FooName": "PQR",
                           "Foos": null
                        },
                        {
                           "FooId": 7,
                           "FooName": "STU",
                           "Foos": null
                        }
                     ]
                  }
               ]
            }
         ]
      }
   ]
}
  

Использование JSON.NET Я могу отобразить это в структуру, подобную этой:

 public class Root {
    public string Id { get; set; }
    public List<Foo> Foos { get; set; }
}

public class Foo {
    public int FooId { get; set; }
    public string FooName { get; set; }
    public List<Foo> Foos { get; set; }
}
  

пока все хорошо … но теперь мне нужно работать снизу вверх по иерархии (начиная с дочерних элементов с fooId = 5), а затем возвращаться к корню. Как мне эффективно справиться с этим?

Из вашего вопроса неясно, хотите ли вы обход postorder (сначала в глубину) или обратный обход уровня (сначала в ширину, обратный). Предполагая, что вы хотите postorder, алгоритм прост:

 public static IEnumerable<T> Postorder<T>(
  this IEnumerable<T> nodes,
  Func<T, IEnumerable<T>> children)
{
  foreach(T node in nodes)
  {
    foreach(T descendant in children(node).Postorder(children))
      yield return descendant;
    yield return node;
  }
}
  

Каждый узел выдается только после всех его потомков, так что это обход по порядку.

Это достаточно эффективно, если дерево мелкое, но вы говорите, что хотите решить проблему для дерева «любой глубины». Этот подход будет эффективно работать только для деревьев глубиной до нескольких десятков уровней, потому что это O (nd), где n — общее количество узлов, а d — средняя глубина; средняя глубина зависит от коэффициента ветвления и поэтому может быть как 1, так и n, что делает этот алгоритм потенциально квадратичным.

Более того, поскольку он использует пространство стека O (dmax), где dmax — максимальная глубина, мы можем взорвать стек вызовов.

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

Упражнение: перепишите мой алгоритм, чтобы использовать явный стек, а не использовать стек вызовов в качестве неявного стека.

Но вы сказали, что вам нужны деревья любой глубины. Что, если в дереве миллиарды или триллионы узлов глубиной в миллиарды или триллионы? В этом случае вам нужно будет использовать решение с внешней памятью, и я бы рекомендовал создать пользовательскую систему хранения, предназначенную для этой проблемы; проведите некоторое исследование масштабируемых графических баз данных, которые могут решить такого рода проблемы.

В любом случае, теперь, когда у вас есть общее решение, ваше конкретное решение простое:

 var ids = root.Foos
              .Postorder(f => f.Foos)
              .Select(f => f.FooId)
              .ToList();
  

или что угодно.