我的数据具有以下属性:
- 每个条目都有一个唯一标识符(Id)
- 每个条目都有一个指向父节点Id的Parent字段。
- 一个节点可以有多个子节点,但只能有一个父节点。
我第一次尝试构建树如下。由于递归导致了无限循环,因此存在缺陷。即使我解决了这个问题,我也不确定是否有更好的方法来处理这个问题。目前,我是通过两次遍历来完成它的。
由于我的数据量较大,我希望它尽可能高效。它还需要动态重建树(根节点可以是任何节点)
程序中有示例数据:
arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
{"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing
我希望输出的结果是一个有效的JSON结构,其中节点作为“value”字段,子节点作为数组。可能存在嵌套结构错误,因为我手动编写了它。请注意保留HTML标记。
{
"value": {"Id":"1", "Name":"abc", "Parent":""},
"children": [
{
"value": {"Id":"2", "Name":"abc", "Parent":"1"},
"children": [
{
"value": {"Id":"3", "Name":"abc", "Parent":"2"},
"children": []
},
{
"value": {"Id":"4", "Name":"abc", "Parent":"2"},
"children": []
}
]
..
}
示例程序:
function convertToHierarchy(arry, root)
{
//root can be treated a special case, as the id is known
arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
{"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing
var mapping = {}; // parent : [children]
for (var i = 0; i < array.length; i++)
{
var node = arry[i];
if (!mapping[node.Id]) {
mapping[node.Id] = {value: node, children:[] } ;
}else{
mapping[node.Id] = {value: node} //children is already set
}
if (!mapping[node.Parent]) { //TODO what if parent doesn't exist.
mapping[node.Parent] = {value: undefined, children:[ {value: node,children:[]} ]};
}else {//parent is already in the list
mapping[node.Parent].children.push({value: node,children:[]} )
}
}
//by now we will have an index with all nodes and their children.
//Now, recursively add children for root element.
var root = mapping[1] //hardcoded for testing, but a function argument
recurse(root, root, mapping)
console.log(root)
//json dump
}
function recurse(root, node, mapping)
{
var nodeChildren = mapping[node.value.Id].children;
root.children.push({value:node.value, children:nodeChildren})
for (var i = 0; i < nodeChildren.length; i++) {
recurse(root, nodeChildren[i], mapping);
}
return root;
}
我已经想出了3个好的解决方案,希望投票能提供更多惯用的、高效的实现方法。我不确定我的数据是否具有以下属性:输入数组集合中只有一个根元素,而且这个根元素始终是给出的,任何一种实现方法都可能更好。我还应该学习如何进行基准测试,因为我的要求是重建树的效率(快速/占用较少内存)。例如,输入已经被缓存(数组),并重新构建树形结构。
convertToHierarchy(parentid)
....
convertToHierarchy(parentid2)
...