关于二叉树的前序、中序、后序三种遍历以及中序遍历的实现

Bertha 。 2021-12-15 01:11 228阅读 0赞

二叉树遍历分为三种：前序、中序、后序，其中序遍历最为重要。为啥叫这个名字？是根据根节点的顺序命名的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODg1NDg4_size_16_color_FFFFFF_t_70]  
比如上图正常的一个满节点，A：根节点、B：左节点、C：右节点，前序顺序是ABC（根节点排最先，然后同级先左后右）；中序顺序是BAC(先左后根最后右）；后序顺序是BCA（先左后右最后根）。

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

比如上图二叉树遍历结果

前序遍历：ABCDEFGHK
    
    中序遍历：BDCAEHGKF
    
    后序遍历：DCBHKGFEA

分析中序遍历如下图，中序比较重要（java很多树排序是基于中序，后面讲解分析）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODg1NDg4_size_16_color_FFFFFF_t_70 2]  
上面的介绍非常清晰,转自：https://blog.csdn.net/qq\_33243189/article/details/80222629  
以下是我对二叉树中序遍历实现：

package com.zgw.collection;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Node2 {
    	private Node2 leftnode;
    	private Node2 rnode;
    	private Object value;
    	
    	private void add(Object i) {
    		if(null==value)
    			value=i;
    		else if((Integer) i -((Integer)value) <= 0){
    			 if (null == leftnode)
    			leftnode= new Node2();
    			leftnode.add(i);
    			 }
    		else{
    			if(null == rnode)
    					rnode= new Node2();
    					rnode.add(i);
    		}}
    	 public List<Object> values() {
    	        List<Object> values = new ArrayList<>();
    	  
    	        // 左节点的遍历结果
    	        if (null != leftnode)
    	            values.addAll(leftnode.values());
    	  
    	        // 当前节点
    	        values.add(value);
    	  
    	        // 右节点的遍历结果
    	        if (null != rnode)
    	  
    	            values.addAll(rnode.values());
    	  
    	        return values;
    	    }
    	 public static void main(String[] args) {
    			int arrs[]= new int []{67, 7, 30, 73, 10, 0, 78, 81, 10, 74};
    			Node2 node = new Node2();
    			for (int number : arrs) {
    				node.add(number);
    	        }
    			 System.out.println(node.values());
    			
    		}
    	 }

代码运行结果  
![在这里插入图片描述][20190704112055382.png]  
**要是还有不太明白的地方请留言，要是对我的文章感兴趣的话，关注一下吧，谢谢！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODg1NDg4_size_16_color_FFFFFF_t_70]: /images/20211214/2c22fa8bdd134523a37e19b90a1dc425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODg1NDg4_size_16_color_FFFFFF_t_70 1]: /images/20211214/08089d8121c24c91a433dff27d24f628.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODg1NDg4_size_16_color_FFFFFF_t_70 2]: /images/20211214/0e4e4edc4a954e25b73eedd582f7bae8.png
[20190704112055382.png]: /images/20211214/06c1bb2a2ca24608beb04d2f9c0bcf13.png