我可以使用什麼算法在C＃中對這個分支列表進行排序？

我試圖創建一個有序的分類列表類別，所以我可以找到任何子類別並在開始時添加"-";而且這一類可能有任何子類別添加"--"等我可以使用什麼算法在C＃中對這個分支列表進行排序？

我的測試類的屬性看起來是這樣的：

public int Id { get; set; } 
    public int OrderInList { get; set; } 
    public int ParentId { get; set; } 
    public IList<TestCategories> Subcategories { get; set; }

例子：

Books 
-Special Offers 
--Fiction 
-eBooks 
--Pdf 
--Mobi 
Maps 
-United Kingdom 
--Cumbria 
--West Yorkshire

我有一個默認的根級類別與Id: 1，ParentId: 1和OrderInList: 1。
所以上面看起來像順序：

Id | ParentId | OrderInList 
2   1    1  //Books 
3   2    1  //-Special Offers 
4   3    1  //--Fiction 
5   2    2  //-eBooks 
6   5    1  //--Pdf 
7   5    2  //--Mobi 
8   1    2  //Maps 
9   8    1  //-United Kingdom 
10  9    1  //--Cumbria 
11  9    2  //--West Yorkshire

我如何排序完全無序列表看起來像上面？

來源

2012-08-14 Kiada

這不是一個「分支列表」，這是一棵樹。 – delnan 2012-08-14 13:39:30

無法理解您的輸入是什麼以及您要查找的輸出是什麼。你有沒有一個無序的列表你想在樹中轉換？或者你有一棵樹想要在一個排序列表中轉換？ – 2012-08-14 13:51:10

感謝您糾正我的問題，我對術語有些不確定，所以我盡我所能地描述了它！ – Kiada 2012-08-14 14:03:55

這種分類被稱爲Topological Sorting。對拓撲進行排序的最簡單方法是使用深度優先遞歸搜索：您離開節點的順序是逆拓撲。如果您需要知道樹中節點的深度，以便知道要在名稱前面放置多少破折號，則可以將深度優先遞歸方法添加一個int level變量。

您可以借用Rosetta Code的實現 - 它在C＃中沒有一個，但是Java中的一個應該足夠簡單易於翻譯。

來源

2012-08-14 13:42:39 dasblinkenlight

拓撲排序對樹木IMO沒有太大的用處。有更好的算法特定於此。或者我錯了？ – 2012-08-14 13:49:22

@lcfseth樹是圖的特例，因爲OP要求一種排序方式，所以可以稱之爲拓撲排序，儘管我同意當圖形是樹時很少調用它。 – dasblinkenlight 2012-08-14 14:00:14

爲此歡呼！至少我有一些工作，並知道我現在尋找什麼。非常感激。 – Kiada 2012-08-14 14:04:58

我可以使用什麼算法在C＃中對這個分支列表進行排序？

回答

相關問題