树的先序、中序和后序遍历知识点讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

 研究生考试中，树的遍历几乎是考试的必考知识点，几乎所有的树相关的算法都需要对树进行遍历。本篇文章主要讲解树的先序遍历，中序遍历和后续遍历中的一个知识点。

一、基础知识

先序遍历、中序遍历、后序遍历中的先、中、后表示的是根结点遍历的顺序。先序遍历就是，先遍历根节点，然后后遍历该根节点的左子树，最后遍历该根节点的右子树。其他两种遍历方式以此类推。需要注意的是，三种遍历都是可以以递归的方式进行遍历，这一点很重要。

对于二叉树来说

先序遍历==》根结点，左子树，右子树；

中序遍历==》左子树，根结点，右子树；

后续遍历==》左子树，右子树，根结点；

按照其递归的思想，子树的遍历也是按照这一顺序来进行遍历的。

例子（以先序遍历为例）：

有如下二叉树图1

按照先序遍历==》根结点，左子树，右子树；

   先不管左右子树的确切顺序，整个左/右子树的相对顺序是确定的。

中序遍历、后序遍历同理；树的遍历同理。

二、真题分析

896-2015年选择题第5题：

如果一棵树的先根遍历序列为ABCDE，后根遍历序列为BDCEA，则这课树的根节点的孩子结点树目为（）。

解题思路：

2.1 思路1

利用树和二叉树的对应关系。树的先序和后续对应二叉树的先序和中序。二叉树的是先序和中序是可以唯一获取到具体的二叉树的，二叉树再转换回树，最后可以知道根节点存在几个子节点；

2.2 思路2

本文重点解释另外一种方法，根据根节点及其子树的遍历顺序来进行确实根结点有几个孩子结点。

与上诉二叉树所述一样，树的先序遍历、中序遍历和后续遍历如下，

先序遍历==》根结点，子树1，子树2，子树3，…，子树x；

中序遍历==》子树1，子树2，子树3，…子树j，根结点，子树j+1…子树x；

后续遍历==》子树1，子树2，子树3，…，子树x，根结点；

根据该题目中，可以知道

先序为：A，子树1，子树2，…，子树x

后序为：子树1，子树2，…，子树x，A

对于子树1来说，从先序来看，其根为B，从后序来看，子树1（以B为结尾）中只有B结点一个。对于子树2来说，从先序来看，其根为C，从后序来看，子树2中有DC两个结点。同理，子树三的根为E，存在E一个结点，综上所述，A结点有3个子树，也就有3个子结点。

三、总结

无论是二叉树，还是树，也可能是森林。其先序遍历，都是先遍历根节点，然后再依次先序遍历根结点的子树。体现到结果上是，根结点、第一棵子树、第二棵子树…。中序遍历和后序遍历同理。