二叉树的BFS和DFS

BFC：广度优先搜索（又称之为 层次遍历、宽度优先搜索）

BFC：（Breadth First Search）

他的访问顺序是：先访问上一层，在访问下一层，一层一层的往下访问

所以下图BFS遍历的结果是：A→B→C→D→E→F

代码实现：使用一个队列辅助

let result = []

function bfsOrder(tree) {
    if (tree === null) return

    let q = [] // 使用数组模拟队列 先进先出

    q.push(tree)

    // 开始一层一层遍历
    while (q.length > 0) {

        // 挨个取出这一层的节点
        let currentNode = q.shift() // 模拟队列的先进先出

        result.push(currentNode.val)

        // 继续遍历下一层
        if (currentNode.left) {
            q.push(currentNode.left)
        }
        if (currentNode.right) {
            q.push(currentNode.right)
        }
    }
}

// 测试
bfsOrder(A)
console.log(result); // [ 'A', 'B', 'C', 'D', 'E', 'F' ]

DFC：深度优先搜索

DFC：（Depth First Search）

他的访问顺序是：先访根节点，然后左结点，一直往下，直到最左结点没有子节点的时候然后往上退一步到父节点，然后父节点的右子节点在重复上面步骤……

所以下图深度优先搜索遍历的结果是：A→B→D→E→C→F

代码实现 递归

let result = []

function dfsOrder(tree) {
    if (tree === null) return

    result.push(tree.val)
    dfsOrder(tree.left)
    dfsOrder(tree.right)

}

// 测试
dfsOrder(A)
console.log(result); // [ 'A', 'B', 'D', 'E', 'C', 'F' ]

参考

数据结构-6,树