首页 > 代码库 > 已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历?
已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历?
- 前序遍历 N->L->R
- 中序遍历 L->N->R
- 后序遍历 L->R->N
/*****************************************************************************************************/
声明:本博内容均由http://blog.csdn.net/droidphone原创,转载请注明出处,谢谢!
/*****************************************************************************************************/
所以,对于以下这棵树,三种遍历方式的结果是:
- 前序遍历 ABCDEF
- 中序遍历 CBDAEF
- 后序遍历 CDBFEA
已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历
其实,只要知道其中任意两种遍历的顺序,我们就可以推断出剩下的一种遍历方式的顺序,这里我们只是以:知道前序遍历和中序遍历,推断后序遍历作为例子,其他组合方式原理是一样的。要完成这个任务,我们首先要利用以下几个特性:
- 特性A,对于前序遍历,第一个肯定是根节点;
- 特性B,对于后序遍历,最后一个肯定是根节点;
- 特性C,利用前序或后序遍历,确定根节点,在中序遍历中,根节点的两边就可以分出左子树和右子树;
- 特性D,对左子树和右子树分别做前面3点的分析和拆分,相当于做递归,我们就可以重建出完整的二叉树;
我们以一个例子做一下这个过程,假设:
- 前序遍历的顺序是: CABGHEDF
- 中序遍历的顺序是: GHBACDEF
第一步,我们根据特性A,可以得知根节点是C,然后,根据特性C,我们知道左子树是:GHBA,右子树是:DEF。
C
/ \
GHBA DEF
/ \
GHBA DEF
第二步,取出左子树,左子树的前序遍历是:ABGH,中序遍历是:GHBA,根据特性A和C,得出左子树的父节点是A,并且A没有右子树。
C
/ \
A DEF
/ \
A DEF
/
GBH
第三步,使用同样的方法,前序是BGH,中序是GBH,得出父节点是B,G和H分别是左右节点。
C
/ \
A DEF
/ \
A DEF
/
B
/ \ G H
第四步,回到右子树,它的前序是EDF,中序是DEF,依然根据特性A和C,得出父节点是E,左右节点是D和F。
C
/ \
A E
/ \
A E
/ / \
B D F
/ \ G H
到此,我们得到了这棵完整的二叉树,因此,它的后序遍历就是:GHBADFEC。
人生若只如初见,何事秋风悲画扇。
已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。