用循环替换递归

Question

我正在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的节点，其性能很慢。请建议一个算法来用循环替换这个递归调用。

Answer 1

因为它递归下降树，代码是做了子节点的名单线性搜索。

这意味着，对于随机分布的亲本的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之前，树的根添加到索引。

Answer 2

广度优先搜索的迭代版本应该是类似以下内容：

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）

Answer 3

您可以从SQL Server数据库使用返回XML格式的数据的XML 然后将其绑定到treeview控件。