解释下深度优先遍历和广度优先遍历的区别及如何实现

Answer 1

1、深度优先采用堆栈结构，先进后出，所占的空间较小，执行时间较长；
2、广度优先采用队列结构先进先出，所占空间较大，执行时间短，空间换时间；

const data = [
        {
            name: 'a',
            children: [
                { name: 'b', children: [{ name: 'e' }] },
                { name: 'c', children: [{ name: 'f' }] },
                { name: 'd', children: [{ name: 'g' }] },
            ],
        },
        {
            name: 'a2',
            children: [
                { name: 'b2', children: [{ name: 'e2' }] },
                { name: 'c2', children: [{ name: 'f2' }] },
                { name: 'd2', children: [{ name: 'g2' }] },
            ],
        }
    ]

    //深度优先
    function byDeepth(data) {
        let result = []
        const map = (item) => {
            result.push(item.name)
            item.children && item.children.forEach((item) => map(item))
        }
        data.forEach((item) => {
            map(item)
        })
        return result.join(',')
    }

    //广度优先
    function byBreadth(data) {
        let result = []
        let queque = data
        while (queque.length > 0) {
            result.push(queque[0].name)
            if (queque[0].children) {
                queque = queque.concat(queque[0].children)
            }
            queque.shift()
        }
        return result.join(',')
    }
    console.time('深度优先')
    console.log('深度优先', byDeepth(data))
    console.timeEnd('深度优先')

    console.time('广度优先')
    console.log('广度优先', byBreadth(data))
    console.timeEnd('广度优先')