尧图网页设计 
考点频率★★★★★数据结构必考选择题和下午题都常出现难度⭐⭐⭐建议重点掌握三种遍历的递归定义和序列推导理解已知两种遍历序列还原二叉树的方法1️⃣ 什么是二叉树的遍历遍历Traversal是指按照某种顺序访问二叉树中的每个节点恰好一次。打个比方遍历二叉树就像检查一栋楼的每个房间。你从楼长根节点开始要确保每个房间都走到、都看一眼访问而且不能重复走。问题是先检查楼长的房间还是先检查楼下的房间这就是“遍历顺序”的选择。对于二叉树常见的遍历方式有三种遍历方式访问顺序一句话概括前序遍历Preorder根 → 左 → 右“先看自己再看左再看右”中序遍历Inorder左 → 根 → 右“先看左再看自己再看右”后序遍历Postorder左 → 右 → 根“先看左再看右再看自己”这三种遍历方式都是递归定义的——即遍历一棵树就是先处理根节点然后递归遍历左子树和右子树。2️⃣ 三种遍历的递归定义2.1 前序遍历Preorder Traversal访问顺序根节点 → 左子树 → 右子树前序遍历算法伪代码 1. 访问根节点 2. 前序遍历左子树 3. 前序遍历右子树示例1 / \ 2 3 / \ \ 4 5 6 前序遍历结果1 → 2 → 4 → 5 → 3 → 62.2 中序遍历Inorder Traversal访问顺序左子树 → 根节点 → 右子树中序遍历算法伪代码 1. 中序遍历左子树 2. 访问根节点 3. 中序遍历右子树示例同一棵树中序遍历结果4 → 2 → 5 → 1 → 3 → 62.3 后序遍历Postorder Traversal访问顺序左子树 → 右子树 → 根节点后序遍历算法伪代码 1. 后序遍历左子树 2. 后序遍历右子树 3. 访问根节点示例同一棵树后序遍历结果4 → 5 → 2 → 6 → 3 → 13️⃣ 三种遍历结果的对比重要对同一棵树进行三种遍历结果完全不同遍历方式结果序列根节点位置前序1 2 4 5 3 6第一个元素中序4 2 5 1 3 6在左子树和右子树之间后序4 5 2 6 3 1最后一个元素关键规律前序第一个是根后序最后一个是根中序根在中间左边是左子树右边是右子树这个规律是已知两个序列还原二叉树的核心依据。前序定根中序分左右——这是软考中最常考的方法。4️⃣ 经典考法已知两种遍历序列还原二叉树这是软考中的高频难题。给你前序中序或者后序中序让你还原出唯一的二叉树。4.1 已知前序 中序 还原二叉树方法前序序列的第一个元素是根节点在中序序列中找到根节点它左边是左子树的中序序列右边是右子树的中序序列在前序序列中确定左子树和右子树的前序序列按中序序列中的数量划分对左右子树递归执行上述步骤示例已知前序1 2 4 5 3 6中序4 2 5 1 3 6第1步前序第一个 1 → 根节点为 1 第2步中序中 1 的位置 → 左边 [4 2 5] 是左子树右边 [3 6] 是右子树 第3步左子树中序 [4 2 5]前序 [2 4 5]从前序中取与左子树中序相同数量的元素 递归前序 [2 4 5] 的第一个 2 为左子树的根 中序 [4 2 5] 中 2 的位置 → 左边 [4] 是左子树右边 [5] 是右子树 第4步右子树中序 [3 6]前序 [3 6] 递归前序 [3 6] 的第一个 3 为右子树的根 中序 [3 6] 中 3 的位置 → 右边 [6] 是右子树还原结果就是上面那棵树4.2 已知后序 中序 还原二叉树方法后序序列的最后一个元素是根节点在中序序列中找到根节点左边是左子树的中序序列右边是右子树的中序序列在后序序列中确定左子树和右子树的后序序列按中序序列中的数量划分对左右子树递归执行上述步骤示例已知后序4 5 2 6 3 1中序4 2 5 1 3 6第1步后序最后一个 1 → 根节点为 1 第2步中序中 1 的位置 → 左边 [4 2 5] 是左子树右边 [3 6] 是右子树 第3步左子树中序 [4 2 5]后序 [4 5 2]从后序开头取与左子树中序相同数量的元素 递归后序 [4 5 2] 的最后一个 2 为左子树的根 中序 [4 2 5] 中 2 的位置 → 左边 [4] 是左子树右边 [5] 是右子树 第4步右子树中序 [3 6]后序 [6 3] 递归后序 [6 3] 的最后一个 3 为右子树的根 中序 [3 6] 中 3 的位置 → 右边 [6] 是右子树结果相同。4.3 为什么不能只有前序后序前序后序只能确定根节点但无法确定左右子树的分界——因为前序和后序都不像中序那样能明确区分左右子树。因此仅凭前序和后序无法唯一确定一棵二叉树。5️⃣ 经典例题例题1某二叉树的前序遍历序列为A B D E C F中序遍历序列为D B E A F C则该二叉树的后序遍历序列为 。A.D E B F C AB.D E B F C A先推导解析前序第一个A是根中序中A的位置 → 左子树中序D B E右子树中序F C前序剩余B D E C F左子树前序B D E右子树前序C F左子树前序B D E中序D B E根B左子树中序D右子树中序E左子树后序D右子树后序E→ 左子树后序D E B右子树前序C F中序F C根C左子树中序F右子树后序F C整棵树后序 左子树后序 右子树后序 根 D E B F C A答案D E B F C A6️⃣ 记忆口诀前序根左右中序左根右后序左右根。前序定根中序分左右后序定根中序分左右。前序中序能还原后序中序也能还前序后序没法办。7️⃣ 小测验评论区对答案某二叉树的中序遍历序列为B A C后序遍历序列为B C A则该二叉树的前序遍历序列为 。A.A B CB.A C BC.B A CD.C A B本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #二叉树 #前序遍历 #中序遍历 #后序遍历 #数据结构 #软考备考 【数据结构】二叉树的遍历：前序/中序/后序
考点频率★★★★★数据结构必考选择题和下午题都常出现难度⭐⭐⭐建议重点掌握三种遍历的递归定义和序列推导理解已知两种遍历序列还原二叉树的方法1️⃣ 什么是二叉树的遍历遍历Traversal是指按照某种顺序访问二叉树中的每个节点恰好一次。打个比方遍历二叉树就像检查一栋楼的每个房间。你从楼长根节点开始要确保每个房间都走到、都看一眼访问而且不能重复走。问题是先检查楼长的房间还是先检查楼下的房间这就是“遍历顺序”的选择。对于二叉树常见的遍历方式有三种遍历方式访问顺序一句话概括前序遍历Preorder根 → 左 → 右“先看自己再看左再看右”中序遍历Inorder左 → 根 → 右“先看左再看自己再看右”后序遍历Postorder左 → 右 → 根“先看左再看右再看自己”这三种遍历方式都是递归定义的——即遍历一棵树就是先处理根节点然后递归遍历左子树和右子树。2️⃣ 三种遍历的递归定义2.1 前序遍历Preorder Traversal访问顺序根节点 → 左子树 → 右子树前序遍历算法伪代码 1. 访问根节点 2. 前序遍历左子树 3. 前序遍历右子树示例1 / \ 2 3 / \ \ 4 5 6 前序遍历结果1 → 2 → 4 → 5 → 3 → 62.2 中序遍历Inorder Traversal访问顺序左子树 → 根节点 → 右子树中序遍历算法伪代码 1. 中序遍历左子树 2. 访问根节点 3. 中序遍历右子树示例同一棵树中序遍历结果4 → 2 → 5 → 1 → 3 → 62.3 后序遍历Postorder Traversal访问顺序左子树 → 右子树 → 根节点后序遍历算法伪代码 1. 后序遍历左子树 2. 后序遍历右子树 3. 访问根节点示例同一棵树后序遍历结果4 → 5 → 2 → 6 → 3 → 13️⃣ 三种遍历结果的对比重要对同一棵树进行三种遍历结果完全不同遍历方式结果序列根节点位置前序1 2 4 5 3 6第一个元素中序4 2 5 1 3 6在左子树和右子树之间后序4 5 2 6 3 1最后一个元素关键规律前序第一个是根后序最后一个是根中序根在中间左边是左子树右边是右子树这个规律是已知两个序列还原二叉树的核心依据。前序定根中序分左右——这是软考中最常考的方法。4️⃣ 经典考法已知两种遍历序列还原二叉树这是软考中的高频难题。给你前序中序或者后序中序让你还原出唯一的二叉树。4.1 已知前序 中序 还原二叉树方法前序序列的第一个元素是根节点在中序序列中找到根节点它左边是左子树的中序序列右边是右子树的中序序列在前序序列中确定左子树和右子树的前序序列按中序序列中的数量划分对左右子树递归执行上述步骤示例已知前序1 2 4 5 3 6中序4 2 5 1 3 6第1步前序第一个 1 → 根节点为 1 第2步中序中 1 的位置 → 左边 [4 2 5] 是左子树右边 [3 6] 是右子树 第3步左子树中序 [4 2 5]前序 [2 4 5]从前序中取与左子树中序相同数量的元素 递归前序 [2 4 5] 的第一个 2 为左子树的根 中序 [4 2 5] 中 2 的位置 → 左边 [4] 是左子树右边 [5] 是右子树 第4步右子树中序 [3 6]前序 [3 6] 递归前序 [3 6] 的第一个 3 为右子树的根 中序 [3 6] 中 3 的位置 → 右边 [6] 是右子树还原结果就是上面那棵树4.2 已知后序 中序 还原二叉树方法后序序列的最后一个元素是根节点在中序序列中找到根节点左边是左子树的中序序列右边是右子树的中序序列在后序序列中确定左子树和右子树的后序序列按中序序列中的数量划分对左右子树递归执行上述步骤示例已知后序4 5 2 6 3 1中序4 2 5 1 3 6第1步后序最后一个 1 → 根节点为 1 第2步中序中 1 的位置 → 左边 [4 2 5] 是左子树右边 [3 6] 是右子树 第3步左子树中序 [4 2 5]后序 [4 5 2]从后序开头取与左子树中序相同数量的元素 递归后序 [4 5 2] 的最后一个 2 为左子树的根 中序 [4 2 5] 中 2 的位置 → 左边 [4] 是左子树右边 [5] 是右子树 第4步右子树中序 [3 6]后序 [6 3] 递归后序 [6 3] 的最后一个 3 为右子树的根 中序 [3 6] 中 3 的位置 → 右边 [6] 是右子树结果相同。4.3 为什么不能只有前序后序前序后序只能确定根节点但无法确定左右子树的分界——因为前序和后序都不像中序那样能明确区分左右子树。因此仅凭前序和后序无法唯一确定一棵二叉树。5️⃣ 经典例题例题1某二叉树的前序遍历序列为A B D E C F中序遍历序列为D B E A F C则该二叉树的后序遍历序列为 。A.D E B F C AB.D E B F C A先推导解析前序第一个A是根中序中A的位置 → 左子树中序D B E右子树中序F C前序剩余B D E C F左子树前序B D E右子树前序C F左子树前序B D E中序D B E根B左子树中序D右子树中序E左子树后序D右子树后序E→ 左子树后序D E B右子树前序C F中序F C根C左子树中序F右子树后序F C整棵树后序 左子树后序 右子树后序 根 D E B F C A答案D E B F C A6️⃣ 记忆口诀前序根左右中序左根右后序左右根。前序定根中序分左右后序定根中序分左右。前序中序能还原后序中序也能还前序后序没法办。7️⃣ 小测验评论区对答案某二叉树的中序遍历序列为B A C后序遍历序列为B C A则该二叉树的前序遍历序列为 。A.A B CB.A C BC.B A CD.C A B本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #二叉树 #前序遍历 #中序遍历 #后序遍历 #数据结构 #软考备考