从祖先数据构建嵌套列表

Question

给定结构：

{
    id: 'id-1',
    name: 'name1',
    ancestors: []
},{
    id: 'id-2',
    name: 'name2',
    ancestors: []
},{
    id: 'id-3',
    name: 'name3',
    ancestors: ['id-1']
},{
    id: 'id-4',
    name: 'name4',
    ancestors: ['id-3', 'id-1']
}

• 假设他们不是以任何有意义的方式进行分类。
• 祖先字段是一个阵列，显示了到顶级的路径。

构建嵌套列表的最有效方法是什么？

我的第一个想法是一种递归方法，但这似乎很麻烦，因为它会反复搜索整个列表。由于这将是在浏览器中运行的JavaScript解决方案，这可能是有问题的。

Answer 1

您可以构建一棵树，然后渲染一个嵌套列表。

function getTree(data) {
    var o = {};
    data.forEach(function (a) {
        var parent = a.ancestors[0];
        if (o[a.id] && o[a.id].children) {
            a.children = o[a.id].children;
        }
        o[a.id] = a;
        o[parent] = o[parent] || {};
        o[parent].children = o[parent].children || [];
        o[parent].children.push(a);
    });
    return o.undefined.children;
}
function buildList(tree, target) {
    var ul = document.createElement('ul');
    tree.forEach(o => {
        var li = document.createElement('li');
        li.appendChild(document.createTextNode(o.name));
        buildList(o.children || [], li);
        ul.appendChild(li);
    });
    target.appendChild(ul);
}
var data = [{ id: 'id-1', name: 'name1', ancestors: [] }, { id: 'id-2', name: 'name2', ancestors: [] }, { id: 'id-3', name: 'name3', ancestors: ['id-1'] }, { id: 'id-4', name: 'name4', ancestors: ['id-3', 'id-1'] }],
    tree = getTree(data);
console.log(tree);
buildList(tree, document.body);

Answer 2

建立一个地图，以更快地查找：

 const byId = new Map(array.map(el => ([el.id, el]));

然后，创建嵌套树非常简单，我们只检查一个节点是否没有祖先，然后是根元素，否则我们将其添加为父母的孩子：

 const root = [];
 for(const obj of array) {
   if(obj.ancestors.length) {
     const parent = byId.get(obj.ancestors[0]);
     if(parent.children) {
       parent.children.push(obj);
     } else {
       parent.children = [obj];
     }
   } else {
    root.push(obj);
   }
 }

因此，现在root包含嵌套树，您可以使用递归方法将其穿越：

 function traverse(elements) {
    for(const el of elements) {
      // Render ...
      traverse(el.children || []);
    }
 }
 traverse(root);