使用id作为引用递归地将对象数组嵌套到树中的最佳方法是什么？

Question

我试图为我的数据库中的所有页面创建一个“树”视图。要做到这一点，我已经给每个页面一个“父”属性以及它是子页面的唯一id。

现在，我想递归地将这个数组对象嵌套在自己的内部，这样所有子页面都嵌套在相应的父页面中。使用父id作为引用，从这里转换以下Array的最有效方法是什么：

[ 
    { 
        _id: 1,
        title: 'Page A-1',
        parent: null 
    },
    { 
        _id: 2,
        title: 'Page A-2',
        parent: 1 
    },
    { 
        _id: 3,
        title: 'Page A-3',
        parent: 2 
    },
    { 
        _id: 4,
        title: 'Page A-4',
        parent: 3 
    },
    { 
        _id: 5,
        title: 'Page A-5',
        parent: 4 
    },
    { 
        _id: 6,
        title: 'Page B-1',
        parent: null 
    },
    { 
        _id: 7,
        title: 'Page B-2',
        parent: 6 
    },
    { 
        _id: 8,
        title: 'Page B-3',
        parent: 7 
    },
    { 
        _id: 9,
        title: 'Page B-4',
        parent: 8 
    },
    { 
        _id: 10,
        title: 'Page B-5',
        parent: 8 
    },
    { 
        _id: 11,
        title: 'Page C-1',
        parent: null
    }
]

这方面：

[ 
    { 
        _id: 1,
        title: 'Page A-1',
        children: [
            { 
                _id: 2,
                title: 'Page A-2',
                children: [
                    { 
                        _id: 3,
                        title: 'Page A-3',
                        children: [
                            { 
                                _id: 4,
                                title: 'Page A-4',
                                children: [
                                    { 
                                        _id: 5,
                                        title: 'Page A-5',
                                        children: [

                                        ]
                                    }       
                                ]
                            }       
                        ]
                    }
                ]
            }       
        ]
    },
    { 
        _id: 6,
        title: 'Page B-1',
        children: [
            { 
                _id: 7,
                title: 'Page B-2',
                children: [
                    { 
                        _id: 8,
                        title: 'Page B-3',
                        children: [
                            { 
                                _id: 9,
                                title: 'Page B-4',
                                children: []
                            },
                            { 
                                _id: 10,
                                title: 'Page B-5',
                                children: []
                            }
                        ]
                    }       
                ]
            }
        ]
    },
    { 
        _id: 11,
        title: 'Page C-1',
        children: []
    }
]

Answer 1

我的回答将忽略这样做的必要性，并在大O复杂性方面给您提供最time-efficient的方法。

算法包含线性复杂度O(items.length)三个步骤，使整个算法也是线性的。

注意:作为常见的权衡，我牺牲了空间来实现最佳的时间复杂度。

第1步)：

遍历项并构建一个Map<id, object>

// you can also use a POJO here
// i'm using a map to demonstrate the appropriate data structure
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  // Note: it might be safer to not use original objects when building the tree
  // and create new objects instead. See the comment in step 2 as well.
  /*
    map.set(item._id, {
      ...item,
      children: []
    })
  */
  return map;
}, new Map())

第二步)

迭代您的项，并将每个项嵌套在其父项下。

items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    // Note: this will actually edit your original objects
    // Since mutability is the cause of many bugs, if you can afford it
    // I'd create new objects with the children property in step 1
    // when inserting items into the map which would make this if
    // statement redundant
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

第3步)

遍历地图中的项目，并获取顶级父母：

const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

下面是一个完整的例子：

​

const items=[{_id:1,title:"Page A-1",parent:null},{_id:2,title:"Page A-2",parent:1},{_id:3,title:"Page A-3",parent:2},{_id:4,title:"Page A-4",parent:3},{_id:5,title:"Page A-5",parent:4},{_id:6,title:"Page B-1",parent:null},{_id:7,title:"Page B-2",parent:6},{_id:8,title:"Page B-3",parent:7},{_id:9,title:"Page B-4",parent:8},{_id:10,title:"Page B-5",parent:8},{_id:11,title:"Page C-1",parent:null}];

// step 1
const map = items.reduce((map, item) => {
  map.set(item._id, item);
  return map;
}, new Map())

// step 2
items.forEach(item => {
  if (item.parent) {
    const parent = map.get(item.parent);
    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(item);
  }
})

// step 3
const result = [];
for (const item of map.values()) {
  if (!item.parent) {
    result.push(item);
  }
}

console.log(result);

​

在现实世界中，性能不仅取决于算法的复杂性，还取决于所有使用的操作和数据结构的实际实现细节。如果这样的关键性能对您很重要，那么构建一个最优的算法需要实际的基准测试。

Answer 2

我将在遍历数组时查找所有对象，并在同一个循环中将子对象添加到父级。假设您的数据不太大，没有内存问题，您可以在一个循环中遍历数组，而不必搜索树的父级。

注意:这假设父母是在数组中的子列之前定义的。如果不是，您将不得不在循环中做更多的工作(但不多)。

​

let data = [
    {
        _id: 1,
        title: 'Page A-1',
        parent: null
    },
    {
        _id: 2,
        title: 'Page A-2',
        parent: 1
    },
    {
        _id: 3,
        title: 'Page A-3',
        parent: 2
    },

    {
        _id: 4,
        title: 'Page A-4',
        parent: 3
    },
    {
        _id: 5,
        title: 'Page A-5',
        parent: 4
    },
    {
        _id: 6,
        title: 'Page B-1',
        parent: null
    },
    {
        _id: 7,
        title: 'Page B-2',
        parent: 6
    },
    {
        _id: 8,
        title: 'Page B-3',
        parent: 7
    },
    {
        _id: 9,
        title: 'Page B-4',
        parent: 8
    },
    {
        _id: 10,
        title: 'Page B-5',
        parent: 8
    },
    {
        _id: 11,
        title: 'Page C-1',
        parent: null
    }
]

let lookup = {}
let tree = {}

data.forEach(item => {
    let obj = {_id: item._id, title: item.title, children: [] }
    // add to lookup
    if(!lookup[item._id]) lookup[item._id] =  obj

    if(!item.parent) {
        // a root node. Add directly to tree
        tree[item._id] = obj
    } else{
        //  a child node. Add to parent's children array
        lookup[item.parent].children.push(obj)
    }
})
console.log(tree)

​