非递归遍历二叉树

实现非递归遍历二叉树的原理就是使用栈来模拟递归的情况。


假设有如下二叉树:

期望:

广度优先遍历的序列:-+/a*efb-cd

深度优先遍历:

  • 先序遍历的序列是:-+a*b-cd/ef
  • 中序遍历的序列是:a+b*c-d-e/f
  • 后序遍历的序列是:abcd-*+ef/-

对象形式:

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
const tree = {
value: '-',
left: {
value: '+',
left: {
value: 'a'
},
right: {
value: '*',
left: {
value: 'b'
},
right: {
value: '-',
left: {
value: 'c'
},
right: {
value: 'd'
}
}
}
},
right: {
value: '/',
left: {
value: 'e'
},
right: {
value: 'f'
}
}
}

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
const breadthFirstTraversal = function (node) {
if (node) {
const stack = []
stack.push(node)
while (stack.length !== 0) {
node = stack.shift()
console.log(node.value)
if (node.left) stack.push(node.left)
if (node.right) stack.push(node.right)
}
}
}

深度优先遍历

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
const preOrderTraversal = function (node) {
if (node) {
const stack = []
stack.push(node)
while(stack.length !== 0) {
node = stack.pop()
console.log(node.value)
if(node.right) stack.push(node.right)
if(node.left) stack.push(node.left)
}
}
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const inOrderTraversal = function (node) {
if (node) {
const stack = []
while (stack.length !== 0 || node) {
if (node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
console.log(node.value)
node = node.right
}
}
}
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const postOrderTraversal= function (node) {
if(node) {
const stack = []
stack.push(node)
let temp = null
while (stack.length !== 0) {
temp = stack[stack.length - 1]
if (temp.left && node !== temp.left && node !== temp.right) {
stack.push(temp.left)
} else if (temp.right && node !== temp.right) {
stack.push(temp.right)
} else {
console.log(stack.pop().value)
node = temp
}
}
}
}