js中的广度优先遍历（BFS）和深度优先遍历（DFS）

对于下面这段html代码,要求打印出每个节点的标签名和类名：

 <div id='root'>
        <span>123
            <a href="#">
                sdsd
            </a>
            <div>sdsd<a>这是一个a标签</a></div>
        </span>
        <span>456
            <p>这是一个p标签</p>
        </span>
    </div>

深度优先遍历

当使用深度优先遍历算法实现的时候
结果一般为

1.png

该算法先将当前结点的孩子全部遍历结束，在遍历同一级的节点
如图所示：先将2节点下的子节点遍历完，如果3号，4号 有子节点则再继续遍历该节点下的子节点，否则将遍历2节点的兄弟节点，直到遍历结束

深度优先遍历.png

下面给出该算法的js实现：

（1）这是深度优先算法的递归实现

function deepTraversal(node,nodeList) {  
    if (node) {    
            nodeList.push(node);    
            var children = node.children;    
            for (var i = 0; i < children.length; i++) 
      //每次递归的时候将  需要遍历的节点  和 节点所存储的数组传下去
                deepTraversal(children[i],nodeList);    
        }    
    return nodeList;  
}  
var root = document.getElementById('root')
console.log(deepTraversal(root,nodeList=[]))

（2）这是深度优先算法的递归实现

function deepTraversal(node) {  
    var nodeList = [];  
    if (node) {  
        var stack = [];  
        stack.push(node);  
        while (stack.length != 0) {  
            var childrenItem = stack.pop();  
            nodeList.push(childrenItem);  
            var childrenList = childrenItem.children;  
            for (var i = childrenList.length - 1; i >= 0; i--)  
                stack.push(childrenList[i]);  
        }  
    }    
    return nodeList;  
}   
var root = document.getElementById('root')
console.log(deepTraversal(root))

广度优先遍历

当使用广度优先遍历的时候，先依次遍历兄弟节点，然后便利兄弟节点下的子节点
结果一般为：

广度优先的结果.png

广度优先遍历二叉树，也就是按层次的去遍历。依次遍历根节点，然后是左孩子和右孩子。所以要遍历完当前节点的所有孩子，。根据左右孩子的顺序来输出，所以就是先进先出的原则，那么我们当然就想到了队列这个数据结构：

广度优先遍历.png

（1） 广度优先算法的的非递归实现

function wideTraversal(node) {  
    var nodes = [];  
    if (node != null) {  
        var queue = [];  
        queue.unshift(node);  
        while (queue.length != 0) {  
            var item = queue.shift();  
            nodes.push(item);  
            var children = item.children;  
            for (var i = 0; i < children.length; i++)  
                queue.push(children[i]);  
        }  
    }  
    return nodes;  
}
var root = document.getElementById('root');
console.log(wideTraversal(root));