二叉树前序或中序或后序遍历

二叉树知识点总结1. 二叉树的性质1.1 二叉树的性质一：二叉树的深度二叉树的深度是指从根节点到叶子节点的最长路径长度。

对于一个空树而言，它的深度为0；对于只有一个根节点的树而言，它的深度为1。

根据定义可知，深度为k的二叉树中，叶子节点的深度值为k。

由此可知，二叉树的深度为所有叶子节点深度的最大值。

1.2 二叉树的性质二：二叉树的高度二叉树的高度是指从根节点到叶子节点的最短路径长度。

对于一个空树而言，它的高度为0；对于只有一个根节点的树而言，它的高度为1。

由此可知，二叉树的高度总是比深度大一。

1.3 二叉树的性质三：二叉树的节点数量对于一个深度为k的二叉树而言，它最多包含2^k - 1个节点。

而对于一个拥有n个节点的二叉树而言，它的深度最多为log2(n+1)。

1.4 二叉树的性质四：满二叉树满二叉树是一种特殊类型的二叉树，它的每个节点要么是叶子节点，要么拥有两个子节点。

满二叉树的性质是：对于深度为k的满二叉树而言，它的节点数量一定是2^k - 1。

1.5 二叉树的性质五：完全二叉树完全二叉树是一种特殊类型的二叉树，它的所有叶子节点都集中在树的最低两层，并且最后一层的叶子节点从左到右依次排列。

对于一个深度为k的完全二叉树而言，它的节点数量一定在2^(k-1)和2^k之间。

2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。

二叉树的遍历主要包括前序遍历、中序遍历和后序遍历三种。

2.1 前序遍历（Pre-order traversal）前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

对于一个二叉树而言，前序遍历的结果就是按照“根-左-右”的顺序访问所有节点。

2.2 中序遍历（In-order traversal）中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

对于一个二叉树而言，中序遍历的结果就是按照“左-根-右”的顺序访问所有节点。

2.3 后序遍历（Post-order traversal）后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

二叉树,树,森林遍历之间的对应关系一、引言在计算机科学中，数据结构是非常重要的知识点之一。

而树这一数据结构，作为基础的数据结构之一，在软件开发中有着广泛的应用。

本文将重点探讨二叉树、树和森林遍历之间的对应关系，帮助读者更加全面地理解这些概念。

二、二叉树1. 二叉树的定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空，也可以是一棵空树。

2. 二叉树的遍历在二叉树中，有三种常见的遍历方式，分别是前序遍历、中序遍历和后序遍历。

在前序遍历中，节点的访问顺序是根节点、左子树、右子树；在中序遍历中，节点的访问顺序是左子树、根节点、右子树；在后序遍历中，节点的访问顺序是左子树、右子树、根节点。

3. 二叉树的应用二叉树在计算机科学领域有着广泛的应用，例如用于构建文件系统、在数据库中存储有序数据、实现算法中的搜索和排序等。

掌握二叉树的遍历方式对于理解这些应用场景非常重要。

三、树1. 树的定义树是一种抽象数据类型，由n(n>0)个节点组成一个具有层次关系的集合。

树的特点是每个节点都有零个或多个子节点，而这些子节点又构成了一颗子树。

树中最顶层的节点称为根节点。

2. 树的遍历树的遍历方式有先根遍历、后根遍历和层次遍历。

在先根遍历中，节点的访问顺序是根节点、子树1、子树2...；在后根遍历中，节点的访问顺序是子树1、子树2...，根节点；在层次遍历中，节点的访问顺序是从上到下、从左到右依次访问每个节点。

3. 树的应用树广泛用于分层数据的表示和操作，例如在计算机网络中的路由算法、在操作系统中的文件系统、在程序设计中的树形结构等。

树的遍历方式对于处理这些应用来说至关重要。

四、森林1. 森林的定义森林是n(n>=0)棵互不相交的树的集合。

每棵树都是一颗独立的树，不存在交集。

2. 森林的遍历森林的遍历方式是树的遍历方式的超集，对森林进行遍历就是对每棵树进行遍历的集合。

3. 森林的应用森林在实际编程中经常用于解决多个独立树结构的问题，例如在数据库中对多个表进行操作、在图像处理中对多个图形进行处理等。

