# 结构定义
class TreeNode{
int val;
TreeNode left;171
TreeNode right;
TreeNode(int val){
this.val = val;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 非递归遍历
# 层次遍历
借助队列实现层次遍历,树可以看成图,层次遍历其实也是BFS遍历。
public void levelOrder(TreeNode root){
if(root == null)
return;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.remove();
System.out.println(t.val + " ");
if(t.left != null)
queue.add(t.left);
if(t.right != null)
queue.add(t.right);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 前序遍历
借助栈和指针p实现树的前序遍历。
算法流程
- 将根放入栈中,一直向左子树走
- 若走到了尽头,出栈,向右走一步
- 重复1-2步
public void preOrder(TreeNode root){
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
// 当栈不为空或者p不为空时继续循环
while(!stack.isEmpty() || p != null){
if(p != null){
stack.push(p);
System.out.print(p.val + " ");
p = p.left; // 一直往左子树走,直到p为空
}else{
p = stack.pop(); // 当p为空,出栈,往右子树走
p = p.right;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 中序遍历
和前序遍历相同,只是访问的位置变了而已。
public void inOrder(TreeNode root){
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.pop();
System.out.print(p.val + " "); // 在此处访问
p = p.right;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 后序遍历
因为后序遍历二叉树的顺序是先访问左子树,再访问右子树,最后访问根结点,因此要分清楚返回根结点时,是从左子树返回还是右子树返回的。
- 若从左子树返回,此时右子树没有访问,不出栈,访问其右子树
- 若从右子树返回,直接将根结点出栈
算法流程
- 将根放入栈中,一直向左子树走
- 当走到头时,若处在栈顶的结点的右子树
- 不为空并且没有访问过,向右走一步
- 为空或者访问过了,出栈,标记访问,用r记录p,同时置p为null
public void postOrder(TreeNode root){
TreeNode p = root;
TreeNode r = null;
Deque<TreeNode> stack = new LinkedList<>();
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.peek();
if(p.right != null && p.right != r){
p = p.right;
}else{
p = stack.pop();
System.out.print(p.val + " ");
r = p;
p = null;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22