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

Question

我正在尝试创建数据库中所有页面的“树” View 。为此，我为每个页面指定了一个“父”属性以及其子页面的唯一 ID。

现在我想递归地将这个对象数组嵌套在其自身内部，以便所有子页面都嵌套在其适当的父页面内。使用父 id 作为引用，从这里转换以下数组的最有效方法是什么:

[ 
    { 
        _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 复杂性方面最时间效率的方法。

该算法包含三个线性复杂度步骤 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())

步骤 2)

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

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)

迭代 map 中的项目并获取顶级父级:

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);

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