我们在之前一篇文章 如何将评论数据从扁平数组结构转为树形结构 ,讲解过如何把数组结构转为树形结构。这里我们讲下,如何将树形结构转为扁平的数组结构。 我们先来定义一个树形结构的数据: 这是一个多层级的树形结构,我们把它转成数组。 这里我们有两个方式来进行转换:深度优先和广度优先。即优先使用当前节点的子节点,还是优先当前节点的兄弟节点。 深度优先,即若当前节点有子节点,优先遍历子节点,直到没有子节点,才遍历其兄弟节点。 我们输出下结果: 从数组的排列顺序中,也能看到,子节点要比兄弟节点更靠前。 广度优先,即若当前节点有兄弟,优先遍历兄弟节点,有子节点时,则先存起来,等待后续的遍历。 我们输出下结果: 从数组的排列顺序中,也能看到,兄弟节点要比子节点更靠前。 无论是深度优先还是广度优先,复杂度都差不多。从图片上也能看到,这里我们并没有进行特殊的处理,有几个节点的const tree = [
{
id: 1,
nick: '111',
children: [{ id: 6, nick: '666' }],
},
{
id: 2,
nick: '222',
children: [
{
id: 3,
nick: '333',
children: [
{
id: 4,
nick: '444',
children: [
{
id: 5,
nick: '555',
children: [
{ id: 8, nick: '888' },
{ id: 9, nick: '999' },
{ id: 10, nick: 'aaa' },
{ id: 11, nick: 'bbb' },
],
},
],
},
{ id: 7, nick: '777' },
],
},
],
},
];
1. 深度优先转换 #
// 深度优先
const treeToListDepth = (tree) => {
let result = [];
tree.forEach((item) => {
result.push(item); // 将该节点压进去
// 若该节点有子节点,则优先执行子节点
if (Array.isArray(item.children) && item.children.length) {
result = result.concat(treeToListDepth(item.children));
}
});
return result;
};
2. 广度优先转换 #
const treeToListBreadth = (tree) => {
let queue = tree; // 用一个队列来存储将要遍历的节点
const result = [];
while (queue.length) {
const item = queue.shift();
result.push(item);
// 子节点存储到队列中,等待遍历
if (Array.isArray(item.children) && item.children.length) {
queue = queue.concat(item.children);
}
}
return result;
};
3. 总结 #
children
还在,更细致的话,应该把每个节点的 children 属性去掉。
版权属于:
加速器之家
作品采用:
《
署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
》许可协议授权
评论