二叉树遍历(递归实现前序/中序/后序遍历)

你的名字 2022-10-07 08:56 159阅读 0赞

#### 1. 准备工作 ####

我们先定义一棵普通的二叉树，如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center]

#### 2. 前序遍历 ####

通过递归进行遍历：  
如果二叉树为空，则操作返回；  
如果非空，否则从根结点开始，然后遍历左子树，再遍历右子树。

前序遍历的结果是：`ABDGHEICFJK`

为什么会遍历出这种结果，请看上面对前序遍历的描述：先遍历左边，然后在遍历右边。

JAVA代码如下：

//前序遍历	
    public static void preTraversal(Node node){
    		if(null!=node){
    			System.out.println(node.getData());
    			preTraversal(node.getLeft());
    			preTraversal(node.getRight());
    			return;
    		}
    	}

#### 3. 中序遍历 ####

通过递归进行遍历：  
如果二叉树为空，则操作返回；  
如果非空，否则从根结点开始，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

前序遍历的结果是： `GDHBEIACJFK`

为什么会遍历出这种结果，请看上面对中序遍历的描述：先遍历左边，然后访问根结点，然后在遍历右边。

JAVA代码如下：

//中序遍历	
    public static void inOrder(Node node){
    		if(null!=node){
    			inOrder(node.getLeft());
    			System.out.println(node.getData());
    			inOrder(node.getRight());
    			return;
    		}
    	}

#### 4. 后序遍历 ####

通过递归进行遍历：  
如果二叉树为空，则操作返回；  
如果非空，否则从左到右，先访问左右子树，再访问右子树，最后访问根结点。

前序遍历的结果是： `GHDIEBJKFCA`

为什么会遍历出这种结果，请看上面对中序遍历的描述：从左到右，先叶子，后结点。

JAVA代码如下：

//后序遍历	
    public static void postOrder(Node node){
    		if(null!=node){
    			postOrder(node.getLeft());
    			postOrder(node.getRight());
    			System.out.println(node.getData());
    			return;
    		}
    	}

#### 5. 总结 ####

以上就是二叉树的其中三种遍历方式，其中的差异性就在于递归调用的时候，对某个结点进行操作。

例如前序遍历，每次递归调用，都是先打印结点的data信息，然后是访问左叶子结点信息，又是打印结点信息，直到没有左叶子的时候，返回上层结点，然后调用右叶子，如此递归，就会出现前序遍历的结果。

中序/后序跟前序原理差不多吗，不同的在于什么时候打印结点信息而已。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/9bf68e2099b248cbb206d74912e24aff.png