树
十月 07, 2020
本文共计:
498 字
预计阅读时长:
2分钟
树是什么?
JS
中没有树,但是可以用Object
和Array
构建树;- 树的常用操作
- 深度优先遍历
- 广度优先遍历
- 先、中、后序遍历
深度优先遍历:尽可能深的搜索树的分支。(DFS
)
武功心法:访问根节点—对根节点的children
挨个进行深度优先遍历。
1 | const tree = { |
广度优先遍历:先访问距离根节点最近的节点。(BFS
)
武功心法:
- 新建一个队列,根节点入队
- 队头出队并访问
- 队头的children挨个入队
- 重复第二、三步,直到队列为空
1 | const bfs = root => { |
二叉树的先、中、后序遍历
什么是二叉树?
树种每个节点最多只能由两个子节点。
1 | // 二叉树 |
先序遍历内功心法
- 根左右
1 | const POrder = tree => { |
中序遍历内功心法
- 左根右
1 | const POrder = tree => { |
后续遍历内功心法
左右根
1
2
3
4
5
6
7
8
9
10const 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
查看评论