⼆叉树的遍历（前序、中序、后序、已知前中序求后序、已知中
后序求前序）
之前的⼀篇随笔（）只对⼆叉树的遍历进⾏了笼统的描述，这篇随笔重点对前、中、后序的遍历顺序进⾏分析
⼆叉树的遍历
⼆叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历，这三种遍历可以⽤递归实现（本篇随笔主要分析递归实现），也可使⽤⾮递归实现的
前序遍历：根节点->左⼦树->右⼦树（根->左->右）
中序遍历：左⼦树->根节点->右⼦树（左->根->右）
后序遍历：左⼦树->右⼦树->根节点（左->右->根）
在进⾏已知两种遍历顺序求另⼀种遍历顺序前，先看⼀下不同遍历顺序对应的代码
前序遍历
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的左⼦树A
A⼜作为根节点，打印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的右⼦树，最后得到的⼆叉树是这个样⼦的

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。