【前端不求人】树形结构和一维数组，一笑泯恩仇

简介

大家好，我是 simple ，我的理想是利用科技手段来解决生活中遇到的各种问题。

在开发过程中，我们有时候遇到后端给你树型结构的数据，需要我们扁平化转换成一维数组。或者需要我们拿到一维数组，转换成树形结构。这种数据结构的转换并未严格规定是前端转还是后端转换，通常是谁能力强，谁负责转换。但只要自己一天没有掌握这种转换方式，必将受制于人，听人差遣。我可以不转，但我绝不能不会转！

树形结构到一维数组的转换

结构介绍

树形结构

const tree = [
    {
        id: 1,
        children: [
            { id: 11 },
            { id: 12 }
        ]
    },
    {
        id: 2,
        children: [
            { id: 21 },
            { 
                id: 22,
                children: [
                    { id: 221 }
                ]
            }
        ]
    }
]

这里分为深度遍历和广度遍历。

深度遍历：从第一个点开始出发，找到第一个点的子节点，找到第一个子节点的第一个子节点...直到子节点没有再下一级的子节点，然后回到上一层的父节点，找到第二个节点，以此往复。

如下方流程图，表示数值就是被遍历的顺序，从节点1开始，然后找到第一个子节点2，找到节点2的第一个子节点3，找到3的第一个子节点4...

广度遍历：从第一个点开始出发，然后直接找到第二个点，找到第三个点...直到这一层已经全部节点被找到，然后进入下一层，即第一个节点的子节点...

如果你已经了解了深度遍历，那么广度遍历其实就是层序遍历，先遍历第一层的所有节点，然后遍历第二层……如下方流程图所示。

简单来说就是树节点转换成一维数组的时候是竖着排还是横着排，竖着排就是先排第一列，再排第二列，而广度遍历就是先排第一行再排第二行。

深度优先遍历（DFS）算法

递归实现

下面这个方法通过递归的方式实现了深度优先遍历

1. 检查树形结构 data 是否为空,若为空则直接返回当前结果 list。
2. 遍历树形结构的顶层节点。
3. 对于每个顶层节点,首先将其推入结果 list。
4. 然后递归调用自身,传入该节点的子树和当前结果 list。
5. 递归终止的条件是子树为空,此时直接返回当前结果 list。
6. 递归返回,并继续遍历其余顶层节点。
7. 全部顶层节点遍历完成,返回结果 list,它包含了树形结构的所有节点,并且节点顺序为 DFS 顺序。

const order = (tree, list = []) => {
    if (!tree?.length) {
        return list
    }
    for (let i = 0, len = tree.length; i < len; i++) {
        list.push(tree[i])
        dfs(tree[i].children, list)
    }
    return list
}

const order = (n) => n?.length ? n.reduce((pre, v) => [...pre, v, ...dfs(v.children)], []) : [];

console.log(order(tree)); 
/**
 * [
 *  { id: 1, children: [ [Object], [Object] ] },
 *  { id: 11 },
 *  { id: 12 },
 *  { id: 2, children: [ [Object], [Object] ] },
 *  { id: 21 },
 *  { id: 22, children: [ [Object] ] },
 *  { id: 221 }
 * ]
 */

迭代实现

相对而言，递归的效率可能不如非递归的循环解决方案。因为递归需要函数调用和返回,这些操作的开销更大。当你追求更高效率的时候，那么就需要使用到迭代的方式了。

实际的递归中隐式调用了栈，在此我们可以直接模拟递归中栈的调用。在迭代过程中，我们会先遍历节点本身，然后从左向右依次先序遍历该每个以子节点为根的子树。

在这里的栈模拟中比较难处理的在于从当前节点 node1 的子节点child1返回时，此时需要处理节点 node1 的下一个节点 node2 ，此时需要记录当前已经遍历完成哪些子节点，才能找到下一个需要遍历的节点。

每次入栈时都将当前节点的 node1 的第一个子节点压入栈中，直到当前节点为空节点为止。 每次查看栈顶元素，如果栈顶节点的子节点已经全部访问过，则将节点从栈中弹出，并从哈希表中移除，表示该以该节点的子树已经全部遍历过；如果当前栈顶节点的子节点还有未遍历的，则将当前节点的 node 的下一个未访问的节点压入到栈中，重复上述的入栈操作。

