Mar*_*ope 16 javascript algorithm
任何人都可以帮助转换以下父子对象列表:
[
{
"name":"root",
"_id":"root_id",
},
{
"name":"a1",
"parentAreaRef":{
"id":"root_id",
},
"_id":"a1_id",
},
{
"name":"a2",
"parentAreaRef":{
"id":"a1_id",
},
"_id":"a2_id",
},
{
"name":"a3",
"parentAreaRef":{
"id":"a2_id",
},
"_id":"a3_id",
},
{
"name":"b1",
"parentAreaRef":{
"id":"root_id",
},
"_id":"b1_id",
},
{
"name":"b2",
"parentAreaRef":{
"id":"b1_id",
},
"_id":"b2_id",
},
{
"name":"b3",
"parentAreaRef":{
"id":"b1_id",
},
"_id":"b3_id",
}
]
显示父子关系的树结构:
[
{
"name": "root",
"_id":"root_id",
"children": [
{
"name": "a1",
"_id":"a1_id",
"children" : [
{
"name" : "a2",
"_id":"a2_id",
"children" : [
{
"name" : "a3"
"_id":"a3_id"
}
]
}
]
},
{
"name": "b1",
"_id":"b1_id",
"children" : [
{
"name" : "b2"
"_id":"b2_id"
},
{
"name" : "b3"
"_id":"b3_id"
}
]
}
]
}
]
(输出结构是一个允许多个根的数组,但是如果我们能够得到一个处理单个根的解决方案,那也很棒.)
输出树如下所示:
root
|
-- a1
| |
| -- a2
| |
| -- a3
|
-- b1
|
-- b2
-- b3
谢谢!
Viv*_*ath 25
我有一个有效的解决方案.就解决问题我可以给你提示.好处是您的数据不包含任何对节点的前向引用.因此,只需一次通过数组即可创建树.如果需要注意,您需要首先遍历整个数组,以构建节点的ID映射.
您的算法将如下所示.
children属性(数组)添加到此节点.children数组中).这应该可以帮助您解决问题.如果您遇到此算法的具体问题,我可以指出问题所在以及如何解决问题或发布解决方案并解释我是如何解决的.
UPDATE
我看了你的解决方案.实际上你不需要递归,你可以使用我上面描述的算法迭代地执行此操作.您还在原地修改结构,这使得算法更复杂.但是你有点走上正轨.这是我解决它的方式:
var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup
var root = null; //Initially set our loop to null
//loop over data
data.forEach(function(datum) {
//each node will have children, so let's give it a "children" poperty
datum.children = [];
//add an entry for this node to the map so that any future children can
//lookup the parent
idToNodeMap[datum._id] = datum;
//Does this node have a parent?
if(typeof datum.parentAreaRef === "undefined") {
//Doesn't look like it, so this node is the root of the tree
root = datum;
} else {
//This node has a parent, so let's look it up using the id
parentNode = idToNodeMap[datum.parentAreaRef.id];
//We don't need this property, so let's delete it.
delete datum.parentAreaRef;
//Let's add the current node as a child of the parent node.
parentNode.children.push(datum);
}
});
现在root指向整个树.
小提琴.
对于元素数组按任意顺序排列的情况,您必须先进行初始化idToNodeMap.算法的其余部分或多或少保持不变(除了您在地图中存储节点的行;这不是必需的,因为您已经在第一次传递中执行了此操作):
var idToNodeMap = data.reduce(function(map, node) {
map[node._id] = node;
return map;
}, {});
我知道这是晚了，但我只是完成这个算法，也许它可以帮助一些人寻找解决同样的问题：http://jsfiddle.net/ akerbeltz / 9dQcn /
它的一个好处是它不需要对原始对象进行任何特殊排序。
如果您需要使其适应您的需求，请更改以下几行：
根据您的结构更改 _id 和 parentAreaRef.id。
if (String(tree[i]._id) === String(item.parentAreaRef.id)) {
根据您的结构更改 parentAreaRef。
if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0])
希望能帮助到你！
更新
根据@Gerfried 评论在此处添加代码：
var buildTree = function(tree, item) {
if (item) { // if item then have parent
for (var i=0; i<tree.length; i++) { // parses the entire tree in order to find the parent
if (String(tree[i]._id) === String(item.parentAreaRef.id)) { // bingo!
tree[i].childs.push(item); // add the child to his parent
break;
}
else buildTree(tree[i].childs, item); // if item doesn't match but tree have childs then parses childs again to find item parent
}
}
else { // if no item then is a root item, multiple root items are supported
var idx = 0;
while (idx < tree.length)
if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0]) // if have parent then remove it from the array to relocate it to the right place
else idx++; // if doesn't have parent then is root and move it to the next object
}
}
for (var i=0; i<data.length; i++) { // add childs to every item
data[i].childs = [];
}
buildTree(data);
console.log(data);
谢谢！