从下到上遍历任意深度的嵌套层次结构

Question

采取像这样的嵌套递归 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 的子级开始）然后回到根目录。我该如何有效地解决这个问题？

Answer 1

从您的问题中不清楚您是想要后序（深度优先）遍历还是反向级别遍历（广度优先，反向）。假设你想要后序，算法很简单：

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

管他呢。