JS算法 —— 二叉树的dfs(深度)和bfs(广度)遍历_js dfs

一、二叉树

演示图

tree:

const tree = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: {
            val: 4,
            left: null,
            right: {
                val: 7,
                left: null,
                right: {
                    val: 8,
                    left: null,
                    right: null
                }
            }
        }
    },
    right: {
        val: 3,
        left: {
            val: 5,
            left: null,
            right: null
        },
        right: {
            val: 6,
            left: null,
            right: null
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

二、dfs深度优先遍历

从左到右，每次都遍历到叶子节点。
使用递归的方法，先递归左部分，然后递归右边部分。

function dfs(node) {
    if (!node) {
        return;
    }
    console.log(node.val); //处理操作
    dfs(node.left);
    dfs(node.right);
}

dfs(tree);
1
2
3
4
5
6
7
8
9
10

三、bfs广度优先遍历（层次遍历）

从上到下，每次都要把每层遍历完。
引入队列，来保存每层的节点，用于遍历。

//运用队列
var bfs = function (root) {
    //二叉树的层次遍历
    let res = [];
    let quene = [root];
    if (root === null) {
        return res;
    }
    while (quene.length !== 0) {
        let currentLevel = [];
        let len = quene.length;
        for (let i = 0; i < len; i++) {
            let node = quene.shift();
            currentLevel.push(node.val);
            console.log(node.val);
            if (node.left) quene.push(node.left);
            if (node.right) quene.push(node.right);
        }
        res.push(currentLevel);
    }
    return res;
};

let res = bfs(tree);
console.log(res);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

运用了队列先进先出的原则，首先将队列初始化为只包含根节点：

let quene = [root]
1

因为后面还会给队列添加节点，所以使用while循环来保证一直循环到所有节点遍历完。
使用一个for循环遍历当前层的所有节点：

for (let i = 0; i < len; i++) {
    let node = quene.shift();//取出队列第一个元素
    currentLevel.push(node.val);
    console.log(node.val);
    if (node.left) quene.push(node.left);
    if (node.right) quene.push(node.right);
}
1
2
3
4
5
6
7

在访问当前层节点的同时，将当前层每个节点的子节点入队列，用于下一次while循环访问。
例如第一次while循环后，也就是" 1 "被访问后，队列应该是：

[{
        val: 2,
        left: null,
        right: {
            val: 4,
            left: null,
            right: {
                val: 7,
                left: null,
                right: {
                    val: 8,
                    left: null,
                    right: null
                }
            }
        }
    },
    {
        val: 3,
        left: {
            val: 5,
            left: null,
            right: null
        },
        right: {
            val: 6,
            left: null,
            right: null
        }
    }

]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

下一次出队列的便是" 2 "节点。