一只一棵二叉树的先序遍历结果为abcdefghi,中序遍历结果为cbafegdhi,请写出后序遍历结果并画出这棵二叉树
前序遍历BEFCGDH
中序遍历FEBGCHD
后序遍历FEGHDCB
先看先序,其第一个为树的根,先序遍历是先根再左子树最后右子树,第一个肯定是树的根,先画A,A再中序遍历中左右都有,说明A有左子树也有右子树。
A
/ \
然后看先序第一个值是B,在中序中为A的前面,所以B是A的左子树
A
/ \
B
继续看先序,接下来是C、D,C再中序中再B的前面,所以C是B的左子树,D在B后面,D是B的右子树。
A
/ \
B
/ \
C D
接下来是E,E在中序是在D后面A前面,所以E是D的右子树
A
/ \
B
/ \
C D
\
E
接着先序中是F,F在中序为A后面,是A的右子树
A
/ \
B F
/ \
C D
\
E
中序中 A 与F之间没有,说明F没有左子树,只有右子树.如上面方法继续分析GHIJ,最终二叉树如下:
A
/ \
B F
/ \ \
C D G
\ / \
E H J
\
I
左一定优先于右 ,所以根的位置有三种。
根 左 右、左 根 右、左 右 根。
分别称为先序遍历、中序遍历、后续遍历,子树也一样,到一个子树就遍历一次,按照遍历顺序写下去就好,尤其注意根特殊对待(只有一个所以只写一个)。
后续遍历是:CBEFDA
依据前序遍历序列可确定根结点为A;再依据中序遍历序列可知其左子树由DBE构成,右子树为FC;又由左子树的前序遍历序列可知其根结点为B,由中序遍历序列可知其左子树为D,同理推算FC的排列顺序。
扩展资料:
除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
有且仅有一个开始结点和一个终端结点,其余结点都有且仅有一个前驱结点和一个后继结点。为了区别于树形结构中前驱(即双亲)结点和后继(即孩子)结点的概念,对上述三种线性序列,要在某结点的前驱和后继之前冠以其遍历次序名称。
参考资料来源:百度百科-二叉树遍历
这类题的推导方法见:http://zhidao.baidu.com/question/199520462615190205.html?oldq=1
一棵二叉树的先序遍历序列为ABCDEF,中序遍历结果为CBAEDF,则后序遍历...
【答案】:A 二叉树的先序遍历序列和中序遍历序列一起可以确定这棵二叉树的形态。本题的解题思路是先根据题设确定这棵二叉树的形态,然后再用后序遍历此二叉树,得到后序遍历序列。根据先序遍历序列,A是二叉树的根结点。根据中序遍历序列,则二叉树的形态一定如图4—9所示。9考虑A的左子树。根据二...
一只一棵二叉树的先序遍历结果为abcdefghi,中序遍历结果为cbafegdhi...
根 左 右、左 根 右、左 右 根。分别称为先序遍历、中序遍历、后续遍历,子树也一样,到一个子树就遍历一次,按照遍历顺序写下去就好,尤其注意根特殊对待(只有一个所以只写一个)。后续遍历是:CBEFDA 依据前序遍历序列可确定根结点为A;再依据中序遍历序列可知其左子树由DBE构成,右子树为FC;...
已知一棵二叉树的前序序列为A B D G C E H I F;中序序列为:D G B A...
二叉树的后序为G、D、B、I、H、E、F、C、A。由前前序第一个为A,所以根节点,所以A的左子树为D、G、B,右子树为E、I、H、C、F。第二个根节点为B,又由中序的出B的左子树为D、G,然后得出D的右子树为G,C为A的右子树,依次进行判断,最后的出二叉树的序列。二叉树图,如下图:...
已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEI...
根据先序遍历和中序遍历,我们可以将这颗二叉树画出来,如下图。所以,根据图片,得出层次遍历序列为:ABCDEFGHI。
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(...
先序:G H 中序:G H 确定G是根,H是G的右孩子。先序:I J 中序:J I 确定I是根,J是I的左孩子。综合起来,树的结构如下所示:A B F C D G I E H J
一棵二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBAEDF,则后序遍历...
先序列号为这个,那么在编辑的时候,可以先进行用顺序的方式,然后再进行。后序序列是CBA。根据前序,可以确定A为根,A在中序中的位置,可以确定CB为A的左子树上的结点,没有右子树。确定A之后,再看中序第二值为B,查看B在中序中的位置,C在B左边,确定C为B的左子树。
知道先序中序遍历序列怎么求后序遍历序列?
先序:cefh --> c e fh 中序:echf --> e c hf 得出结论:c是右子树的根结点,c有左子树(只有e结点),有右子树(有fh结点)。先序:fh --> f h 中序:hf --> h f 得出结论:f是c的左子树的根结点,f有左子树(只有h结点),无右子树。还原二叉树为:a b c d...
已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAF...
前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回。因此,A是根结点,B是A的左子树,F是A的右子树。E是B的左子树,C是B的右子树,...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
(1)先序遍历(D L R):访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历(L D R):中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历(L R D):后序遍历左子树;后序遍历右子树;访问根结点。一棵二叉树不论哪种遍历算法,有以下要点:①所有叶子节点先后顺序不...
二叉树的先序、中序、后序是如何确定的?
二叉树的先序,中序,后序确定的方法如下:1、根据后序遍历的特点,我们知道后序遍历最后一个结点即为根结点,即根结点为G。2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树,G右侧的HMZ必然是root的右子树。3、观察左子树ADEF,左子树的中的根节点必然是大树的root的left...
兆昆昂醒脾: 1. 先序ABDFCEG,则A为根 2. 中序DFBACEG,则A左边的DFB为左子树,A右边的CEG为右子树 3. 左子树先序BDF,中序DFB 3.1. 先序BDF,则B为根 3.2. 中序DFB,则B左边的DF为左子树,D右边没有右子树 3.3. 左子树先序DF,中序DF ...
中站区17077451230: 一颗2叉树的先序遍历序列为ABDEHCFGI,中序遍历序列为DBHEAFLIG试还原该二叉树,并给出还原过程(求详解 - ?
兆昆昂醒脾: 就是先序遍历是根左右,所以A肯定是这棵二叉树的根;中序是左根右,从中序序列里,我们可以看出来,在A左面的是它的左子树,右边是右子树;再看先序,BDEH(我们从中序知道它是左子树的结点值),还是根据根左右知道,B是这四个结点的根;再看中序中的DBHE,根据左根右,知道D是B的左儿子,HE是B右子树的结点,再回看先序(BDEH中还剩EH),还是根左右,所以E是H的父,而E又是B的右儿子,H是E的左儿子;对于这棵二叉树的左子树确定了,右子树也是一样的这样来推,还有你的中序是不是给错了?怎么多了个L,应该是C吧
中站区17077451230: 一个数据结构二叉树的问题:已知一个二叉树的先序遍历为ABDFGEHC,中序遍历为FDGBEHAC, - ?
兆昆昂醒脾: A/,D是根先序遍历为ABDFGEHC A是根中序遍历为FDGBEHAC 可知A的左子树是FDGBEH 右叶结点C F是 叶结点 后序遍历为 FGDHEBCA 结合上面FGDHEB中B是根;D E/ \B C/ \,可知FDG就B的左子树 EH是右子树 后序中有FGD,所以,E是根 结果为, G是右叶 后序中的HE说明H是叶,F是左叶,再看中序FDGBEH(找B的左右); \ \
中站区17077451230: 一棵二叉树的前序遍历序列为abdec,二叉树的根为什么? 答案和原因,谢谢 - ?
兆昆昂醒脾: 根是a.因为二叉树前序遍历按 根左右的顺序,所以a就是二叉树的根节点.
中站区17077451230: 已知一颗二叉树的先序遍历序列为:ABDCEF,中遍历为:BDAECF,请画出这颗二叉树,并给出其后序遍历序列 - ?
兆昆昂醒脾: A->Lchild=D,A->Rchild=C,D->lchild=B,C->lchild=E,C->rchild=F 后序遍历:BDEFCA
中站区17077451230: 某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出二叉树 并给出其后序遍历序列 最好解释 - ?
兆昆昂醒脾: 分析过程: 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左...
中站区17077451230: 一棵二叉树的先序遍历次序为ABDGECFH,中序遍历次序为DGBEAFHC,则其后序遍历次序为多少呢?(数据结构试题?
兆昆昂醒脾: 先序遍历次序由:根+根的左子树先序遍历次序+根的右子树先序遍历次序构成; 中序遍历次序由:根的左子树中序遍历次序+根+根的右子树中序遍历次序构成; 由先序遍历次序为ABDGECFH可知,二叉树的根为A; 再由中序遍历次序为...
中站区17077451230: 对某二叉树进行前序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序周游的结果为 - ?
兆昆昂醒脾: 太简单了,对于一个小学生来说简直如同儿戏. 结果:DFEBCA 我们首先要构造一棵树. 根是A,然后根据先序遍历得知左子树的根是B,再根据中序遍历得知,B的左子树是D,右子树的根是E,如果是F,那先序遍历就无法遍历了.E的左子树是F,A的左边完了,右边就是C.FD EB CA 就是这棵树.(可能有点不标准)
中站区17077451230: 如果一棵二叉树的前序遍历序列是ABDFCEG,中序遍历序列是DFBACEG,则它的后序遍历序列是 - ?
兆昆昂醒脾: 由前序可得根(A)有中序可得左子树(DFB)右子数(CEG) 前序可分为三份 根(A)、左子树(BDF)、 右子数(CEG) 前序中的左子树的根(B),由中序可得先访问D、F后访问B,所以F为B的左子树,D为F的左子树.同理,前序中的右子树的根(C)、由中序可得先访问根,根C没有左子树,根据前序中先访问E,则E为C的右子树的根,有根据中序,先访问根E,所以G为根E的右子树.完毕.A(B(F(D, ), ), C(, E(, G))) 忘了,它的后序:DFBGECA