我有一堆扁平结构的物体.这些物体具有ID和ParentID属性,因此它们可以排列在树木中.它们没有特别的顺序.每个ParentID属性不一定与ID结构中的a 匹配.因此它们可能是从这些物体中出现的几棵树.
您将如何处理这些对象以创建生成的树？
我不是一个解决方案,但我确信它远非最佳...
我需要创建这些树,然后按正确的顺序将数据插入数据库.
没有循环引用.当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 Children = new List();
public Node Parent { get; set; }
public MyObject AssociatedObject { get; set; }
}
IEnumerable BuildTreeAndGetRoots(List actualObjects)
{
Dictionary lookup = new Dictionary();
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 Children = new List();
public Node Parent { get; set; }
public MyObject Source { get; set; }
}
List BuildTreeAndGetRoots(List actualObjects)
{
var lookup = new Dictionary();
var rootNodes = new List();
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);
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": {}
}
}
}
}
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)
京公网安备 11010802040832号 | 京ICP备19059560号-6 