如何从平面结构有效地建造树木？

Question

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

您将如何处理这些对象以创建生成的树？

我不是一个解决方案,但我确信它远非最佳...

我需要创建这些树,然后按正确的顺序将数据插入数据库.

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

Answer 1

将对象的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);
}

Answer 2

根据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;
}

Answer 3

这是一个简单的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);

Answer 4

Python解决方案

def subtree(node, relationships):
    return {
        v: subtree(v, relationships) 
        for v in [x[0] for x in relationships if x[1] == node]
    }

例如:

# (child, parent) pairs where -1 means no parent    
flat_tree = [
     (1, -1),
     (4, 1),
     (10, 4),
     (11, 4),
     (16, 11),
     (17, 11),
     (24, 17),
     (25, 17),
     (5, 1),
     (8, 5),
     (9, 5),
     (7, 9),
     (12, 9),
     (22, 12),
     (23, 12),
     (2, 23),
     (26, 23),
     (27, 23),
     (20, 9),
     (21, 9)
    ]

subtree(-1, flat_tree)

生产:

{
    "1": {
        "4": {
            "10": {}, 
            "11": {
                "16": {}, 
                "17": {
                    "24": {}, 
                    "25": {}
                }
            }
        }, 
        "5": {
            "8": {}, 
            "9": {
                "20": {}, 
                "12": {
                    "22": {}, 
                    "23": {
                        "2": {}, 
                        "27": {}, 
                        "26": {}
                    }
                }, 
                "21": {}, 
                "7": {}
            }
        }
    }
}

Answer 5

JS版本返回一个根或一个根数组,每个根将包含一个包含相关子节点的Children数组属性.不依赖于有序输入,体面紧凑,不使用递归.请享用!

// creates a tree from a flat set of hierarchically related data
var MiracleGrow = function(treeData, key, parentKey)
{
    var keys = [];
    treeData.map(function(x){
        x.Children = [];
        keys.push(x[key]);
    });
    var roots = treeData.filter(function(x){return keys.indexOf(x[parentKey])==-1});
    var nodes = [];
    roots.map(function(x){nodes.push(x)});
    while(nodes.length > 0)
    {

        var node = nodes.pop();
        var children =  treeData.filter(function(x){return x[parentKey] == node[key]});
        children.map(function(x){
            node.Children.push(x);
            nodes.push(x)
        });
    }
    if (roots.length==1) return roots[0];
    return roots;
}


// demo/test data
var treeData = [

    {id:9, name:'Led Zep', parent:null},
    {id:10, name:'Jimmy', parent:9},
    {id:11, name:'Robert', parent:9},
    {id:12, name:'John', parent:9},

    {id:8, name:'Elec Gtr Strings', parent:5},
    {id:1, name:'Rush', parent:null},
    {id:2, name:'Alex', parent:1},
    {id:3, name:'Geddy', parent:1},
    {id:4, name:'Neil', parent:1},
    {id:5, name:'Gibson Les Paul', parent:2},
    {id:6, name:'Pearl Kit', parent:4},
    {id:7, name:'Rickenbacker', parent:3},

    {id:100, name:'Santa', parent:99},
    {id:101, name:'Elf', parent:100},

];
var root = MiracleGrow(treeData, "id", "parent")
console.log(root)

Answer 6

对于对 Eugene 解决方案的 C# 版本感兴趣的任何人，请注意node_list是作为映射访问的，因此请改用字典。

请记住，此解决方案仅在表按parent_id排序时才有效。

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

var root = new Node { id = 0 };
var node_list = new Dictionary<int, Node>{
    { 0, root }
};

foreach (var item in table)
{
    node_list.Add(item.id, item);
    node_list[item.parent_id].children.Add(node_list[item.id]);
}

节点定义如下。

class Node
{
    public int id { get; set; }
    public int parent_id { get; set; }
    public List<Node> children = new List<Node>();
}

Answer 7

在这里找到了一个很棒的 JavaScript 版本：http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

\n\n

让\xe2\x80\x99s 假设你有一个像这样的数组：

\n\n

const models = [\n    {id: 1, title: \'hello\', parent: 0},\n    {id: 2, title: \'hello\', parent: 0},\n    {id: 3, title: \'hello\', parent: 1},\n    {id: 4, title: \'hello\', parent: 3},\n    {id: 5, title: \'hello\', parent: 4},\n    {id: 6, title: \'hello\', parent: 4},\n    {id: 7, title: \'hello\', parent: 3},\n    {id: 8, title: \'hello\', parent: 2}\n];\n

\n\n

并且您希望像这样嵌套对象：

\n\n

const nestedStructure = [\n    {\n        id: 1, title: \'hello\', parent: 0, children: [\n            {\n                id: 3, title: \'hello\', parent: 1, children: [\n                    {\n                        id: 4, title: \'hello\', parent: 3, children: [\n                            {id: 5, title: \'hello\', parent: 4},\n                            {id: 6, title: \'hello\', parent: 4}\n                        ]\n                    },\n                    {id: 7, title: \'hello\', parent: 3}\n                ]\n            }\n        ]\n    },\n    {\n        id: 2, title: \'hello\', parent: 0, children: [\n            {id: 8, title: \'hello\', parent: 2}\n        ]\n    }\n];\n

\n\n

这里\xe2\x80\x99是一个实现它的递归函数。

\n\n

function getNestedChildren(models, parentId) {\n    const nestedTreeStructure = [];\n    const length = models.length;\n\n    for (let i = 0; i < length; i++) { // for-loop for perf reasons, huge difference in ie11\n        const model = models[i];\n\n        if (model.parent == parentId) {\n            const children = getNestedChildren(models, model.id);\n\n            if (children.length > 0) {\n                model.children = children;\n            }\n\n            nestedTreeStructure.push(model);\n        }\n    }\n\n    return nestedTreeStructure;\n}\n

\n\n

用法：

\n\n

const models = [\n    {id: 1, title: \'hello\', parent: 0},\n    {id: 2, title: \'hello\', parent: 0},\n    {id: 3, title: \'hello\', parent: 1},\n    {id: 4, title: \'hello\', parent: 3},\n    {id: 5, title: \'hello\', parent: 4},\n    {id: 6, title: \'hello\', parent: 4},\n    {id: 7, title: \'hello\', parent: 3},\n    {id: 8, title: \'hello\', parent: 2}\n];\nconst nestedStructure = getNestedChildren(models, 0);\n

\n

Answer 8

我将Mehrdad Afshari 的 C# 答案转换为 Java：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Tree {

    Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
        Map<Integer, Node> lookup = new HashMap<>();
        actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
        //foreach (var item in lookup.Values)
        lookup.values().forEach(item ->
                {
                    Node proposedParent;
                    if (lookup.containsKey(item.associatedObject.parentId)) {
                        proposedParent = lookup.get(item.associatedObject.parentId);
                        item.parent = proposedParent;
                        proposedParent.children.add(item);
                    }
                }
        );
        //return lookup.values.Where(x =>x.Parent ==null);
        return lookup.values().stream().filter(x -> x.parent == null).iterator();
    }

}

class MyObject { // The actual object
    public int parentId;
    public int id;
}

class Node {
    public List<Node> children = new ArrayList<Node>();
    public Node parent;
    public MyObject associatedObject;

    public Node(MyObject associatedObject) {
        this.associatedObject = associatedObject;
    }
}