const iteration = (tree) => {
    if (!tree?.length) {
        return [];
    }
    const ans = [];
    const stack = [];
    const nextIndex = new Map();
    let node = { children: tree };
    while (stack.length || node) {
        while (node) {
            ans.push(node);
            stack.push(node);
            if (!node.children?.length) {
                break;
            }
            nextIndex.set(node, 1);
            node = node.children[0];
        }
        node = stack[stack.length - 1];
        const i = nextIndex.get(node);
        if (i < node.children?.length) {
            nextIndex.set(node, i + 1);
            node = node.children[i];
        } else {
            stack.pop();
            nextIndex.delete(node);
            node = null;
        }
    }
    ans.shift();
    return ans;
}
console.log(iteration(tree)); 

第一次接触这种算法的掘友们可能需要多看几遍才能看懂，不要急于求成，不然容易烧掉自己的icu。 点赞+收藏==学会

广度优先遍历（BFS）算法

递归实现

这个方法的具体逻辑是:

1. 检查树形结构 tree 是否为空,若为空则直接返回。 
2. 定义一个队列 queue,初始值为树形结构的根节点数组。
3. 如果队列不为空,执行如下操作: 
   • 从队列头部取出一项,赋值给 curr,打印 curr 的 id。
   • 检查 curr 是否有子节点,如果有,将其子节点追加到队列尾部。 
4. 递归调用 bfs 方法,传入 queue 作为参数,在队列上重复 1-3 的步骤。
5. 递归终止的条件是队列 queue 为空。

const bfs = (tree, list = []) => {
    if (!tree.length) return;
    let queue = [...tree];
    let curr;
    if (queue.length) {
        curr = queue.shift();
        list.push(curr)
        if (curr.children) queue = [...queue, ...curr.children];
        bfs(queue, list);
    }
    return list
}
bfs(tree)

迭代实现

下面这个方法实现了对树形结构的数据进行广度优先搜索(BFS)。具体的逻辑如下:

1. 检查树形结构 data 是否为空,若为空则直接返回。
2. 定义一个队列,初始只有一项,其 children 属性为树形结构的根节点。
3. 定义结果数组 res,初始为空。
4. While 循环,若队列不为空,执行如下操作:- 从队列头部取出一项,推入到 res 结果数组。- 检查该项的 children 是否为空,若为空则继续循环。- 若不为空,则将该项的所有子节点推入到队列尾部。
5. 循环结束,返回 res 结果数组,它包含了树形结构的所有节点,并且节点顺序为 BFS 顺序。

const iteration = (tree) => {
    if (!tree) return;
    const queue = [{ children: tree }];
    let res = []
    while (queue.length) {
        let curr = queue.shift();
        res.push(curr);
        if (!curr.children?.length) continue
        for (let child of curr.children) {
            queue.push(child);
        }
    }
    return res
}
iteration(tree)

数组到树形结构的转换

我们需要拿到一维数组和根节点id之后，就可以根据父节点id找到它的所有children了。

1. 比如说根节点为-1，那么所有parentId为-1的节点都应该属于根节点的children
2. 如果有一个节点为{id: 1, parentId: -1},那么就可以直接将节点1推入到根节点的children
3. 然后再查所有parentId为1的节点，再推入到id为1的节点children属性中

数据结构

const arr = [
    { id: 1, parentId: -1 },
    { id: 11, parentId: 1 },
    { id: 12, parentId: 1 },
    { id: 2, parentId: -1 },
    { id: 21, parentId: 2 },
    { id: 22, parentId: 2 },
    { id: 221 , parentId: 22 },
]

递归算法

具体的逻辑如下:

1. 定义子节点数组 child,初始为空。
2. 检查列表数据 list 是否为空,若为空则直接返回 child。
3. 遍历列表数据 list。
4. 对于每个项,检查其 parentId 是否等于传入的 id。
   • 若等于,表示该项应属于当前树形结构节点。那么递归调用自身,传入列表和该项的 id,得到其子树。
   • 然后将该项的子树赋值给其 children 属性,并推入到 child 数组。
5. 遍历结束,返回 child 数组,它包含了当前树形结构节点的所有子节点。
6. 通过递归,最终可以构建出整个树形结构,并返回根节点的子树。

const transListToTree = (list, id) => {
    const child = []
    if(!list) return child
    for(let item of list) {
        if(id === item.parentId) {
            item.children = transListToTree(list, item.id)
            child.push(item)
        }
    }
    return child
}

同样做一些简化

const transListToTree = (list, id) =>  list ? list.filter(item => item.parentId === id).map(item => ({...item, children: transListToTree(list, item.id)})) : []

