2025年二叉树的前、中、后序遍历与层序遍历

大家好，我是讯享网，很高兴认识大家。

前言

遍历是二叉树的最重要的操作之一，是二叉树进行其他运算的基础，本文将详细讲解遍历二叉树的常用的四种方式。

一、前序遍历

前序遍历也叫先序遍历，它的遍历顺序是：

根节点——> 根节点的左子树 ——> 根节点的右子树

举个栗子：

讯享网上图中的二叉树，使用前序遍历的结果为：A B D C E F

那么如何把前序遍历转换为代码呢？

前序遍历的顺序是：根→左→右，所以首先应该打印的是根节点

public void preOrder(TreeNode root) { if (root == null) return;//如果节点为空，返回 System.out.print(root.val + " ");//打印根节点 }

讯享网

然后再打印左子树和右子树，但是根节点的左子树和右子树也可以被看作一棵二叉树：

很明显，这是一种递归，转换为代码：

讯享网//前序遍历 public void preOrder(TreeNode root) { if (root == null) return;//如果节点为空，返回 System.out.print(root.val + " ");//打印根节点 preOrder(root.left);//递归打印根的左子树 preOrder(root.right);//递归打印根的右子树 }

把这个递归展开的话就是这样：

对照这张图看方便一点：

图画的有点凌乱，大家不要介意哈~

二、中序遍历

中序遍历的遍历顺序是：

根的左子树——>根——>根的右子树

举个粒子：

上图中的二叉树，使用中序遍历的结果为：D B A E C F

转换为代码：

//中序遍历 void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left);//递归左子树 System.out.print(root.val + " ");//打印 inOrder(root.right);//递归右子树 }

中序遍历逻辑和前序遍历类似，这里就不再画递归展开图了~

三、后序遍历

后序遍历的遍历顺序是：

根的左子树——>根的右子树——>根

举个李子：

上图中的二叉树，使用后序遍历的结果为：D B E F C A

转换为代码：

讯享网//后序遍历 void postOrder(TreeNode root) { if (root == null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.val + " "); }

四、层序遍历

层序遍历的遍历顺序是：

从上到下，从左到右，逐层的遍历。

上图中的二叉树，使用层序遍历的结果为：A B C D E F

要把层序遍历转换为代码，我们需要借助一个队列：

如果二叉树的根不为空，那么就把根放入到队列中：

此时队列不为空，弹出队列顶部元素，如果队列顶部元素的左子树或右子树不为空，那么就把左子树和右子树放入到队列中：

此时队列中有两个元素：B和C，队列不为空，我们继续弹出队列顶部元素，并把队列顶部元素的左右子树放到队列中：

此时队列中有两个元素：C和D，队列不为空，我们继续弹出队列顶部元素，并把队列顶部元素的左右子树放到队列中：

通过这样不断地循环，直到队列内所有元素都被弹出，队列为空时，就停止循环。

这样，我们就实现了从上到下，从左到右，逐层访问每一个节点，即层序遍历。

转换为代码：

//层序遍历 public void levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return;//根节点如果为空，返回 queue.offer(root);//把根节点放入到队列中 while (!queue.isEmpty()){ TreeNode cur = queue.poll();//弹出队列顶部元素 System.out.print(cur.val + " "); if(cur.left != null){ queue.offer(cur.left);//顶部元素的左子树入队 } if(cur.right != null){ queue.offer(cur.right);//顶部元素的右子树入队 } } }

以上就是遍历二叉树的四种方式~

2025年二叉树的前、中、后序遍历与层序遍历

前言

一、前序遍历

二、中序遍历

三、后序遍历

四、层序遍历

相关推荐