浅谈广度优先和深度优先遍历（栈和队列）

1.什么是深度优先和广度优先？

其实简单来说 深度优先就是自上而下的遍历搜索，上图深度优先顺序为 (root–a--c–h--i–d--g–k--b–e--l–m--f–n--o), 广度优先则是逐层遍历，上图广度优先顺序为 (root–a--b–c--d–e--f–h--i–g--k–l--m–n--o)！很好理解就不说了！

2.原理及如何实现？

先上一段代码!

let nodes = {
    "value": "root",
    "child": [{
        "value": "a",
        "child": [{
            "value": "c",
            "child": [{
                "value": "h"
            }, {
                "value": "i"
            }]
        }, {
            "value": "d",
            "child": [{
                "value": "g"
            }, {
                "value": "k"
            }]
        }]
    }, {
        "value": "b",
        "child": [{
            "value": "e",
            "child": [{
                "value": "l"
            }, {
                "value": "m"
            }]
        }, {
            "value": "f",
            "child": [{
                "value": "n"
            }, {
                "value": "o"
            }]
        }]
    }]
}

其实和上图的结构是一样，题目是需要找出每层的vlaue,那么先来看下深度遍历怎么模拟实现？最容易想到的是递归！

//深度遍历
function deepTraversal(nodes) {
    let result = [];
    function recursive(nodes) {
        result.push(nodes.value);
        nodes.child && nodes.child.forEach(node => {
            recursive(node);
        });
    };
    recursive(nodes);
    return result;
};
console.log(deepTraversal(nodes));// ["root", "a", "c", "h", "i", "d", "g", "k", "b", "e", "l", "m", "f", "n", "o"]

第二种方法可以利用的是堆栈的思想, 后进先出！

//深度遍历
function deepTraversal(nodes) {
    let stack = [],
        result = [];
    stack.push(nodes);
    while (stack.length != 0) {
        let node = stack.pop();
        result.push(node.value);
        if (node.child) {
            for (var i = node.child.length - 1; i >= 0; i--) {
                stack.push(node.child[i]);
            };
        };
    };
    return result;
};
console.log(deepTraversal(nodes));// ["root", "a", "c", "h", "i", "d", "g", "k", "b", "e", "l", "m", "f", "n", "o"]

那么广度遍历如何实现呢？广度优先则可以利用队列的思想, 即先进先出！

//广度遍历
function breadthTraversal(nodes) {
    let queue = [],
        result = [];
    queue.push(nodes);
    while (queue.length != 0) {
        var node = queue.shift();
        result.push(node.value);
        if (node.child) {
            for (var i = 0; i < node.child.length; i++) {
                queue.push(node.child[i]);
            };
        };
    };
    return result;
};
console.log(breadthTraversal(nodes));//["root", "a", "b", "c", "d", "e", "f", "h", "i", "g", "k", "l", "m", "n", "o"]

以上就是广度和深度遍历的实现方法！递归方法虽然易写易懂，但是层级如果太深会导致栈溢出，所以可以借助栈和队列的思想来实现！