总结了一下二叉树的广度优先遍历、深度优先遍历的递归和非递归实现方式。
二叉树的遍历方式：
1、广度优先
按照树的深度，一层一层的访问树的节点
2、深度优先：
1)先序遍历：先访问根节点，再依次访问左子树和右子树
2)中序遍历：先访问左子树，再访问根节点吗，最后访问右子树
3)后序遍历：先访问左子树，再访问右子树，最后访问根节点
1、广度优先遍历
图1是一个二叉树，使用广度优先遍历的顺序应该是1、2、3、4、5、6。
思路是定义一个队列，先将root节点push进去作为初始值，并计算当前层所包含的节点数，root层就为1，将root从列表最前面弹出，然后访问root的left和right，将访问到的节点存入列表中。此时root层遍历结束，列表中存储的是下一层的所有节点，计算当前层所包含的节点数，然后从列表中依次弹出当前层的每个节点，并且访问每个节点的left和right节点，再存入列表中。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var BFS = function(root) {
let a=[];
let tmp;
if(root===null){
return 0;
}
a.push(root);
let count;
while(a.length!==0){
count=a.length;
while(count){
tmp=a.shift();
if(tmp.left!==null){a.push(tmp.left);}
if(tmp.right!==null){a.push(tmp.right);}
count--;
}
}
};
|
2、深度优先遍历
深度优先遍历分为先序遍历、中序遍历和后序遍历。下面每种遍历方式都会使用递归和迭代两种方法。
2.1 先序遍历
图1的二叉树使用深度优先遍历的结果是1、2、4、5、3、6。
迭代的思路是定义一个栈，先将root节点push进去作为初始值，检测栈是否为空，不为空，则弹出最上面的元素将其输出，然后如果该元素有左右节点则，先将右节点入栈，再将左节点入栈。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var DFS= function(root) {
let stack=[];
if(root!==null){
stack.push(root)
while(stack.length!==0){
let top = stack.pop();
console.log(top.val);
if(top.right!==null){
stack.push(top.right);
}
if(top.left!==null){
stack.push(top.left);
}
}
}
};
|
递归的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
var preorderTraversal = function(root) {
let result=[];
DFS(root, result);
return result;
};
function DFS(root,result){
if(root){
result.push(root.val);
DFS(root.left,result);
DFS(root.right,result);
}
}
|
2.2 中序遍历
图1的二叉树使用中序遍历的结果是4、2、5、1、3、6。
迭代的思路是定义一个栈，先将当前节点的所有左侧子结点压入栈，直到指针指向空，然后再一个一个弹出栈中的节点并访问当前节点的右节点（对右节点也是将每个子节点进行入栈）。代码如下：
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
|
var inorderTraversal = function(root) {
let stash=[];
let result=[];
while(stash.length||root){
if(root){
stash.push(root);
root=root.left;
}else{
root = stash.pop();
result.push(root.val);
root=root.right;
}
}
return result;
};
|
递归的代码如下：
1
2
3
4
5
6
7
| var DFS = function(root) {
if(root!==null){
DFS (root.left);
console.log(root.val);
DFS (root.right);
}
};
|
2.3 后序遍历
图1的二叉树使用后序遍历的结果是4、5、2、6、3、1。
迭代思路是定义一个栈，先将当前节点的所有左侧子结点压入栈，现在要保证在访问当前节点的右子结点之后才能访问当前节点。所以每次从栈中拿出左侧节点时，都需要判断该节点的右子树是否存在或右子树是否被访问过，这里使用了一个preNode来记录刚被访问过的节点，这样就可以实现只有当前节点的右子结点访问完成，才能访问当前节点。代码如下：
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
| var DFS = function(root) {
let stack=[];
let node=root;
let preNode=null;
while(node!==null||stack.length!==0){
while(node!==null){
stack.push(node);
node=node.left;
}
if(stack.length!==0){
let tmp = stack[stack.length-1].right;
if(tmp===null||tmp===preNode){
node=stack.pop();
console.log(node.val);
preNode=node;
node=null;
}else{
node=tmp;
}
}
}
};
|
递归的代码如下：
1
2
3
4
5
6
7
| var DFS = function(root) {
if(root!==null){
DFS (root.left);
DFS (root.right);
console.log(root.val);
}
};
|