如何从平面结构高效地构建树？

我有一堆扁平结构的物体。 这些对象有一个ID和一个ParentID属性，因此它们可以排列在树中。 他们没有特定的顺序。 每个ParentID属性不一定与结构中的ID匹配。 因此他们可能是从这些物体出现的几棵树。

你将如何处理这些对象来创建结果树？

我离解决方案还有很远的距离，但我相信它远没有达到最佳效果......

我需要创建这些树，然后按正确的顺序将数据插入到数据库中。

没有循环引用。 当ParentID == null或在其他对象中找不到ParentID时，Node是RootNode

---

将对象的ID存储在映射到特定对象的散列表中。 枚举所有对象并查找它们的父对象，并相应地更新其父指针。

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

---

基于Mehrdad Afshari的回答和Andrew Hanlon对加速的评论，这里是我的看法。

与原始任务的重要区别：根节点具有ID​​ == parentID。

class MyObject
{   // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject Source { get; set; }
}

List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    var lookup = new Dictionary<int, Node>();
    var rootNodes = new List<Node>();

    foreach (var item in actualObjects)
    {
        // add us to lookup
        Node ourNode;
        if (lookup.TryGetValue(item.ID, out ourNode))
        {   // was already found as a parent - register the actual object
            ourNode.Source = item;
        }
        else
        {
            ourNode = new Node() { Source = item };
            lookup.Add(item.ID, ourNode);
        }

        // hook into parent
        if (item.ParentID == item.ID)
        {   // is a root node
            rootNodes.Add(ourNode);
        }
        else
        {   // is a child row - so we have a parent
            Node parentNode;
            if (!lookup.TryGetValue(item.ParentID, out parentNode))
            {   // unknown parent, construct preliminary parent
                parentNode = new Node();
                lookup.Add(item.ParentID, parentNode);
            }
            parentNode.Children.Add(ourNode);
            ourNode.Parent = parentNode;
        }
    }

    return rootNodes;
}

---

下面是一个简单的JavaScript算法，用于将平坦表分析为运行时间为N的父/子树结构：

var table = [
    {parent_id: 0, id: 1, children: []},
    {parent_id: 0, id: 2, children: []},
    {parent_id: 0, id: 3, children: []},
    {parent_id: 1, id: 4, children: []},
    {parent_id: 1, id: 5, children: []},
    {parent_id: 1, id: 6, children: []},
    {parent_id: 2, id: 7, children: []},
    {parent_id: 7, id: 8, children: []},
    {parent_id: 8, id: 9, children: []},
    {parent_id: 3, id: 10, children: []}
];

var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};

for (var i = 0; i < table.length; i++) {
    node_list[table[i].id] = table[i];
    node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}

console.log(root);

链接地址: http://www.djcxy.com/p/30459.html

上一篇: How to efficiently build a tree from a flat structure?

下一篇: MySQL "WITH" clause