JavaScript 递归之 深度优先 和 广度优先

在前端工作当中，经常会遇到树组件、树形表格、机构树等功能，这个时候就需要对后端返回的数据进行处理，在对树形数据处理时，一般是需要用到递归来处理，而递归又分为了 深度优先 和 广度优先，这里给出了两种递归方法的示例

image.png

1 数据准备

const tree = {
    id: 1,
    children: [
        {
            id: 2,
            children: [
                {
                    id: 4,
                    children: [
                        { id: 8 },
                        { id: 9 }
                    ]
                },
                { id: 5 }
            ]
        },
        {
            id: 3,
            children: [
                { id: 6 },
                { id: 7 }
            ]
        },
    ]
};

2 深度优先

顾名思义，深度优先的意思就是以深度为主。我们可以把树机构的分支看作为一个个路径，当进行深度优先的递归时，程序会在一条路径下，一直走下去，直到不能在走为止，然后换一个路径继续走到底，走的层级很深。

通过代码打印的 1, 2, 4, 8, 9 可以看到是把第一个分支里面走到了底

function recursion(list){
    list.forEach(item => {
        console.log(item.id);
        if(item.children){
            recursion(item.children);
        }
    });
}
recursion([tree]); // 调用函数，会依次打印：1, 2, 4, 8, 9, 5, 3, 6, 7

3 广度优先

前面说深度优先是一条道走到底，类似于遇见了岔道，一条岔道走到了底，直到无路可走，而广度优先则恰恰相反，广度优先是把每一个层级的所有选择都走一遍，只有当第一个层级走完之后，才会走第二个层级。

以上面的图为例，先走到1，然后1走完之后，遇见了2和3，广度优先时会先走一下2和3，走完之后，再处理4和5，顺序为1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9

// 方法一：
// 先遍历当前节点，forEach 当中找到当前项所有的子节点，放到同一个数组当中
// 也就是找到下一层级的全部节点
let tempArr = [];
function recursion(list){
    tempArr = [];
    list.forEach(item => {
        console.log(item.id);
        if(item.children){
            tempArr = tempArr.concat(item.children);
        }
    });
    tempArr.length > 0 && recursion(tempArr);
}
recursion([tree]); // 调用函数，会依次打印：1, 2, 3, 4, 5, 6, 7, 8, 9

// 方法二：使用队列的思想，先进先出，依次将节点加入到数组当中，再从前面弹出
function queueRecursion(){
    while (tempArr.length){
        let item = tempArr.shift(); // 弹出第一个
        console.log(item.id);
        if(item.children){
            tempArr = tempArr.concat(item.children); // 添加节点
        }
    }
}
let tempArr = [];
tempArr = [tree]; 
queueRecursion(); // 调用函数，会依次打印：1, 2, 3, 4, 5, 6, 7, 8, 9

原文地址：https://blog.csdn.net/qq_44212319/article/details/126212938