1

问题

订购一组平坦无序节点的最快方法是什么，以便始终在其子级之前列出父级。我当前的解决方案使用队列以广度优先方式迭代树。但是我一直想知道是否有更好/更有效的方法。

笔记：

  • 我无法预先计算任何值
  • Id 和 ParentId 也可以是 Guid（即使整数我不能保证顺序 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 回答