2rever的前端小站

js二叉树遍历方法

Word count: 442 / Reading time: 2 min
2018/10/23 Share

深度优先遍历

  • 二叉树前序遍历
1
2
3
4
5
6
7
8
//二叉树前序遍历
function preOrderTraverse(root,action = console.log){
if (root) {
action(root.val)
preOrderTraverse(root.left,action)
preOrderTraverse(root.right,action)
}
}
  • 二叉树后序遍历
1
2
3
4
5
6
7
8
//二叉树后序遍历
function postOrderTraverse(root,action = console.log){
if (root) {
postOrderTraverse(root.left,action)
postOrderTraverse(root.right,action)
action(root.val)
}
}
  • 二叉树中序遍历
1
2
3
4
5
6
7
8
//二叉树中序遍历
function midOrderTraverse(root,action = console.log){
if (root) {
midOrderTraverse(root.left,action)
action(root.val)
midOrderTraverse(root.right,action)
}
}

广度优先遍历

  • 广度优先遍历是从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
    实现: 使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候,执行循环:取出队列的一个节点,如果该结点的左子树为非空,则将该结点的左子树入队列;如果该结点的右子树为非空,则将该结点的右子树入队列。
    (描述有点不清楚,直接看代码吧。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//按层遍历1 两个数组
function levelOrderTraverse(root) {
if (!root) {
return
}

var currRow = [root]
var nextRow = []

while(currRow.length) {
for(var i = 0; i<currRow.length; i++) {
console.log(currRow[i].obj)
currRow[i].left && nextRow.push(currRow[i].left)
currRow[i].right && nextRow.push(currRow[i].right)
}
console.log('--------')
currRow = nextRow
nextRow = []
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//按层遍历2 一个数组
function levelOrderTraverse2(root) {
if (!root) {
return
}

var row = [root]

while(row.length) {
var l = row.length
for(var i = 0; i < l; i++) {
console.log(row[i].obj)
row[i].left && row.push(row[i].left)
row[i].right && row.push(row[i].right)
}
row.splice(0, l)
console.log('--------')
}
}
CATALOG
  1. 1. 深度优先遍历
  2. 2. 广度优先遍历