【算法与数据结构】二叉树的三种遍历代码实现（上）—— 用递归序知识点讲解

朴灿烈づ我的快乐病毒、 2024-03-01 08:12 3阅读 0赞

![815c17f3538c49db8a5e8bc76cb999b3.png][]

本篇博客**（上篇）**先带大家学习**递归方式**进行三种遍历，

而在后续的**（下篇）**中将为大家详细讲解非递归的三种遍历方式。

**目录**

1、二叉树

2、二叉树的递归遍历

2.1、先序遍历

2.2、中序遍历

2.3、后序遍历

![6a9a2fd739a44757a2ce5bc5a0d833cd.gif][]

## 1、二叉树 ##

> 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

![5d8a14ecc534458283f5773ca59de864.png][]

## 2、二叉树的递归遍历 ##

要了解二叉树的递归遍历写法，首先来了解一下**递归序**：

> **递归序**就是按照先序遍历的顺序，遇到的所有结点按顺序排列，重复的结点也必须记录。

![ac3ec3794863457791ace30eddae3485.png][]

> 我们可以发现递归序中每个结点都会遇到三次。
> 
> 这是因为当进入某一结点时，对该结点进行**第一次操作**，然后调用其左孩子结点，等左孩子结点结束调用时会返回自己，此时就可以对自己进行**第二次操作**，然后再调用其右孩子结点，等左孩子结点结束调用时又会返回自己，此时就可以对自己进行**第三次操作，因为不管怎样，调用完孩子结点后终究会返回到父结点。**
> 
> **下面用代码来给大家举例子：**

public static void f(Node head) {
    		//1
    
            //1
    		f(head.left);
            //2
    
            //2
    		f(head.right);
            //3
    
            //3
    	}

> 上面代码中：虽然此时代码中并没有对该节点进行其他操作，但是如果有的话
> 
> 注释1部分就是该结点第一次被操作的时候，
> 
> 注释2部分就是该结点第二次被操作的时候，
> 
> 注释3部分就是该结点第三次被操作的时候。

### 2.1、先序遍历 ###

> 对于所有子树，都是遵循【头左右】的顺序进行操作。
> 
> 例如操作是打印结点，那么就应该先打印头结点，然后在打印左子树的结点，左子树的结点打印依然遵循【头左右】的操作顺序，然后再打印右子树的结点，操作也一样。
> 
> 即**先序遍历**为：1，2，4，5，3，6，7。
> 
> 对于1来说，是先打印了1再到2和3，对于3来说，是先打印了3再到6和7。

![ac3ec3794863457791ace30eddae3485.png][]

> 那么**递归序**在这里有什么用呢？递归序中**第一次**遇到该节点时打印结点，第二次第三次均不做任何操作，这就是**先序遍历**。如下图：

![7a1ba920bd934cc38ae24c24b02a13b8.png][]

> 那么用代码表示就是在**注释1**处增加打印操作即是先序遍历。

public static void preOrderRecur(Node head) {
    		//1
            if (head == null) {
    			return;
    		}
    		System.out.print(head.value + " ");   //在第一次遇到该结点时打印
            //1
    		preOrderRecur(head.left);
            //2
            //2
    		preOrderRecur(head.right);
            //3
            //3
    	}

### 2.2、中序遍历 ###

> 对于所有子树，都是遵循【左头右】的顺序进行操作。
> 
> 例如操作是打印结点，那么就应该先打印头结点的左子树的所有结点，左子树的结点打印依然遵循【左头右】的操作顺序，然后返回到头节点此时对头节点进行打印，然后再打印右子树的结点，操作也一样。
> 
> 即**中序遍历**为：4，2，5，1，6，3，7。
> 
> 对于1来说，是先打印了2再到1然后到3，对于3来说，是先打印了6再到3然后到7。

![ac3ec3794863457791ace30eddae3485.png][]

> 递归序中**第二次**遇到该节点时打印结点，第一次第三次均不做任何操作，这就是**中序遍历**。如下图：

![08852e9df3c34f48bb670caaa4f710b2.png][]

> 那么用代码表示就是在**注释2**处增加打印操作即是中序遍历。

public static void inOrderRecur(Node head) {
            //1
    		if (head == null) {
    			return;
    		}
            //1
    		inOrderRecur(head.left);
            //2
    		System.out.print(head.value + " ");  //在第二次遇到该结点时打印
            //2
    		inOrderRecur(head.right);
            //3
            //3
    	}

### 2.3、后序遍历 ###

> 对于所有子树，都是遵循【左右头】的顺序进行操作。
> 
> 例如操作是打印结点，那么就应该先打印头结点的左子树的所有结点，左子树的结点打印依然遵循【左右头】的操作顺序，返回到头节点不做操作，然后打印右子树的结点，操作也一样。最后返回到头节点此时对头节点进行打印。
> 
> 即**后序遍历**为：4，5，2，6，7，3，1。
> 
> 对于1来说，是先打印了2再到3然后到1，对于3来说，是先打印了6再到7然后到3。

![ac3ec3794863457791ace30eddae3485.png][]

> 递归序中**第三次**遇到该节点时打印结点，第一次第二次均不做任何操作，这就是**后序遍历**。如下图：

![4ab4f1011baa4d11a7a68b2cbc8a7eea.png][]

> 那么用代码表示就是在**注释3**处增加打印操作即是后序遍历。

public static void posOrderRecur(Node head) {
            //1
    		if (head == null) {
    			return;
    		}
            //1
    		posOrderRecur(head.left);
            //2
            //2
    		posOrderRecur(head.right);
            //3
    		System.out.print(head.value + " ");   在第三次遇到该结点时打印
            //3
    	}

![be9b7d1dc5974beeb81140dba04d4ec7.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[815c17f3538c49db8a5e8bc76cb999b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/7074600f7c2a4b52b6d3a5d1857568f8.png
[6a9a2fd739a44757a2ce5bc5a0d833cd.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/c190b8c6608d45cdbe8d8d334e5412f1.png
[5d8a14ecc534458283f5773ca59de864.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/cd25252cdbfa44e8a43d03dbbb04acf1.png
[ac3ec3794863457791ace30eddae3485.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/b0edefe8795d495a85730fa0168bd927.png
[7a1ba920bd934cc38ae24c24b02a13b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/fe25b130e80046e997115420b9918707.png
[08852e9df3c34f48bb670caaa4f710b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/955a18f57b7c4e4abcec15c50297a264.png
[4ab4f1011baa4d11a7a68b2cbc8a7eea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/c747ea79f25c4b4ebd93397c29f9ea0d.png
[be9b7d1dc5974beeb81140dba04d4ec7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/5cf8d914bf3c4467b26fce1f195123f5.png