美文网首页
深度优先与广度优先

深度优先与广度优先

作者: 明里人 | 来源:发表于2019-09-25 12:35 被阅读0次
    深度优先:先将自己所有子元素遍历完,再回来遍历下一个邻近节点。递归就是深度优先遍历。
    广度优先:先将自己与邻近节点这一层遍历完,再遍历自已与邻近节点下的第一层子节点,直至遍历结束。
    <div id="parent">
        <div class="child-1">
            <div class="child-1-1">
                <div class="child-1-1-1">a</div>
            </div>
        </div>
    
        <div class="child-2">
            <div class="child-2-2">
                <div class="child-2-2-2">b</div>
            </div>
        </div>
    
        <div class="child-3">
            <div class="child-3-3">
                <div class="child-3-3-3">c</div>
            </div>
        </div>
    </div>
    
    // 深度优先
    let parent = document.querySelector('#parent');
    let deepTraversal1 = (node, nodeList = []) => {
        if (node !== null) {
            nodeList.push(node)
            let children = node.children
            for (let i = 0; i < children.length; i++) {
                deepTraversal1(children[i], nodeList)
            }
        }
        return nodeList
    }
    console.log(deepTraversal1(parent));
    
    image.png
    // 广度优先
    let widthTraversal2 = (node) => {
        let nodes = [] // 存储元素集合
        let stack = [] // 遍历元素集合 按顺序先进先出一层一层遍历
        if (node) {
            stack.push(node)
             while (stack.length) {
                 let item = stack.shift()
                 let children = item.children
                 nodes.push(item)
                 // 队列,先进先出
                 // nodes = [] stack = [parent]
                 // nodes = [parent] stack = [child1,child2,child3]
                 // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
                 // nodes = [parent,child1,child2]
                 for (let i = 0; i < children.length; i++) {
                     stack.push(children[i])
                 }
             }
         }
        return nodes
    }
    console.log(widthTraversal2(parent));
    
    image.png

    相关文章

      网友评论

          本文标题:深度优先与广度优先

          本文链接:https://www.haomeiwen.com/subject/hhwiuctx.html