二叉树的遍历总结

二叉树的遍历主要有先序、中序、后序以及层序遍历四种。前三种遍历分别有递归和非递归两种方式,本文总结了这7种遍历的实现。

  • 先序遍历:根节点 -> 左孩子 -> 右孩子
  • 中序遍历:左孩子 -> 根节点 -> 右孩子
  • 后序遍历:左孩子 -> 右孩子 -> 根节点
  • 层序遍历:从上往下逐层访问,每一层从左往右。

递归实现

二叉树的先序、中序、后序的递归实现非常简单,大多数时候采用递归的方式。

先序遍历

1
2
3
4
5
6
7
8
//先序遍历 递归
public static void preOrder(BinaryTreeNode root){
if(root != null){
visit(root);
preOrder_1(root.left);
preOrder_1(root.right);
}
}

中序遍历

1
2
3
4
5
6
7
8
//中序遍历 递归
public static void inOrder(BinaryTreeNode root){
if(root != null){
inOrder(root.left);
visit(root);
inOrder(root.right);
}
}

后序遍历

1
2
3
4
5
6
7
8
//后序遍历 递归
public static void postOrder(BinaryTreeNode root){
if(root != null){
postOrder(root.left);
postOrder(root.right);
visit(root);
}
}

非递归实现

先序遍历

先序遍历的顺序是根节点 -> 左孩子 -> 右孩子,我们需要一个辅组栈来节点。对于一颗二叉树可以分为根节点、左孩子、右孩子三个部分,在左右孩子中可以继续分为根节点、左孩子、右孩子三个部分。对于这三个部分进行以下操作:

  1. 访问当前节点(一开始为根节点),打印输出,并入栈。再看其左孩子是否为空。
  2. 若当前节点的左孩子不为空,则更新当前节点为其左孩子节点,回到1。
  3. 若当前节点的左孩子为空,弹出栈顶元素,更新当前节点为栈顶元素的右孩子,回到1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//先序遍历 非递归
public static void preOrder(BinaryTreeNode root){
if(root == null)
return;
BinaryTreeNode node = root;
Stack<BinaryTreeNode> stack = new Stack();
while(node != null || !stack.isEmpty()){
while(node != null){//一直到最左边节点
visit(node);
stack.push(node);
node = node.left;
}
if(!stack.isEmpty()){
node = stack.pop();
node = node.right;
}
}
}

中序遍历

中序遍历与先序遍历的思路大致相同,按照以下步骤进行:

  1. 将当前节点入栈,再看左孩子是否为空。
  2. 若当前节点的左孩子不为空,则更新当前节点为其左孩子节点,回到1。
  3. 若当前节点的左孩子为空,弹出栈顶元素,并且访问输出,更新当前节点为栈顶元素的右孩子,回到1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//中序遍历 非递归
public static void inOrder(BinaryTreeNode root){
if(root == null)
return;
BinaryTreeNode node = root;
Stack<BinaryTreeNode> stack = new Stack();
while(node != null || !stack.isEmpty()){
while(node != null){//一直到最左边节点
stack.push(node);
node = node.left;
}
if(!stack.isEmpty()){
node = stack.pop();
visit(node);
node = node.right;
}
}
}

后序遍历

后序遍历的非递归实现稍微复杂了一点,由于后序的顺序是左孩子 -> 右孩子 -> 根节点,所以我们需要两次访问根节点:第一次访问根节点用来将其左右孩子入栈;第二次访问根节点输出节点信息。为了判别是第几次访问根节点,我们需要用一个指针来记录上一次访问的节点。如果上一次访问的是左右孩子则这一次将是第二次访问根节点,需要输出节点信息。操作步骤如下:

  1. 根节点入栈。
  2. cur指针指向栈顶元素。
  3. 若cur节点没有孩子节点或者孩子节点都已经被访问过了,则输出当前节点信息,出栈cur元素,用pre指针保存该元素。
  4. 若cur节点有孩子节点且没有访问过,则一次入栈右孩子、左孩子。回到2。
  5. 直到栈空。
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
//后序遍历 非递归
public static void postOrder_2(BinaryTreeNode root){
if(root == null)
return;
Stack<BinaryTreeNode> stack = new Stack();
BinaryTreeNode cur; //当前结点
BinaryTreeNode pre = null; //前一次访问的结点
stack.push(root);
while(!stack.empty()) {
cur=stack.peek();
//如果 当前节点没有孩子节点 || 孩子节点都已经被访问过了
if((cur.left == null && cur.right == null) ||
(pre != null && (pre == cur.left || pre == cur.right))) {
visit(cur);
stack.pop();
pre = cur;
}
else {
//先入栈右孩子再入栈左孩子,这样出栈的顺序才是先左后右
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
}

层序遍历

二叉树的层序遍历是从上到下,从左到右依次访问。采用队列实现,即从上到下、从左到右依次入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void levelOrder(BinaryTreeNode root){
if(root == null)
return;
Queue<BinaryTreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
BinaryTreeNode node = queue.poll();
visit(node);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
}
您的支持将鼓励我继续创作!