第146题 深度优先和广度优先遍历一个DOM树

遍历DOM树

• 给一个DOM树
• 深度优先遍历结果会输出什么
• 广度优先遍历结果会输出什么

    <!-- 需要遍历的html节点 -->
    <div id="box">
        <p>hello <b>world</b></p>
        <img src="https://www.baidu.com/img/flexible/logo/pc/result.png"/>
        <!-注释->
        <ul>
            <li>a</li>
            <li>b</li>
        </ul>
    </div>

深度优先，以深为主，递归，贪心，有深就深入，否则在回溯到上一级父节点

广度优先，使用队列，对子节点以广为主一层层的遍历

深度优先遍历一个DOM树

    /**
     * 访问节点
     * @param n node
     */
    function visitNode(n) {
        if (n instanceof Comment) {
          // 注释
          console.info('Comment node ---', n.textContent)
        }
        if (n instanceof Text) {
          // 文本
          const t = n.textContent?.trim() // 去掉换行符
          if (t) {
            console.info('Text node ---', t)
          }
        }
        if (n instanceof HTMLElement) {
          // element
          console.info('Element node ---', `<${n.tagName.toLowerCase()}>`)
        }
    }

深度优先遍历-递归

    /**
     * 深度优先遍历-递归
     * @param root dom node
     */
    function depthFirstTraverse1(root) {
        visitNode(root) // 先访问root节点
    
        // .childNodes 和 .children 不一样
        // children // children是HTMLCollection 只获取元素
        // childNodes // childNodes是NodeList 包含Text和Comment节点
        const childNodes = root.childNodes 
        if (childNodes.length) {
            childNodes.forEach(child => {
                depthFirstTraverse1(child) // 递归 深入访问子节点
            })
        }
    }

深度优先遍历-栈实现

    /**
     * 可以不用递归，用栈。因为递归本身就是栈
     * 深度优先遍历：使用栈来实现  先进后出 进push 出pop
     * @param root dom node
     */
     function depthFirstTraverse2(root) {
        const stack = []
    
        // 根节点压栈
        stack.push(root)
    
        // stack.length继续访问栈顶
        while (stack.length > 0) {
            const curNode = stack.pop() // 出栈
            if (curNode == null) break
    
            visitNode(curNode) // 访问栈顶
    
            // 子节点压栈
            const childNodes = curNode.childNodes
            if (childNodes.length > 0) {
                // reverse 反顺序压栈
                // 压栈过程 [div,ul,comment,img,p,b,hello,world,li右,li左,a,b] 遇到子节点倒叙压栈
                Array.from(childNodes).reverse().forEach(child => stack.push(child))
            }
        }
     }

• 递归逻辑更加清晰，但容易发生栈溢出错误。频繁创建函数，效率低一些
• 非递归效率好，但逻辑比较复杂

    <!-- 测试 -->
    <div id="box">
        <p>hello <b>world</b></p>
        <img src="https://www.baidu.com/img/flexible/logo/pc/result.png"/>
        <!-注释->
        <ul>
            <li>a</li>
            <li>b</li>
        </ul>
    </div>
    <script>
        const box = document.getElementById('box')
        depthFirstTraverse2(box)
    </script>

深度优先遍历结果

广度优先遍历一个DOM树

    /**
     * 广度优先遍历 需要一个队列：先进先出 进unshift 出pop
     * @param root dom node
     */
    function breadthFirstTraverse(root) {
        const queue = [] // 数组 vs 链表实现性能更好一些
     
        // 根节点入队列
        queue.unshift(root)
    
        while (queue.length > 0) {
          const curNode = queue.pop() // 当前节点
          if (curNode == null) break
    
          visitNode(curNode)
    
          // 子节点入队
          const childNodes = curNode.childNodes
          if (childNodes.length) {
            // queue = [ul, comment, img, p] 出队pop  p标签出来访问 img出来访问 ...
            // p标签访问 也会导致子p下的子节点入队 [<b>,hello] ...
            childNodes.forEach(child => queue.unshift(child))
          }
        }
    }

    <!-- 测试 -->
    <div id="box">
        <p>hello <b>world</b></p>
        <img src="https://www.baidu.com/img/flexible/logo/pc/result.png"/>
        <!-注释->
        <ul>
            <li>a</li>
            <li>b</li>
        </ul>
    </div>
    <script>
        const box = document.getElementById('box')
        breadthFirstTraverse(box)
    </script>

广度优先遍历结果