深度优先和广度优先遍历算法

DFS深度优先遍历

<div class="root">
    <div class="child1">
        <a href="">link</a>
        <span>text</span>
    </div>
    <div class="child2">
        <span>2</span>
    </div>
</div>

深度优先遍历结果：

[
    div.root,
    div.child1,
    a,
    span,
    div.child2,
    span
]

DFS递归实现：
深度优先需要优先查找子节点，因此需要实现后进先出（栈）

function deepTraversal(node, nodeList) {
    if (node) {
        const children = node.children || []
        nodeList.push(node)
        for (let i = 0 ; i < children.length ; i++) {
            deepTraversal(children[i], nodeList)
        }
    }
    return nodeList
}

递归maybe导致栈溢出！！！

DFS递归优化（尾递归）

function tailD(nodeList=[], stack=[]){
    if(!stack.length) return nodeList
    return tailD([].concat(nodeList,stack[stack.length - 1]),[].concat(stack,Array.from(stack.pop().children||[]).reverse()))
}

使用方式: tailD([], [node])

DFS遍历实现：

function deepTraversal(node) {
    const nodeList = []
    const stack = []
    stack.push(node)
    while (stack.length) {
        let currentNode = stack.pop() // 需要后进先出
        let children = currentNode.children
        nodeList.push(currentNode)
        for (let i=children.length - 1;i>=0;i--){
            stack.push(children[i])
        }
    }
    return nodeList
}

BFS 广度优先遍历

广度优先需要优先查找兄弟节点，因此要实现先进先出（队列）

BFS结果：

[
    div.root,
    div.child1,
    div.child2,
    a,
    span,
    span
]

BFS递归实现：

let queen = [node]
let nodeList = []
let count = 0

function bTraversal() {
    let currentNode = queen[count]
    if (currentNode) {
        let children = currentNode.children || []
        nodeList.push(currentNode)
        queen.push(...children)
        count ++
        bTraversal(count)
    }
    return nodeList
}

BFS遍历实现：

function bTraversal(node) {
    const nodeList = []
    const queen = []
    queen.push(node)
    while (queen.length) {
        let currentNode = queen.shift()
        let children = currentNode.children
        nodeList.push(currentNode)
        for (let i=0;i<children.length;i++){
            queen.push(children[i])
        }
    }
    return nodeList
}