創建一個算法時，對無限兒童層次結構的頁面進行排序時的建議

Question

當需要解決排序算法時，我需要一些建議。這個特定的算法將會輸入一個包含n個項目的列表。每個項目都有一個ID和一個父母ID。就像這樣：

[ 
    {id : 1, parent_id : 0}, 
    {id : 2, parent_id : 1}, 
    {id : 3, parent_id : 1}, 
    {id : 4, parent_id : 2}, 
    {id : 5, parent_id : 4}, 
    {id : 6, parent_id : 0} 
] 

這裏是預期的結果：

[ 
    {id : 1, parent_id : 0, children: 
    [ 
     {id : 2, parent_id : 1, children: 
     [ 
      {id : 4, parent_id : 2, children: 
      [ 
       {id : 5, parent_id : 4} 
      ]} 
     ] 
     }, 
     {id : 3, parent_id : 1}    
    ]}, 
    {id : 6, parent_id : 0} 
] 

我最初的想法是將算法拆分成遞歸解析每個層次結構的水平。所以，它看起來在理論上是這樣的：

• 比較與所有項目的無序列表中的每個項目，看看是否有任何比賽，把每場比賽中的一個子節點的每個家長，把每個家長在排序列表變量。
• 比較子節點中的每個項目與未排序列表中的所有項目以查看它們是否匹配，將每個子節點中的匹配放入其自己的子節點中。
• 繼續上一步，直到每個級別都沒有任何匹配。

我剛剛開始尋找一些函數式編程範例，並開始閱讀關於算法和分析的更多內容，僅僅是因爲我不熟悉遞歸思維。

所以我的問題是：

• 用一種邏輯打交道時你有什麼建議嗎？
• 我該如何學會以正確的方式思考？
• 通過查看我目前的算法，我覺得我已經理解了這個概念，除非我真的不知道如何將第二次檢查工作作爲遞歸解決方案。我遠離正確的方向嗎？

到目前爲止，我已經創建了一個算法，將能夠2級的層次結構。它看起來是這樣的（目前用PHP編寫的，是的概念代碼恰恰證明）：

Answer 1

你會通常與某種字典數據結構的做到這一點。基本上，你有這樣的結構：

Node 
{ 
    int id; 
    int parent; 
    Node[] children; 
} 

你把它保存在一個字典或由ID鍵控的關聯數組。創建一個ID值爲0，父ID爲-1的節點。

通過父ID對輸入數組進行排序，然後遍歷列表。對於每個項目，將其添加到字典中。還要查找它的父節點（由於輸入列表已按照父節點ID排序，因此它已經在字典中），並將新節點添加到父節點的子節點列表中。

完成後，節點[0]包含構造的層次結構。

我沒有太大的PHP程序員的，所以你必須用僞做：

Nodes = new associative array 
Nodes[0] = new Node(0, -1) 
sortedInput = sort input by parent id 
foreach item in sortedInput 
    Nodes[item.id] = new Node(item.id, item.parent); 
    //Nodes[item.parent].Children.Add(Node); 
    // Above line commented and replaced with this. 
    Nodes[item.parent].Children.Add(Nodes[item.id]); 
end 

// Nodes[0] contains the hierarchy 
OutputNode(Nodes[0], "") 

輸出功能的層次結構是遞歸的：

OutputNode(Node, indent) 
    print indent, Node.id, Node.parent 
    foreach (child in Node.children) 
     OutputNode(child, indent+" "); 
    end 
end 

Answer 2

沒有需要遞歸。只是簡單的循環遍歷對象。對於每個對象，如果其parent_id爲0，則將其複製到答案數組中。否則通過它在數組中的位置來訪問父對象，並將當前對象附加到它的子對象列表中。

這是如何解決你的陣列。請仔細注意更新對象一次更新該對象的所有副本這一事實的結果。

0: Start 
    answer = [] 
    objects = [ 
     {id : 1, parent_id : 0}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1}, 
     {id : 4, parent_id : 2}, 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

1: Append object 1 to answer 
    answer = [ 
     {id : 1, parent_id : 0} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1}, 
     {id : 4, parent_id : 2}, 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

2: Append object 2 to children of object 1 
    answer = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1} 
     ]} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1} 
     ]}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1}, 
     {id : 4, parent_id : 2}, 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

3: Append object 3 to children of object 1 
    answer = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1} 
     ]} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1} 
     ]}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1}, 
     {id : 4, parent_id : 2}, 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

4: Append object 4 to children of object 2 
    answer = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3} 
      ]} 
     ]} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3} 
      ]} 
     ]}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1, children : [ 
      {id : 4, parent_id : 3} 
     ]}, 
     {id : 4, parent_id : 2}, 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

5: Append object 5 to children of object 4 
    answer = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3, children : [ 
        {id : 5, parent_id : 4} 
       ]} 
      ]} 
     ]} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3, children : [ 
        {id : 5, parent_id : 4} 
       ]} 
      ]} 
     ]}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1, children : [ 
      {id : 4, parent_id : 3, children : [ 
       {id : 5, parent_id : 4} 
      ]} 
     ]}, 
     {id : 4, parent_id : 3, children : [ 
      {id : 5, parent_id : 4} 
     ]} 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ] 

6: Append object 6 to answer 
    answer = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3, children : [ 
        {id : 5, parent_id : 4} 
       ]} 
      ]} 
     ]}, 
     {id : 6, parent_id : 0} 
    ] 
    objects = [ 
     {id : 1, parent_id : 0, children : [ 
      {id : 2, parent_id : 1}, 
      {id : 3, parent_id : 1, children : [ 
       {id : 4, parent_id : 3, children : [ 
        {id : 5, parent_id : 4} 
       ]} 
      ]} 
     ]}, 
     {id : 2, parent_id : 1}, 
     {id : 3, parent_id : 1, children : [ 
      {id : 4, parent_id : 3, children : [ 
       {id : 5, parent_id : 4} 
      ]} 
     ]}, 
     {id : 4, parent_id : 3, children : [ 
      {id : 5, parent_id : 4} 
     ]} 
     {id : 5, parent_id : 4}, 
     {id : 6, parent_id : 0} 
    ]