广度与深度优先遍历

By bobo 2021-12-26 22:37:41 文章分类:JavaScript

广度优先遍历


/**
 * 广度优先遍历口诀
 * 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