二叉树后序遍历（递归+非递归）Java

我不是女神ヾ 2023-05-31 12:21 9阅读 0赞

### 目录 ###

*  一、结构
 *  二、遍历二叉树
 *   *  1.后序遍历（递归）
     *   *  代码
         *  图解
     *  2.后序遍历（非递归）
     *   *  代码
         *  图解

--------------------

# 一、结构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]

# 二、遍历二叉树 #

这块内容是二叉树最核心的部分。不但要掌握七种遍历的写法，前、中、后序的递归、非递归写法+层次遍历，还有学会（1）用前、中、后序遍历数组创建二叉树；（2）用一维数组存储二叉树。

## 1.后序遍历（递归） ##

前序遍历访问节点的顺序是 左儿子-右儿子-根节点。

### 代码 ###

public void postOrderRecur(Node root) {
        
    		if (root == null) {
        
    			return;
    		}
    		postOrderRecur(root.left);
    		postOrderRecur(root.right);
    		System.out.print(root.data + " -> ");
    	}

注意：这个代码是不是很眼熟呢？其实就是把前序或中序遍历中的一行代码换了个位置。

### 图解 ###

初始。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 1]  
第一步：  
（1）执行postOrderRecur（Node root）方法，root不为null，于是调用postOrderRecur（root.left）方法，访问节点B；  
（2）B不为空，继续调用postOrderRecur（B.left）方法，访问节点D；  
（3）D不为空，调用postOrderRecur（D.left）方法，D.left为空，返回；  
（4）调用postOrderRecur（D.right）方法，访问节点H；  
（5）H不为空，调用postOrderRecur（H.left）方法，H.left为空，返回；  
（6）调用postOrderRecur（H.right）方法，H.right为空，返回；  
（7）打印“H”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 2]  
第二步：  
（1）打印“H”的语句执行完后，其所在的方法结束，返回上一级方法；  
（2）打印“D”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 3]  
第三步：  
（1）打印“D”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）调用postOrderRecur（B.right）方法，访问节点E；  
（3）递归调用postOrderRecur（E.left）方法，访问节点I；  
（4）递归调用postOrderRecur（I.left）方法，I.left为空，返回；  
（5）递归调用postOrderRecur（I.right）方法，H.right为空，返回；  
（6）打印“I”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 4]  
第四步：  
（1）打印“I”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）调用postOrderRecur（E.right）方法，访问节点J；  
（3）递归调用postOrderRecur（J.left）方法，J.left为空，返回；  
（4）递归调用postOrderRecur（J.right）方法，J.right为空，返回；  
（5）打印“J”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 5]  
第五步：  
（1）打印“J”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）打印“E”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 6]  
第六步：  
（1）打印“E”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）打印“B”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 7]  
第七步：  
（1）打印“E”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）调用postOrderRecur（A.right）方法，访问节点C；  
（3）递归调用postOrderRecur（C.left）方法，访问节点F；  
（4）递归调用postOrderRecur（F.left）方法，F.left为空，返回；  
（5）递归调用postOrderRecur（F.right）方法，F.right为空，返回；  
（6）打印“F”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 8]  
第八步：  
（1）打印“F”的语句执行完后，其所在的方法结束，返回到上一级方法；  
（2）调用postOrderRecur（C.right）方法，访问节点G；  
（3）递归调用postOrderRecur（G.left）方法，G.left为空，返回；  
（4）递归调用postOrderRecur（G.right）方法，G.right为空，返回；  
（5）打印“G”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 9]  
第九步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 10]  
第十步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 11]  
打印顺序：**HDIJEBFGCA**

## 2.后序遍历（非递归） ##

### 代码 ###

要实现访问顺序为左儿子-右儿子-根节点，可以利用后进先出的栈，在节点不为空的情况下，依次将根节点、右儿子、左儿子压入一个栈中，最后一起打印栈中的元素。

public void postOrder() {
        
    		Node current = root;
    		//就是图中的S1，把LinkedList作为栈使用
    		LinkedList<Node> s1 = new LinkedList<Node>();
    		//就是图中的S2，把LinkedList作为栈使用
    		LinkedList<Node> s2 = new LinkedList<Node>();
    		while (current != null || !s1.isEmpty()) {
        
    			while (current != null) {
        
    				s1.addFirst(current);
    				s2.addFirst(current);
    				current = current.right;
    			}
    			if (!s1.isEmpty()) {
        
    				current = s1.removeFirst();
    				current = current.left;
    			}
    		}
    		while (!s2.isEmpty()) {
        
    			System.out.print(s2.removeFirst().data + " -> ");
    		}
    	}

### 图解 ###

初始。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 1]  
图一：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 12]  
图二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 13]  
图三：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 14]  
图四：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 15]  
图五：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 16]  
图六：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 17]  
图七：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 18]  
图八：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 19]  
图九：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 20]  
图十：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 21]  
图十一：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 22]  
最后再从栈S2取出元素，得到打印顺序为**HDIJEBFGCA**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]: /images/20230531/251fdb8ae83a42e184791bceb95948ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 1]: /images/20230531/d1f6f986c666443a91ff3b9541d76123.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 2]: /images/20230531/807b75878c9d41fbb29e927762edfd65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 3]: /images/20230531/db8630aecd9e4275a71b851a258124f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 4]: /images/20230531/6c82baf114f74217818c87835ba204b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 5]: /images/20230531/392c0d93c3c94682b5f8b705f59ae5dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 6]: /images/20230531/4c2c9c74e1dc4b9ca15a8d4c20e1b1ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 7]: /images/20230531/aad08fa68a0c4db48360d656475e8695.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 8]: /images/20230531/3e3c6e6e14554f4d9169ee14625026c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 9]: /images/20230531/bdf63c63e9ce41da9c9f7726d19197f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 10]: /images/20230531/3e5f932b2ed1425f9a92343972267366.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 11]: /images/20230531/4a465c274c744551b5d95dcfba5013f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 12]: /images/20230531/02a04b96770444838d6cefbc9d04c94f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 13]: /images/20230531/db7072f58ae14ad983043898879ad75c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 14]: /images/20230531/90ff61b348724f77b27d5946e85b8765.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 15]: /images/20230531/942445fafcbb48c59915954d9b9c92e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 16]: /images/20230531/f1db84c25be648b298721602f7524f99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 17]: /images/20230531/ef7aeec13e8644db8697858286b78f4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 18]: /images/20230531/9ae700f5c8954becb4488be2447b06e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 19]: /images/20230531/c68e188f622746979fd0ee38cf2e72f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 20]: /images/20230531/ca5d99130c5e415b9b07e19bf4459609.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 21]: /images/20230531/8a8c9079214b40af93b4a0dc33e93d67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 22]: /images/20230531/f7f10b13582f4decb0d449c94430e7b8.png