广度与深度优先遍历

广度优先遍历

/**
 * 广度优先遍历口诀
 * 1. 新建一个队列，把根节点入队
 * 2. 把队头出队并访问
 * 3. 把队头的孩子们挨个入队
 * 4. 重复 2,3 步骤，直到队列为空
 */

const bt = require("./bt")

const bfs = (root) => {
    // 1. 新建一个队列，把根节点入队
    const queue = [root]

    // 4. 重复 2,3 步骤，直到队列为空
    while (queue.length) {
        // 2. 把队头出队并访问
        const node = queue.shift()
        console.log(node.val)

        // 3. 把队头的孩子们挨个入队
        if (node.left) {
            queue.push(node.left)
        }
        if (node.right) {
            queue.push(node.right)
        }
    }
}


bfs(bt) // 1,2,3,4,5,6,7

深度优先遍历

/**
 * 深度优先遍历口诀
 * 1. 访问根节点的值
 * 2. 对根节点的孩子们进行深度优先遍历
 */

const bt = require('./bt')

const dfs = (root) => {
    if (!root) {
        return false
    }

    // 1. 访问根节点的值
    console.log(root.val)

    // 2. 对根节点的孩子们进行深度优先遍历
    if (root.left) {
        dfs(root.left)
    }
    if (root.right) {
        dfs(root.right)
    }
}

dfs(bt) // 1,2,4,5,3,6,7

模拟数据

/*
二叉树

        1
     /   \
    2     3
   / \    / \
  4   5  6   7
*/
const bt = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}


module.exports = bt