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

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>(&nbsp; this IEnumerable<T> nodes,&nbsp; Func<T, IEnumerable<T>> children){&nbsp; foreach(T node in nodes)&nbsp; {&nbsp; &nbsp; foreach(T descendant in children(node).Postorder(children))&nbsp; &nbsp; &nbsp; yield return descendant;&nbsp; &nbsp; yield return node;&nbsp; }}每个节点仅在其所有后代之后才产生，因此这是后序遍历。如果树很浅，那是相当有效的，但是您说您希望解决“任意深度”树的问题。这种方法只对深度达到几十层的树有效，因为它是 O(nd)，其中 n 是节点总数，d 是平均深度；平均深度取决于分支因子，因此可以低至 1 或高至 n，这使其成为潜在的二次算法。此外，由于它使用 O(dmax) 堆栈空间，其中 dmax 是最大深度，我们可以破坏调用堆栈。因此：如果您有数百或数千个级别，请使用显式堆栈技术。练习：重写我的算法以使用显式堆栈而不是将调用堆栈用作隐式堆栈。但是你说你需要任何深度的树。如果树中有数十亿或数万亿个节点，深度为数十亿或数万亿，该怎么办？在这种情况下，您需要使用外部存储器解决方案，我建议构建一个专用于解决此问题的自定义存储系统；对大规模图形数据库进行一些研究，可以解决此类问题。不管怎样，既然你有了通用的解决方案，你的具体解决方案就很简单了：var ids = root.Foos&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .Postorder(f => f.Foos)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .Select(f => f.FooId)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .ToList();管他呢。