如何从一个平坦的结构有效地build立一棵树？
我有一堆扁平结构的物体。 这些对象有一个ID和一个ParentID属性，所以他们可以安排在树上。 他们没有特定的顺序。 每个ParentID属性不一定与结构中的ID匹配。 因此，他们可能是从这些物体出现的几棵树。
你将如何处理这些对象来创build结果树？
我离解决scheme还有很远的距离，但我确信它远远不是最理想的。
我需要创build这些树，然后按正确的顺序将数据插入到数据库中。
没有循环引用。 当ParentID == null或在其他对象中找不到ParentID时，Node是RootNode
将对象的ID存储在映射到特定对象的散列表中。 枚举所有的对象，并find它们的父母，如果它存在并相应地更新其父指针。
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); }
下面是一个简单的JavaScriptalgorithm，用于将平坦表分析为运行时间为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);
根据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; }
JS版本，返回一个根或一个根数组，其中每个根将有一个儿童数组属性包含相关的孩子。 不依赖于有序的input，体积小巧，不使用recursion。 请享用！
// 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)
Python解决scheme
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": {} } } } }
模糊的问题在我看来，我可能会创build一个从ID到实际对象的地图。 在伪java（我没有检查它是否工作/编译），它可能是这样的：
Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>(); for (FlatObject object: flatStructure) { flatObjectMap.put(object.ID, object); }
并查找每个家长：
private FlatObject getParent(FlatObject object) { getRealObject(object.ParentID); } private FlatObject getRealObject(ID objectID) { flatObjectMap.get(objectID); }
通过重用getRealObject(ID)并从对象到对象集合（或它们的ID）进行映射，您也可以获得父 – >子映射。
我在@Mehrdad Afshari基础上松散地在C＃中编写了一个通用的解决scheme：
void Example(List<MyObject> actualObjects) { List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1); } public class TreeNode<T> { public TreeNode(T value) { Value = value; Children = new List<TreeNode<T>>(); } public T Value { get; private set; } public List<TreeNode<T>> Children { get; private set; } } public static class TreeExtensions { public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey)) { var roots = new List<TreeNode<TValue>>(); var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(overrideValue)).ToArray(); var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value)); foreach (var currentNode in allNodes) { TKey parentKey = parentKeySelector(currentNode.Value); if (Equals(parentKey, defaultKey)) { roots.Add(currentNode); } else { nodesByRowId[parentKey].Children.Add(currentNode); } } return roots; } }
你坚持只使用这些属性？ 如果没有，那么创build一个子节点数组可能是很好的，在这里你可以遍历所有这些对象来构build这样的属性。 从那里，select有孩子但没有父母的节点，从上到下迭代地构build你的树。
我可以用4行代码和O（n log n）时间来做到这一点，假设Dictionary是类似于TreeMap的东西。
dict := Dictionary new. ary do: [:each | dict at: each id put: each]. ary do: [:each | (dict at: each parent) addChild: each]. root := dict at: nil.
编辑 ：好吧，现在我读了一些parentIDs是假的，所以忘了上面，做到这一点：
dict := Dictionary new. dict at: nil put: OrderedCollection new. ary do: [:each | dict at: each id put: each]. ary do: [:each | (dict at: each parent ifAbsent: [dict at: nil]) add: each]. roots := dict at: nil.
大部分的答案都假定你正在寻找数据库以外的地方。 如果你的树本质上是相对静态的，你只需要将树映射到数据库中，你可能要考虑在数据库端使用嵌套集表示。 查看Joe Celko的书籍（或者Celg概述）。
如果绑定到Oracle dbs，请查看它们的CONNECT BY以获得直接的SQL方法。
无论采用哪种方法，在将数据加载到数据库之前，都可以完全跳过映射树。 只是以为我会提出这个替代scheme，这可能是完全不适合你的具体需求。 原始问题的整个“正确的顺序”部分在某种程度上意味着你需要命令在数据库中是“正确的”？ 这可能会推动我在那里处理树木。
这与提问者所寻找的并不完全一样，但我很难把这个答案放在这里提供的含糊不清的答案上，我仍然认为这个答案符合标题。
我的答案是将平面结构映射到直接对象树，其中所有对象都是每个对象上的ParentID 。 ParentID为null或0如果它是根。 与提问者相反，我假定所有有效的ParentID指向列表中的其他东西：
var rootNodes = new List<DTIntranetMenuItem>(); var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>(); //Convert the flat database items to the DTO's, //that has a list of children instead of a ParentID. foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem> { //Automapper (nuget) DTIntranetMenuItem intranetMenuItem = Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem); intranetMenuItem.Children = new List<DTIntranetMenuItem>(); dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem); } foreach (var efIntranetMenuItem in flatIntranetMenuItems) { //Getting the equivalent object of the converted ones DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID]; if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0) { rootNodes.Add(intranetMenuItem); } else { var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value]; parent.Children.Add(intranetMenuItem); //intranetMenuItem.Parent = parent; } } return rootNodes;
下面是Mehrdad Afshari给出的同样的实现，但这一次在java中：
public class Node { private SomeObject someObject; private List<Node> children; private Node parent; public Node(SomeObject so) { super(); this.someObject = so; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public SomeObject getSomeObject() { return someObject; } public void setSomeObject(SomeObject so) { this.someObject = so; } public List<Node> getChildren() { return children; } public void setChildren(List<Node> children) { this.children = children; } public void addChild(Node node) { if (children == null) { children = new ArrayList<Node>(); } children.add(node); }
}
for (SomeObject someObject: list) { lookup.put(someObject.getId(), new Node(someObject)); } Set<Long> keySet = lookup.keySet(); for (Long id : keySet) { Node value = lookup.get(id); long parentId = value.getSomeObject().getParentId(); Node parentNode = lookup.get(parentId); if (parentNode != null) { value.setParent(parentNode); parentNode.addChild(value); } }
