遍历之深度优先遍历和广度优先遍历的区别

  在日常工作中，我们经常会用到遍历操作。如遍历一颗树，找到某个节点。遍历又分为广度优先遍历(Depth First Traversal)和深度优先遍历(Breadth First Traversal)两种。

1、深度优先遍历(DFS)

  首先访问根节点，其次是它的子节点，访问子节点的子节点，直到子节点没有子节点为止，就这样一直循环下去，直到根节点下所有的子节点都被访问到为止。简单点说就是，从根节点出发，按照从左到右的顺序，访问其子节点，如果子节点还有子节点，则一直向下访问，直到没有子节点为止。然后再返回到离根节点最近的而没有访问到的子节点，然后按照前面的查找方法，一遍一遍的循环下去，直到所有的节点被访问完毕为止。 算法实现如下：

    function deepTranversal(node，nodeList=[]){
        if(node){
            nodeList.push(node)
            let children=node.children;
            let len=children.length;
            if(children&&len){
                for(let i=0;i<len;i++){
                    deepTranversal(node,nodeList)
                }
            }
        }
        return nodeList;
    }

    //验证
    <div id="A">
        A
        <div id="B1">
            B1
            <span id="C1">C1</span>
            <span id="C2">C2</span>
        </div>
        <div id="B2">B2
            <span id="C3">C3</span>
            <span id="C4">C4</span>
        </div>
        <div id="B3">B3
            <span id="C5">C5</span>
            <span id="C6">C6</span>
        </div>
        <div id="B4">B4
            <span id="C7">C7</span>
            <span id="C8">C8</span>
        </div>
    </div>
    //如上所示节点树
    let  node=document.querySelector("#A");
    for(let item of deepTranversal(node,[])){
        console.log(item.id);
    }
    

输出结果如下

2、广度优先遍历

  首先访问根节点，其次是它的子节点，然后按照从左到右的顺序，访问子节点的子节点，直到子节点没有子节点为止，就这样一直循环下去，直到根节点下所有的子节点都被访问到为止。简单点说就是从根节点出发，一层一层的从上向下访问，同层节点从左往右访问，直到所有的节点都被访问到为止。 算法实现如下：

    function breadthTranversal(node,nodeList=[]){
        let satck=[];
        if(node){
            stack.push(node);
            while(stack.length){
                let item=stack.shift();
                nodeList.push(item);
                let children=item.children;
                let len=children.length;
                for(let i=0;i<len;i++){
                    stack.push(children[i]);
                }
            }
        }
        return nodeList;
    }
    //验证 节点还是上面的节点数据
    for(let item of breadthTranversal(node,[])){
        console.log(item.id)
    }

输出结果如下