迭代算法

这个方法的主要逻辑是:将一个列表数据转换为树形结构数据。具体的过程如下:

1. 定义一个 map 对象,初始只包含根节点,其 children属性为空数组。
2. 遍历列表数据,为每个项添加 children 属性,并以其 id 为键将其添加到 map 中。
3. 再次遍历列表数据,获取每个项的 parentId,并将其添加到对应的 parent 节点的 children 数组中。
4. 返回根节点的 children,这就是转换后的树形数据。

const transListToTreeData = (list, id) => {
    const map = { [id]: {children: []} }
    list.forEach(item => {
        item.children = []
        map[item.id] = item
    })
    list.forEach(item => {
        map[item.parentId].children.push(item)
    })
    return map[id].children
}

扩展

树形结构的遍历

当你需要对一个树结构进行遍历，那么你可以看看下面这个方法

下面这个方法实现了对树形结构的数据进行遍历。它接收一个回调函数 cb,并在遍历的每个节点上调用该回调函数。具体的逻辑如下:

1. 检查列表数据 list 是否为空,若为空则直接返回。
2. 遍历列表数据 list 的顶层节点。
3. 对于每个顶层节点,首先推入其索引到路径数组 path。
4. 然后将该节点、路径数组和其父节点传入回调函数 cb 中调用。
5. 接着递归调用自身,传入该节点的子树、路径数组和该节点自身作为父节点。
6. 递归返回时,从路径数组 path 中弹出该节点的索引。
7. 继续遍历其余顶层节点。
8. 递归终止的条件是子树为空。
9. 通过递归,最终可以遍历树形结构的所有节点,并在每个节点上调用回调函数 cb。

const traverse = (list, cb, path = [], parent = null) => {
    if(!list?.length) return
    for(let i = 0,len = list.length;i < len;i++) {
        path.push(i)
        const child = list[i]
        cb(child, path, parent)
        traverse(child.children, cb, path, child)
        path.pop()
    }
}
traverse(tree, (item, path, parent) => {
    console.log(item, path, parent) 
})

根据唯一值获取路径

当你需要根据一个唯一值，去获取在树形结构中节点的路径。 具体的逻辑如下:

1. 检查树形结构 data 是否为空,若为空则直接返回 false。
2. 遍历树形结构的顶层节点。
3. 对于每个顶层节点,首先将其推入路径数组 path。
4. 如果该节点的 id 等于传入的 id,则直接返回 path,表示找到节点的路径。
5. 否则,递归调用自身,传入该节点的子树、要查找的 id 和当前路径 path。
6. 如果递归返回结果为真,表示在子树中找到节点路径,直接返回。
7. 否则,从路径 path 中弹出该节点,继续遍历其余顶层节点。
8. 递归终止的条件是子树为空,此时返回 false。
9. 如果全部顶层节点遍历完成仍未找到,则返回 false。

const getPath = (tree, id, path = []) => {
    if (!tree?.length) return false
    for (let item of tree) {
        path.push(item)
        if (id === item.id) {
            return path
        }
        if (getPath(item.children, id, path)) {
            return path
        }
        path.pop()
    }
}

console.log(getPath(tree, 221)); 
// [
//  { id: 2, children: [ [Object], [Object] ] },
//  { id: 22, children: [ [Object] ] },
//  { id: 221 }
// ]

根据索引获取节点

这个方法实现了在树形结构中根据节点索引路径获取子节点。具体的逻辑如下:

1. 定义初始的 child 节点,其 children 属性为树形结构的根节点。
2. 如果索引路径 indexList 非空,执行如下操作:
   • 从 indexList 中取出第一个索引
   • 根据该索引,获取 child 节点的子节点中的对应项
   • 将该子节点赋值给 child,作为新的要搜索的节点
3. 重复步骤 2,直到 indexList 为空
4. 此时的 child 即为根据索引路径得到的子节点,返回该节点

const getChildByIndex = (tree, indexList) => {
    let child = { children: tree }
    while (indexList.length) {
        child = child.children[indexList.shift()]
    }
    return child
}
console.log(getChildByIndex(tree, [1, 1, 0])); // { id: 221 }

总结

个人觉得要想写好树形结构的相关逻辑，数据分析必不可少。宁可不动键盘也要先分析清楚数据之间的关系。如果你对树形结构、广度优先搜索、深度优先搜索、递归等主题有任何其他问题,欢迎在评论中提出。