采取像這樣的嵌套遞歸 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 的子級開始）然后回到根目錄。我該如何有效地解決這個問題？
1 回答
HUX布斯
TA貢獻1876條經驗 獲得超6個贊
從您的問題中不清楚您是想要后序（深度優先）遍歷還是反向級別遍歷（廣度優先，反向）。假設你想要后序，算法很簡單：
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) 堆?？臻g，其中 dmax 是最大深度，我們可以破壞調用堆棧。
因此：如果您有數百或數千個級別，請使用顯式堆棧技術。
練習：重寫我的算法以使用顯式堆棧而不是將調用堆棧用作隱式堆棧。
但是你說你需要任何深度的樹。如果樹中有數十億或數萬億個節點，深度為數十億或數萬億，該怎么辦？在這種情況下，您需要使用外部存儲器解決方案，我建議構建一個專用于解決此問題的自定義存儲系統；對大規模圖形數據庫進行一些研究，可以解決此類問題。
不管怎樣，既然你有了通用的解決方案，你的具體解決方案就很簡單了：
var ids = root.Foos
.Postorder(f => f.Foos)
.Select(f => f.FooId)
.ToList();
管他呢。
- 1 回答
- 0 關注
- 156 瀏覽
添加回答
舉報
0/150
提交
取消