1

ASP.Netページで作業していますが、ツリービューがあります。ツリービューでは、一部のノードにブランチなどのネストされたノードがあります。次の形式のカスタムオブジェクトのリストにデータがあります。

Id、Description、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を超えるノードでは、パフォーマンスが低下します。この再帰呼び出しをループに置き換えるアルゴリズムを提案してください。

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であるため、メモリ付きで最適ではありません。（メモリ使用量はO（n）であり、 DFSまたは反復深化DFSと比較してO（log n ）ではありません。）

于 2013-02-16T12:56:32.193 に答える
-1

for xmlを使用してSQLサーバーデータベースからxml形式でデータを返し、 それをツリービューコントロールにバインドできます。

于 2013-02-16T13:01:49.693 に答える