用循環替換遞歸

我正在ASP.Net頁面上工作，並且裏面有一個樹形視圖。在樹視圖中，一些節點具有像分支一樣的嵌套節點。我有數據在以下格式的自定義對象的列表：用循環替換遞歸

ID，描述，parentId的

現在，我使用的是函數遞歸節點添加到樹視圖。以下是代碼片段：

private bool findParentAddNode(string id, string description, string parentid, ref List<CustomTreeNode> treeList) 
{ 
    bool isFound = false; 
    foreach (CustomTreeNode node in treeList) 
    { 
     if (node.id == parentid)//if current node is parent node, add in it as its child 
     { 
      node.addChild(id, description, parentid); 
      isFound = true; 
      break; 
     } 
     else if (node.listOfChildNodes != null)//have child nodes 
     { 
      isFound = findParentAddNode(id, description, parentid, ref node.listOfChildNodes); 
      if (isFound) 
       break; 
     } 

    } 

    return isFound; 
}

上述技術運行良好，但對於多於30K的節點，其性能很慢。請建議一個算法來用循環替換這個遞歸調用。

來源

2013-02-16 Nadeem Jamali

你確定遞歸是問題嗎？除非你的樹形狀很奇怪，不應該是那麼多層次。 – millimoose 2013-02-16 12:44:29

我相信'for loops'在30K節點上仍然會很慢。如果不使用相同參數調用函數，則遞歸方法很好 – ogzd 2013-02-16 12:44:52

注意：您可能會將數據源列表視爲也包含三列和未排序數據的表。 – 2013-02-16 12:46:47

因爲它遞歸下降樹，代碼是做了子節點的名單線性搜索。

這意味着，對於隨機分佈的親本的id，之後加入N個節點到樹它將平均搜索N/2將所述第N + 1節點之前對父節點。所以節點的數量是O（N 2）。

代替線性掃描，創建ID的索引節點，並用它來快速找到父母。當您創建節點並將其添加到樹中時，也將其添加到Dictionary<int,CustomTreeNode>。如果要將節點添加到父級，請在索引中找到父級並添加它。如果addChild返回它創建的孩子，那麼代碼變爲：

Dictionary<int,CustomTreeNode> index = new Dictionary<int,CustomTreeNode>(); 

private bool findParentAddNode(string id, string description, string parentid) 
{ 
    if (!nodeIndex.TryGetValue (parentid, out parentNode)) 
     return false; 

    index[id] = parentNode.addChild(id, description, parentid); 

    return true; 
}

您需要使用findParentAddNode之前，樹的根添加到索引。

來源

2013-02-16 21:54:51

-1

廣度優先搜索的迭代版本應該是類似以下內容：

var rootNodes = new List<CustomTreeNode> { new CustomTreeNode() }; 

while (rootNodes.Count > 0) { 
    var nextRoots = new List<CustomTreeNode>(); 
    foreach (var node in rootNodes) { 
     // process node here 
     nextRoots.AddRange(node.CustomTreeNode); 
    } 
    rootNodes = nextRoots; 
}

也就是說，這不是測試，因爲它是一個BFS，是不是最佳的W/R/t記憶。（內存使用是O（n）的，不O（log n）的相比，DFS或迭代加深DFS）

來源

2013-02-16 12:56:32 millimoose

它看起來更好，我會測試它。謝謝毫毛。 – 2013-02-16 13:00:18

@NadeemJamali您可能還會考慮做一個迭代DFS而不是BFS，但這在C＃中有點醜陋，因爲您需要修改列表而不是使用'foreach'。（由於頻繁前置，因爲基於數組的'List'，可能需要也可能不需要使用'LinkedList'）。進一步的微觀優化將初始化'nextRoots'，其容量是'rootNodes.Count'的一個因子。根據您的樹的分支因子的估計來調整大小。 – millimoose 2013-02-16 13:03:26

-1

您可以從SQL Server數據庫使用返回XML格式的數據的XML 然後將其綁定到treeview控件。

來源

2013-02-16 13:01:49 user1990587

-1：這實際上並不是OP所做的，他正在摧毀他已有的一些樹木數據。 – millimoose 2013-02-16 13:04:45

綁定數據不是問題，但實際的問題是添加節點（我以格式記錄/對象）將樹視圖及其分支放在正確的位置。 – 2013-02-16 13:10:03

用循環替換遞歸

回答

相關問題