⼆叉树遍历（前序、中序、后序、层次、⼴度优先、深度优先遍历）⽬录转载：⼆叉树概念⼆叉树是⼀种⾮常重要的数据结构，⾮常多其他数据结构都是基于⼆叉树的基础演变⽽来的。

对于⼆叉树，有深度遍历和⼴度遍历，深度遍历有前序、中序以及后序三种遍历⽅法，⼴度遍历即我们寻常所说的层次遍历。

由于树的定义本⾝就是递归定义，因此採⽤递归的⽅法去实现树的三种遍历不仅easy理解并且代码⾮常简洁，⽽对于⼴度遍历来说，须要其他数据结构的⽀撑。

⽐⽅堆了。

所以。

对于⼀段代码来说，可读性有时候要⽐代码本⾝的效率要重要的多。

四种基本的遍历思想前序遍历：根结点 ---> 左⼦树 ---> 右⼦树中序遍历：左⼦树---> 根结点 ---> 右⼦树后序遍历：左⼦树 ---> 右⼦树 ---> 根结点层次遍历：仅仅需按层次遍历就可以⽐如。

求以下⼆叉树的各种遍历前序遍历：1 2 4 5 7 8 3 6中序遍历：4 2 7 5 8 1 3 6后序遍历：4 7 8 5 2 6 3 1层次遍历：1 2 3 4 5 6 7 8⼀、前序遍历1）依据上⽂提到的遍历思路：根结点 ---> 左⼦树 ---> 右⼦树，⾮常easy写出递归版本号：public void preOrderTraverse1(TreeNode root) {if (root != null) {System.out.print(root.val+" ");preOrderTraverse1(root.left);preOrderTraverse1(root.right);}}2）如今讨论⾮递归的版本号：依据前序遍历的顺序，优先訪问根结点。

然后在訪问左⼦树和右⼦树。

所以。

对于随意结点node。

第⼀部分即直接訪问之，之后在推断左⼦树是否为空，不为空时即反复上⾯的步骤，直到其为空。

若为空。

则须要訪问右⼦树。

注意。

在訪问过左孩⼦之后。

第5章树和二叉树一、填空题1、指向结点前驱和后继的指针称为线索。

二、判断题1、二叉树是树的特殊形式。

（）2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。

（）3、对于有N个结点的二叉树，其高度为。

（）4、满二叉树一定是完全二叉树，反之未必。

（）5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。

（）6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

（）7、不使用递归也可实现二叉树的先序、中序和后序遍历。

（）8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。

（）9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

（）110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。

（）三、单项选择题1、把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2、由3个结点可以构造出多少种不同的二叉树？（D）A．2 B．3 C．4 D．5解释：五种情况如下：3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（D）。

A．250 B． 500 C．254 D．501解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

4、一个具有1025个结点的二叉树的高h为（C）。

A．11 B．10 C．11至1025之间 D．10至1024之间解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h在11至1025之间。

二叉树基本知识：
1.二叉树的定义：二叉树是每个结点最多有两个子树的树结构，它有五种基本形态：
二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

2.二叉树的性质：若规定根结点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)
(i>0)个结点。

若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结
点数是2^K -1 (k >= 0)个。

对任何一颗二叉树，如果其叶子结点个数为n0，度为2的非叶子结点个数为n2，则有n0=n2+1。

3.二叉树的分类：二叉树有两大类，一是普通二叉树，二是特殊二叉树。

普通二叉树
是指除了满二叉树和完全二叉树之外的二叉树，特殊二叉树包括满二叉树和完全二叉树。

满二叉树是指所有层都完全填满的二叉树，而完全二叉树是指只有最下面两层结点度数可以小于2，并且最下面一层的叶子结点都位于本层中间位置的二叉树。

4.二叉树的遍历：二叉树的遍历主要有三种方法，分别是前序遍历、中序遍历和后序
遍历。

前序遍历是先访问根结点，然后遍历左子树，最后遍历右子树；中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根结点。

⼆叉树遍历（前中后序遍历，三种⽅式）⽬录刷题中碰到⼆叉树的遍历，就查找了⼆叉树遍历的⼏种思路，在此做个总结。

对应的LeetCode题⽬如下：，，，接下来以前序遍历来说明三种解法的思想，后⾯中序和后续直接给出代码。

⾸先定义⼆叉树的数据结构如下：//Definition for a binary tree node.struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};前序遍历，顺序是“根-左-右”。

