二叉树遍历

发表于

深度优先遍历（递归遍历）

觉得用这几个字母表示递归遍历的三种方法不错：

D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。

先序遍历：DLR

中序遍历：LDR

后序遍历：LRD

这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总
是优先往深处访问。

先序遍历
1
2
3
4
5
6
7
var preOrder = function (node) {
	if (node) { 
  		console.log(node.value);
  		preOrder(node.left); 
 		preOrder(node.right); 
  	}
}
中序遍历
1
2
3
4
5
6
7
var inOrder = function (node) { 
	if (node) { 
 		inOrder(node.left); 
 		console.log(node.value);
 		inOrder(node.right); 
 	} 
}
后序遍历
1
2
3
4
5
6
7
var postOrder = function (node) { 
	if (node) { 
		postOrder(node.left); 
		postOrder(node.right); 
		console.log(node.value);
	} 
}
先序遍历

广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
var levelOrderTraversal = function(node) { 
	if(!node) { 
		throw new Error('Empty Tree') 
	} 
	var que = [] 
	que.push(node) 
	while(que.length !== 0) { 
		node = que.shift() 
		console.log(node.value) 
		if(node.left) que.push(node.left)
		if(node.right) que.push(node.right) 
	}
}
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var inOrderUnRecur = function (node) {
    if (!node) {
        throw new Error('Empty Tree')
    }
    var 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
19
var posOrderUnRecur = function (node) {
    if (!node) {
        throw new Error('Empty Tree')
    }
    var stack = []
    stack.push(node)
    var tmp = null
    while (stack.length !== 0) {
        tmp = stack[stack.length - 1]
        if (tmp.left && node !== tmp.left && node !== tmp.right) {
            stack.push(tmp.left)
        } else if (tmp.right && node !== tmp.right) {
            stack.push(tmp.right)
        } else {
            console.log(stack.pop().value)
            node = tmp
        }
    }
}