二叉树(先序遍历，中序遍历，后序遍历)

悠悠 2021-10-01 09:18 460阅读 0赞

# 二叉树定义 #

每个节点的子节点数(度)不能大于2

# 先序遍历 #

*  定义：从二叉树的根结点出发，当**第一次到达结点时就输出结点数据**，按照先向左在向右的方向访问。  
    
    
    ![7043118-df454c0a574836de.png][]
    
    image
    
      
    以上先序遍历输出的即如果为：ABDHIEJCFG  
    访问顺序为：

> 从根结点出发，则第一次到达结点A，故输出A;  
> 继续向左访问，第一次访问结点B，故输出B；  
> 按照同样规则，输出D，输出H；  
> 当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；  
> I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；  
> 向E左子树，故输出J；  
> 按照同样的访问规则，继续输出C、F、G；

# 中序遍历 #

*  定义：从二叉树的根结点出发，当**第二次到达结点时就输出结点数据**，按照先向左在向右的方向访问。  
    中序遍历上图的输出结果是：HDIBJEAFCG  
    访问顺序

> 先访问A节点，因为是第一次访问所以不输出，再访问左子节点到B，因为左子节点不为空，再访问左子节点到D，再访问D的左子节点H，因为H为叶子节点，直接输出H， -----> H  
> 然后返回D，到D是第二次访问了，直接输出D， -----> HD  
> 然后再访问右子节点I，右子节点是叶子节点，所以直接输出I ----->HDI  
> ...

# 后序遍历 #

*  定义：从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问  
    后序遍历输出结果是:HIDJEBFGCA  
    访问顺序

> 从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；  
> 到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；  
> H右子树为空，则返回至H，此时第三次到达H，故输出H；  
> 由H返回至D，第二次到达D，不输出D；  
> 继续访问至I，I左右子树均为空，故第三次访问I时，输出I；  
> 返回至D，此时第三次到达D，故输出D；  
> 按照同样规则继续访问，输出J、E、B、F、G、C，A；

作者：MrHorse1992  
链接：[https://www.jianshu.com/p/bf73c8d50dc2][https_www.jianshu.com_p_bf73c8d50dc2]

[7043118-df454c0a574836de.png]: /images/20210825/0659715f09a04adf9d0bd8e7a151c3d5.png
[https_www.jianshu.com_p_bf73c8d50dc2]: https://www.jianshu.com/p/bf73c8d50dc2