1

問題

親が子の前に常にリストされるように、ノードのフラットな順序付けされていないセットを順序付けるための最速の方法は何ですか。私の現在のソリューションでは、キューを使用して幅優先の方法でツリーを反復処理しています。しかし、私はもっと良い/より効率的な方法があるかどうか疑問に思っていました。

ノート：

  • 値を事前に計算できません
  • IdとParentIdもGuidである可能性があります（intがシーケンシャルIDを保証できない場合でも）

Linqパッドコード

void Main()
{
    var nodes = new Node[] {
        new Node { Id = 7, ParentId = 3 },
        new Node { Id = 4, ParentId = 2 },
        new Node { Id = 1, ParentId = 0 },
        new Node { Id = 2, ParentId = 1 },
        new Node { Id = 3, ParentId = 1 },

        new Node { Id = 5, ParentId = 2 },
        new Node { Id = 6, ParentId = 3 },
        new Node { Id = 8, ParentId = 0 },
    };

    SortHierarchy(nodes).Dump();
}

IEnumerable<Node> SortHierarchy(IEnumerable<Node> list)
{
    // hashtable lookup that allows us to grab references to the parent containers, based on id
    var lookup = new Dictionary<int, List<Node>>();

    Queue<Node> nodeSet = new Queue<Node>();
    List<Node> children;

    foreach (Node item in list) {
        if (item.ParentId == 0) { // has no parent
            nodeSet.Enqueue(item); // This will add all root nodes in the forest
        } else {
            if (lookup.TryGetValue(item.ParentId, out children)) {
                // add to the parent's child list
                children.Add(item);
            } else {
                // no parent added yet
                lookup.Add(item.ParentId, new List<Node> { item });
            }
        }
    }

    while (nodeSet.Any()) {
        var node = nodeSet.Dequeue();
        if (lookup.TryGetValue(node.Id, out children)) {
            foreach (var child in children) {
                nodeSet.Enqueue(child);
            }
        }
        yield return node;
    }
}

private class Node {
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
}

リサーチ

私はこれを見つけましたが、それは私が求めていたものではありませんでした（コードも機能しません）

親/子のフラットリストから階層オブジェクトを構築する

4

1 に答える 1

-1

このコードは、同じ dump() の結果を返します。リストを最初に parentid で並べ替えます。

IEnumerable<Node> SortHierarchy2(IEnumerable<Node> list)
{
    return list.OrderBy(l => l.ParentId);
}

これは、子供の ID が親の ID よりも小さい限り機能します。

于 2013-01-30T09:08:34.440 に答える