请教一个树形结构扁平化算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 935 天前的主题，其中的信息可能已经有所发展或是发生改变。

需要将以下树形结构转成扁平化数组，同时添加一个从父级到子级的路径数组。

let tree = [
    {
        id: 1,
        title: "grandfather",
        children: [
            {
                id: 3,
                title: "father"
            },
            {
                id: 4,
                title: "father2",
                children: [{
                    id: 6,
                    title: "child1"
                }]
            }
        ]
    },
    {
        id: 2,
        name: "grandfather2",
        children: [{
            id: 5,
            name: "father3"
        }]
    }
];


let list = [
    { id: 1, title: "grandfather", path: ['grandfather'] },
    { id: 3, title: "father", path: ['grandfather', 'father'] },
    { id: 4, title: "father2", path: ['grandfather', 'father2'] },
    { id: 6, title: "child1", path: ['grandfather', 'father2', 'child1'] },
    { id: 2, title: "grandfather", path: ['grandfather2'] },
    { id: 5, title: "father3", path: ['grandfather2', 'father3'] },
];

递归问题实在有点让我头疼，没有能解出来，因此请教一下万能的 V 友有没有什么好的解法。

8 条回复 • 2022-06-07 09:42:34 +08:00

cpstar

2022-06-06 22:51:54 +08:00

深度优先遍历

sharida

2022-06-06 22:55:17 +08:00

递归
```javascript
const res = [];
function tree2list(tree, path = []) {
for (let i = 0; i < tree.length; i++) {
const item = tree[i];
const p = [...path, item.title];
res.push({ ...item, path: p });
if (Array.isArray(item.children)) {
cb(item.children, p);
}
}
}
```

cpstar

2022-06-06 23:00:10 +08:00

补充 1# 就是递归

array list = [];
func recursion(node, parent_path) {
list.add({id: node.id, title: node.title, path: parent_path});
for(let n in node.children)
recursion(n, parent_path.add(n.title));
}
for (let t in tree) {
recursion(t, [t.title]);
}

luob

2022-06-06 23:23:21 +08:00

来点函数式

const h = (list, paths, sum) => list.reduce((acc, { id, title, children }) => ([...acc, { id, title, paths: [...paths, title] }, ...h(children || [], [...paths, title], [])]), sum);

const flat = (tree) => h(tree, [], []);

rabbbit

2022-06-06 23:36:42 +08:00

const flat = (children) => {
　 const pathMap = new Map(children.map((i) => [i.id, [i.title]]));
　 const list = [...children];
　 const result = [];
　 while (list.length > 0) {
　　 const { id, title, children } = list.shift();
　　 const path = pathMap.get(id);
　　 result.push({ id, title, path });
　　 if (children) {
　　　 list.unshift(...children);
　　　 children.forEach((i) => pathMap.set(i.id, [...path, i.title]));
　　}
　}
　 return result;
};

wunonglin

2022-06-06 23:38:53 +08:00

https://s3.bmp.ovh/imgs/2022/06/06/9091a15a6016a2cc.png

这样不知道对不对

Kei001

2022-06-07 09:38:50 +08:00

@sharida @cpstar @luob @rabbbit @wunonglin 感谢，解决了！

Kei001

2022-06-07 09:42:34 +08:00

@wunonglin 第二个父节点的 title 不小心写成了 name ，没想到你也考虑到了，哈哈感谢！