用循环替换递归

本文关键字：递归 替换 循环 | 更新日期: 2023-09-27 17:59:52

我正在开发一个ASP。网页中，有一个树视图。在树视图中，一些节点有像分支一样的嵌套节点。我有以下格式的自定义对象列表中的数据：

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的节点，其性能较慢。请建议用循环替换此递归调用的算法。

用循环替换递归

当它沿着树递归时，代码正在对子节点列表进行线性搜索。

这意味着，对于随机分布的父ID，在向树中添加N个节点后，在添加第N+1个节点之前，它将平均搜索N/2个节点以查找父ID。因此，成本将是节点数量的O（N²）。

不是线性扫描，而是创建一个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之前，您需要将树的根添加到索引中。

广度优先搜索的迭代版本应该如下所示：

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内存。（与DFS或迭代深化DFS相比，内存使用是O（n），而不是O（logn）。）

您可以使用为xml从sql server数据库返回xml格式的数据然后将其绑定到树视图控件。

相关文章：