使⽤递归实现：递归的思想很简单就是我们每次访问根节点后就递归访问其左节点，左节点访问结束后再递归的访问右节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;helper(root,res);return res;}void helper(TreeNode *root, vector<int> &res){res.push_back(root->val);if(root->left) helper(root->left, res);if(root->right) helper(root->right, res);}};使⽤辅助栈迭代实现：算法为：先把根节点push到辅助栈中，然后循环检测栈是否为空，若不空，则取出栈顶元素，保存值到vector中，之后由于需要想访问左⼦节点，所以我们在将根节点的⼦节点⼊栈时要先经右节点⼊栈，再将左节点⼊栈，这样出栈时就会先判断左⼦节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;stack<TreeNode*> st;st.push(root);while(!st.empty()){//将根节点出栈放⼊结果集中TreeNode *t = st.top();st.pop();res.push_back(t->val);//先⼊栈右节点，后左节点if(t->right) st.push(t->right);if(t->left) st.push(t->left);}return res;}};Morris Traversal⽅法具体的详细解释可以参考如下链接：这种解法可以实现O(N)的时间复杂度和O(1)的空间复杂度。

前序后序中序详细讲解1.引言1.1 概述在数据结构与算法中，前序、中序和后序是遍历二叉树的三种基本方式之一。

它们是一种递归和迭代算法，用于按照特定的顺序访问二叉树的所有节点。

通过遍历二叉树，我们可以获取有关树的结构和节点之间关系的重要信息。

前序遍历是指先访问根节点，然后递归地访问左子树，最后递归地访问右子树。

中序遍历是指先递归地访问左子树，然后访问根节点，最后递归地访问右子树。

后序遍历是指先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

它们的不同之处在于访问根节点的时机不同。

前序遍历可以帮助我们构建二叉树的镜像，查找特定节点，或者获取树的深度等信息。

中序遍历可以帮助我们按照节点的大小顺序输出树的节点，或者查找二叉搜索树中的某个节点。

后序遍历常用于删除二叉树或者释放二叉树的内存空间。

在实际应用中，前序、中序和后序遍历算法有着广泛的应用。

它们可以用于解决树相关的问题，例如在Web开发中，树结构的遍历算法可以用于生成网页导航栏或者搜索树结构中的某个节点。

在图像处理中，前序遍历可以用于图像压缩或者图像识别。

另外，前序和后序遍历算法还可以用于表达式求值和编译原理中的语法分析等领域。

综上所述，前序、中序和后序遍历算法是遍历二叉树的重要方式，它们在解决各种与树有关的问题中扮演着关键的角色。

通过深入理解和应用这些遍历算法，我们可以更好地理解和利用二叉树的结构特性，并且能够解决更加复杂的问题。

1.2文章结构文章结构是指文章中各个部分的布局和组织方式。

一个良好的文章结构可以使读者更好地理解和理解文章的内容。

本文将详细讲解前序、中序和后序三个部分的内容和应用。

首先，本文将在引言部分概述整篇文章的内容，并介绍文章的结构和目的。

接下来，正文部分将分为三个小节，分别对前序、中序和后序进行详细讲解。

在前序讲解部分，我们将定义和解释前序的意义，并介绍前序在实际应用中的场景。

通过详细的解释和实例，读者将能更好地理解前序的概念和用途。

前序序列和后续序列确定⼆叉树⼆叉树：已知前序与后序建树那么我们换⼀种思考⽅式，我们先来看看先序与后序序列的排布规律。

以下⾯这棵树来举例：其先序序列为： 1 2 3 4 6 7 5后序序列为：2 6 7 4 5 3 1⾸先我们要知道：先序序列遍历顺序是：根结点-左⼦树-右⼦树后序序列遍历顺序是：左⼦树-右⼦树-根结点很明显，我们可以看出结点在先、后序列中的排布有以下这些特征：【1】、在先序序列中，根结点在⼦树中的结点前⾯，在后序序列中，根结点在⼦树中的结点后⾯。

【2】、以任⼀节点为根结点时，其⼦树在先序后序序列中排布都是先左⼦树后右⼦树，⽽根结点排在最后。

那么，反过来思考，已知这个先序与后序序列所确定的树是唯⼀的吗？进⼀步推⼴：怎么通过先序与后序序列判断是否存在唯⼀的树呢？现在，我们来⼀步步分析已知先序与后序的建树过程：①、根据特征【1】可知：根结点为先序序列第⼀个节点以及后序序列最后⼀个结点，因此根结点为1。

②、先序序列中第⼆个结点为2，其在后序序列中的位置是第⼀个，那么根据特征【2】我们可以知道结点2是没有⼦树的，⽽且结点2要么在根结点的左⼦树，要么在右⼦树。

假设结点2在右⼦树，那么由特征【2】可知根结点1没有左⼦树，⽽且先序序列中结点2后⾯的结点全部为结点2的⼦树上的结点。

再看后序序列，由特征【2】可知，结点2后⾯的结点不可能是其⼦树上的结点。

因此，假设显然与已知⽭盾。

这样，我们⼜知道结点2是结点1的左孩⼦，且结点2没有⼦结点。

③、先序序列第三个位置上的结点为3，该结点在后序序列中排倒数第⼆个。

由②可知，结点3必然是根结点1的右孩⼦。

④、先序序列第四个位置上的结点为4，该结点在后序序列中排第四个。

因为结点4在先序序列中排在结点3后⾯，⼜因为结点3是根结点1的右孩⼦，所以结点4只可能在结点3的⼦树上。

结点3的⼦树可能出现的情况是：只有左⼦树，只有右⼦树，左右⼦树都有。

因为在后序序列中，结点4左边是结点6、7，右边是结点5。

二叉树的三种遍历方法
二叉树是一种常见的数据结构，它由节点和边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的遍历是指按照一定的顺序依次访问二叉树中的所有节点。

常见的二叉树遍历方法有三种，分别是前序遍历、中序遍历和后序遍历。

一、前序遍历
前序遍历是指先访问根节点，再依次访问左子树和右子树。

具体步骤如下：
1. 访问根节点。

2. 前序遍历左子树。

3. 前序遍历右子树。

二、中序遍历
中序遍历是指先访问左子树，再访问根节点，最后访问右子树。

具体步骤如下：
1. 中序遍历左子树。

2. 访问根节点。

3. 中序遍历右子树。

三、后序遍历
后序遍历是指先访问左子树，再访问右子树，最后访问根节点。

具体步骤如下：
1. 后序遍历左子树。

2. 后序遍历右子树。

3. 访问根节点。

以上三种遍历方法都是深度优先遍历，因为它们都是先访问一个节点的所有子节点，再依次访问子节点的子节点。

在实际应用中，不同的遍历方法有不同的应用场景，例如前序遍历可以用于复制一棵二叉树，中序遍历可以用于排序，后序遍历可以用于计算表达式的值。

⼆叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）之前的⼀篇随笔（）只对⼆叉树的遍历进⾏了笼统的描述，这篇随笔重点对前、中、后序的遍历顺序进⾏分析⼆叉树的遍历⼆叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历，这三种遍历可以⽤递归实现（本篇随笔主要分析递归实现），也可使⽤⾮递归实现的前序遍历：根节点->左⼦树->右⼦树（根->左->右）中序遍历：左⼦树->根节点->右⼦树（左->根->右）后序遍历：左⼦树->右⼦树->根节点（左->右->根）在进⾏已知两种遍历顺序求另⼀种遍历顺序前，先看⼀下不同遍历顺序对应的代码前序遍历1/* 以递归⽅式前序遍历⼆叉树 */2void PreOrderTraverse(BiTree t, int level)3 {4if (t == NULL)5 {6return ;7 }8 printf("data = %c level = %d\n ", t->data, level);9 PreOrderTraverse(t->lchild, level + 1);10 PreOrderTraverse(t->rchild, level + 1);11 }中序遍历1/* 以递归⽅式中序遍历⼆叉树 */2void PreOrderTraverse(BiTree t, int level)3 {4if (t == NULL)5 {6return ;7 }8 PreOrderTraverse(t->lchild, level + 1);9 printf("data = %c level = %d\n ", t->data, level);10 PreOrderTraverse(t->rchild, level + 1);11 }后序遍历1/* 以递归⽅式后序遍历⼆叉树 */2void PreOrderTraverse(BiTree t, int level)3 {4if (t == NULL)5 {6return ;7 }8 PreOrderTraverse(t->lchild, level + 1);9 PreOrderTraverse(t->rchild, level + 1);10 printf("data = %c level = %d\n ", t->data, level);11 }三种遍历⽅式对应的代码⼏乎相同，只是⼀条语句的位置发⽣了变化printf("data = %c level = %d\n ", t->data, level);只看⽂字和代码来理解遍历的过程是⽐较困难的，建议读者亲⾃去遍历，为了理清遍历的过程下⾯上题（图⽚来源：）前序遍历前序的遍历的特点，根节点->左⼦树->右⼦树，注意看前序的遍历的代码printf语句是放在两条递归语句之前的，所以先访问根节点G，打印G，然后访问左⼦树D，此时左⼦树D⼜作为根节点，打印D，再访问D的左⼦树AA⼜作为根节点，打印A，A没有左⼦树或者右⼦树，函数调⽤结束返回到D节点（此时已经打印出来的有：GDA）D节点的左⼦树已经递归完成，现在递归访问右⼦树F，F作为根节点，打印F，F有左⼦树访问左⼦树E，E作为根节点，打印E，（此时已经打印出来的有：GDAFE），E没有左⼦树和右⼦树，函数递归结束返回F节点，F的左⼦树已经递归完成了，但没有右⼦树，所以函数递归结束，返回D节点，D节点的左⼦树和右⼦树递归全部完成，函数递归结束返回G节点，访问G节点的右⼦树M，M作为根节点，打印M，访问M的左⼦树H，H作为根节点，打印H，（此时已经打印出来的有：GDAFEMH）H没有左⼦树和右⼦树，函数递归结束，返回M节点，M节点的左⼦树已经递归完成，访问右⼦树Z，Z作为根节点，打印Z，Z没有左⼦树和右⼦树，函数递归结束，返回M节点，M节点的左⼦树右⼦树递归全部完成，函数递归结束，返回G节点，G节点的左右⼦树递归全部完成，整个⼆叉树的遍历就结束了（MGJ，终于打完了··）前序遍历结果：GDAFEMHZ总结⼀下前序遍历步骤第⼀步：打印该节点（再三考虑还是把访问根节点这句话去掉了）第⼆步：访问左⼦树，返回到第⼀步（注意：返回到第⼀步的意思是将根节点的左⼦树作为新的根节点，就好⽐图中D是G的左⼦树但是D也是A节点和F节点的根节点）第三步：访问右⼦树，返回到第⼀步第四步：结束递归，返回到上⼀个节点前序遍历的另⼀种表述：（1）访问根节点（2）前序遍历左⼦树（3）前序遍历右⼦树（在完成第2,3步的时候，也是要按照前序遍历⼆叉树的规则完成）前序遍历结果：GDAFEMHZ中序遍历（详细遍历过程就不再赘述了，(┬＿┬)）中序遍历步骤第⼀步：访问该节点左⼦树第⼆步：若该节点有左⼦树，则返回第⼀步，否则打印该节点第三步：若该节点有右⼦树，则返回第⼀步，否则结束递归并返回上⼀节点（按我⾃⼰理解的中序就是：先左到底，左到不能在左了就停下来并打印该节点，然后返回到该节点的上⼀节点，并打印该节点，然后再访问该节点的右⼦树，再左到不能再左了就停下来）中序遍历的另⼀种表述：（1）中序遍历左⼦树（2）访问根节点（3）中序遍历右⼦树（在完成第1，3步的时候，要按照中序遍历的规则来完成）所以该图的中序遍历为：ADEFGHMZ后序遍历步骤第⼀步：访问左⼦树第⼆步：若该节点有左⼦树，返回第⼀步第三步：若该节点有右⼦树，返回第⼀步，否则打印该节点并返回上⼀节点后序遍历的另⼀种表述：（1）后序遍历左⼦树（2）后序遍历右⼦树（3）访问根节点（在完成1,2步的时候，依然要按照后序遍历的规则来完成）该图的后序遍历为：AEFDHZMG（读者如果在纸上遍历⼆叉树的时候，仍然容易将顺序搞错建议再回去看⼀下三种不同遍历对应的代码）进⼊正题，已知两种遍历结果求另⼀种遍历结果（其实就是重构⼆叉树）第⼀种：已知前序遍历、中序遍历求后序遍历前序遍历：ABCDEF中序遍历：CBDAEF在进⾏分析前读者需要知道不同遍历结果的特点1、前序遍历的第⼀元素是整个⼆叉树的根节点2、中序遍历中根节点的左边的元素是左⼦树，根节点右边的元素是右⼦树3、后序遍历的最后⼀个元素是整个⼆叉树的根节点（如果读者不明⽩上述三个特点，建议再回去看⼀下三种不同遍历对应的代码，并在纸上写出⼀个简单的⼆叉树的三种不同的遍历结果，以加深对三种不同遍历的理解）⽤上⾯这些特点来分析遍历结果，第⼀步：先看前序遍历A肯定是根节点第⼆步：确认了根节点，再来看中序遍历，中序遍历中根节点A的左边是CBD，右边是EF，所有可以确定⼆叉树既有左⼦树⼜有右⼦树第三步：先来分析左⼦树CBD，那么CBD谁来做A的左⼦树呢？这个时候不能直接⽤中序遍历的特点（左->根->右）得出左⼦树应该是这个样⼦因为有两种情况都满⾜中序遍历为CBD⽆法直接根据中序遍历来直接得出左⼦树的结构，这个时候就要返回到前序遍历中去观察前序遍历ABCDEF，左⼦树CBD在前序遍历中的顺序是BCD，意味着B是左⼦树的根节点（这么说可能不太好理解，换个说法就是B是A的左⼦树）,得出这个结果是因为如果⼀个⼆叉树的根节点有左⼦树，那么这个左⼦树⼀定在前序遍历中⼀定紧跟着根节点（这个是⽤前序遍历的特点（根->左->右）得出的）,到这⾥就可以确认B是左⼦树的根节点第四步：再观察中序遍历CBDAEF，B元素左边是C右边是D，说明B节点既有左⼦树⼜有右⼦树，左右⼦树只有⼀个元素就可以直接确定了，不⽤再返回去观察前序遍历第五步：到这⾥左⼦树的重建就已经完成了，现在重建右⼦树，因为重建右⼦树的过程和左⼦树的过程⼀模⼀样，步骤就不像上⾯写这么细了（(┬＿┬)），观察中序遍历右⼦树为EF，再观察前序遍历ABCDEF中右⼦树的顺序为EF，所以E为A的右⼦树，再观察中序便利中E只有右边有F，所有F为E的右⼦树，最后得到的⼆叉树是这个样⼦的所有求得的后序遍历为：CDBFEA总结⼀下上述步骤：先观察前序遍历找到根节点->观察中序遍历将根节点左边归为左⼦树元素，右边归为右⼦树元素（可能会出现只有左⼦树或者右⼦树的情况）->观察前序遍历中左\右⼦树⼏个元素的顺序，最靠前的为左\右⼦树的根节点->重复前⾯的步骤第⼆种：已知中序遍历、后序遍历求前序遍历（题还是上⾯这道）中序遍历：CBDAEF后序遍历为：CDBFEA仍然是根据不同遍历⽅式结果的特点来重构⼆叉树，过程很相似这⾥就不详细说了，后序遍历的最后⼀个元素A是根节点，在中序遍历中以根节点A作为分界将元素分为左⼦树（CBD）和右⼦树（EF），再观察后序遍历中左⼦树的顺序是CDB，可以判断出B是左⼦树的根节点（因为后序遍历是：左->右->根），再观察中序遍历，B元素左边是C右边是D，说明B节点既有左⼦树⼜有右⼦树，左右⼦树只有⼀个元素就可以直接确定了，不⽤再返回去观察后序遍历，左⼦树重建完成，现在来看右⼦树，右⼦树有两个元素EF，观察后序遍历E在F的后⾯，所以E是右⼦树的根节点，然后看中序遍历中E只有右边⼀个F元素了，即F是E的右⼦树，此时整个⼆叉树重构完成总结⼀下上述步骤：先观察后序遍历找到根节点->观察中序遍历将根节点左边归为左⼦树元素，右边归为右⼦树元素（可能会出现只有左⼦树或者右⼦树的情况）->观察后序遍历中左\右⼦树⼏个元素的顺序，最靠后的为左\右⼦树的根节点->重复前⾯的步骤注意：已知前序遍历、后序遍历⽆法求出中序遍历（因为由前序后序重构出来的⼆叉树不⽌⼀种）举个栗⼦左图这两种⼆叉树前序（BEFA）和后序（AFEB）⼀样，但对应的中序遍历结果不⼀样（左边的是AFEB右边的是BEFA），所以仅靠前序后序是重构出唯⼀的⼆叉树。