1

我正在处理一个 ASP.Net 页面，其中有树视图。在树视图中，一些节点具有嵌套节点，如分支。我在以下格式的自定义对象列表中有数据：

标识、描述、父标识

现在，我正在使用一个函数来递归地将节点添加到树视图中。以下是代码片段：

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 的节点，它的性能很慢。请提出一种算法来用循环替换这个递归调用。

4

3 回答 3

3

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

这意味着对于随机分布的父 ID，在将 N 个节点添加到树之后，它会在添加第 N+1 个节点之前平均搜索 N/2 个节点来寻找父节点。因此，节点数量的成本将为 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。

于 2013-02-16T21:54:51.097 回答
-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 内存。（与 DFS 或迭代深化 DFS 相比，内存使用是O(n)，而不是O(log n) 。）

于 2013-02-16T12:56:32.193 回答
-1

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

于 2013-02-16T13:01:49.693 回答