十月 07, 2020

树是什么?

  • JS中没有树,但是可以用ObjectArray构建树;
  • 树的常用操作
    • 深度优先遍历
    • 广度优先遍历
    • 先、中、后序遍历

深度优先遍历:尽可能深的搜索树的分支。(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