树

树

十月 07, 2020 本文共计： 498 字 预计阅读时长： 2分钟

树是什么？

  • JS中没有树，但是可以用Object和Array构建树；
  • 树的常用操作
    • 深度优先遍历
    • 广度优先遍历
    • 先、中、后序遍历

深度优先遍历：尽可能深的搜索树的分支。(DFS)

alt

武功心法：访问根节点—对根节点的children挨个进行深度优先遍历。

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
34
35
36
37
38
39
const tree = {
    val: 'a',
    children: [
        {
            val: '1',
            children: [
                {
                    val: 'b',
                    children: [
                        {
                            val: '1',
                            children: []
                        }, {
                            val: '2',
                            children: []
                        },
                    ],
                }
            ]
        }, {
            val: '2',
            children: []
        },
    ],
}

const dfs = root => {
    console.log(root.val)
    root.children.forEach(dfs)
}

dfs(tree)
// console
/* a
   1
   b
   1
   2
   2 */

广度优先遍历：先访问距离根节点最近的节点。(BFS)

alt

武功心法：
- 新建一个队列，根节点入队
- 队头出队并访问
- 队头的children挨个入队
- 重复第二、三步，直到队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const bfs = root => {
    const q = [root];
    while (q.length >0) {
        const n = q.shift();
        console.log('bfs',n.val);
        n.children.forEach(child => {
            q.push(child);
        })
    }
}

bfs(tree)

// console
/**
    bfs a
    bfs 1
    bfs 2
    bfs b
    bfs 1
    bfs 2
 */

二叉树的先、中、后序遍历

什么是二叉树？

树种每个节点最多只能由两个子节点。

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
34
35
36
37
38
39
// 二叉树
const BTree = {
    val: 2,
    left: {
        val: 7,
        left: {
            val: 2,
            left: null,
            right: null
        },
        right: {
            val: 6,
            left: {
                val: 5,
                left: null,
                right: null
            },
            right: {
                val: 11,
                left: null,
                right: null
            }
        }

    },
    right: {
        val: 5,
        left: null,
        right: {
            val: 9,
            left: {
                val: 4,
                left: null,
                right: null
            },
            right: null
        }
    }
}

先序遍历内功心法

  • 根左右
1
2
3
4
5
6
7
8
9
10
const POrder = tree => {
    if(!tree) { return }
    console.log(tree.val);
    POrder(tree.left)
    POrder(tree.right)
}

POrder(BTree)

// 2 7 2 6 5 11 5 9 4

中序遍历内功心法

  • 左根右
1
2
3
4
5
6
7
8
9
10
const POrder = tree => {
    if(!tree) { return }
    POrder(tree.left)
    console.log(tree.val);
    POrder(tree.right)
}

POrder(BTree)

// 2 7 5 6 11 2 5 4 9

后续遍历内功心法

  • 左右根

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    const POrder = tree => {
        if(!tree) { return }
        POrder(tree.left)
        POrder(tree.right)
        console.log(tree.val);
    }

    POrder(BTree)

    // 2 5 11 6 7 4 9 5 2