彻底弄懂二叉树的先序、中序、后序三种遍历与做题方式

彻底弄懂二叉树的先序、中序、后序三种遍历与做题方式

二叉树的遍历是数据结构中的基础知识，也是计算机二级考试中的重点内容。本文将详细讲解二叉树的先序、中序和后序三种遍历方式，并通过实例演示如何根据遍历结果推导二叉树的结构。

二叉树遍历的基本概念

树的遍历是指对树中所有结点信息的访问，即依次对树中每个结点的访问一次且仅访问一次。对于普通的树来说，遍历方式主要包括先序遍历、后序遍历和层次遍历。而对于二叉树来说，除了上述三种遍历方式外，还有一种特殊的中序遍历。

二叉树的遍历可以分为三种：

• 先序遍历（先根遍历）：先访问根节点，然后访问左子树，最后访问右子树。
• 中序遍历（中根遍历）：先访问左子树，然后访问根节点，最后访问右子树。
• 后序遍历（后根遍历）：先访问左子树，然后访问右子树，最后访问根节点。

以一个简单的二叉树为例：

• 先序遍历的顺序：ABC
• 中序遍历的顺序：BAC
• 后序遍历的顺序：BCA

二叉树遍历的实例分析

以一个更复杂的二叉树为例：

这棵树的遍历结果如下：

• 先序遍历：ABDFCEGHI
• 中序遍历：BFDACHGIE
• 后序遍历：FDBHIGECA

先序遍历的分析方法

1. 从根节点A开始，根据先序遍历的原则：首先访问根节点A，然后访问它的左子树B，最后访问右子树C，遍历顺序就是A->B->C
2. 左子树B也按照先序遍历的原则来处理，遍历顺序就是B->D。B的右子树也按照先序遍历的原则，顺序是D->F，就可以得到A->B->D->F->C
3. 右子树C按照先序遍历的原则处理，顺序是C->E，同理C的子树得遍历顺序E->G->H->I
4. 因此，这棵树先序遍历的结果就是：A->B->D->F->C->E->G->H->I

这是递归思路，根据原则遍历子树，子树没了子节点遍历完，则遍历同深度。

中序遍历的分析方法

推导计算，两种遍历序列算出第三种序列。

记住两点：

• 先序/后序遍历可以确定根节点。
• 中序遍历可以确定左子树和右子树。

做这种题就是，反复来回这两点。

题目分析：

由前序遍历知道，A是根节点。
则根据中序遍历 知道HBDF是左子树 EKCG是右子树的
然后在根据前序遍历 BHFD 知道B是左子树的根节点 ，再根据中序遍历知道H是左子树，DF是右子树，同理F是根，D是左子树。
由此也可推出A的右子树的结构
所有整个树的结构是：

因此后序遍历是：HDFBKGCEA