采取像這樣的嵌套遞歸 JSON 片段，它可以繼續(xù)到任何深度：{ "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 我可以將其映射到這樣的結(jié)構(gòu)中：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; }}到目前為止一切順利......但現(xiàn)在我需要從層次結(jié)構(gòu)的底部向上工作（從 FooId = 5 的子級開始）然后回到根目錄。我該如何有效地解決這個問題？
1 回答
HUX布斯
TA貢獻(xiàn)1876條經(jīng)驗 獲得超6個贊
從您的問題中不清楚您是想要后序（深度優(yōu)先）遍歷還是反向級別遍歷（廣度優(yōu)先，反向）。假設(shè)你想要后序，算法很簡單：
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;
}
}
每個節(jié)點僅在其所有后代之后才產(chǎn)生，因此這是后序遍歷。
如果樹很淺，那是相當(dāng)有效的，但是您說您希望解決“任意深度”樹的問題。這種方法只對深度達(dá)到幾十層的樹有效，因為它是 O(nd)，其中 n 是節(jié)點總數(shù)，d 是平均深度；平均深度取決于分支因子，因此可以低至 1 或高至 n，這使其成為潛在的二次算法。
此外，由于它使用 O(dmax) 堆棧空間，其中 dmax 是最大深度，我們可以破壞調(diào)用堆棧。
因此：如果您有數(shù)百或數(shù)千個級別，請使用顯式堆棧技術(shù)。
練習(xí)：重寫我的算法以使用顯式堆棧而不是將調(diào)用堆棧用作隱式堆棧。
但是你說你需要任何深度的樹。如果樹中有數(shù)十億或數(shù)萬億個節(jié)點，深度為數(shù)十億或數(shù)萬億，該怎么辦？在這種情況下，您需要使用外部存儲器解決方案，我建議構(gòu)建一個專用于解決此問題的自定義存儲系統(tǒng)；對大規(guī)模圖形數(shù)據(jù)庫進(jìn)行一些研究，可以解決此類問題。
不管怎樣，既然你有了通用的解決方案，你的具體解決方案就很簡單了：
var ids = root.Foos
.Postorder(f => f.Foos)
.Select(f => f.FooId)
.ToList();
管他呢。
- 1 回答
- 0 關(guān)注
- 153 瀏覽
添加回答
舉報
0/150
提交
取消