已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA,写出这颗二叉树并转化为森林!
嗯,这个问题我以前回答过了
凑合着看吧
很显然你还不懂的遍历一棵二叉树的原理
当你拿到一棵二叉树,无论它的形状如何的千奇百怪
我们都可以将它按照如下的方式划分
根
/ \
左子树 右子树
一棵有很多个节点的二叉树可以划分为以上的形式
也可以这么理解,只要是按以上形式组合的都可以称为是二叉树
一个仅仅只有根节点的二叉树也可以划分成以上的形式,只不过他的左右子树都为空罢了
所以,我们发现,二叉树的定义其实是一个递归定义的过程
大的二叉树是由小的二叉树构建而成的
所以,当我们考虑要遍历一棵二叉树时
也是首选递归的遍历
遍历二叉树
它的基本思想是先按照上面的形式把整棵二叉树划分为3部分
哪么接下来的工作就很简单了
我们只需要将这3部分都遍历一遍就可以了(这里用到了分而治之的思想)
而对于这3部分来说
根节点的遍历无疑是最方便的,直接访问就ok了
而对于左右子树呢?
我们不难发现,左右子树其实分别成为了两棵完整的树
他们拥有各自独立的根节点,左子树和右子树
对他们的遍历,很显然应该与刚才的遍历方法一致便可
(如果上面的都理解了,那么这个题就是小菜一碟了,如果觉得无法理解,可以按照下面的方法自己多分解几棵树)
对于这个题目,中序遍历这可二叉树
先看根节点
1
/ \
左子树 右子树
我们应该先遍历左子树
也就是下面这棵树
2
/ \
4 5
对于这棵树在进行中序遍历
我们应先遍历她的左子树
他只有一个根节点4,左右子树都为空
哪么遍历这个只有一个根节点的二叉树
先访问她的左子树,为空
返回
访问该树的根节点4
在访问右子树也为空
此时,这棵树已经被完全的遍历了
我们需要返回上一层也就是
2
/ \
4 5
这棵树
此时,她的左子树已经被访问完毕
根据中序遍历的规则
需要访问此树的根节点2
此时的访问顺序是4-2
访问了根节点
在访问右子树只有一个根节点的5(具体过程看4的访问)
5访问完毕
也就意味着
2
/ \
4 5
这棵树已经访问完了
需要返回上一层
也就是1为根的树
此时这棵树的左子树已经访问完毕
此时访问的顺序是4-2-5应该没有问题
接下来访问根节点1
在访问右子树
3
/ \
4 7
是不是觉得似曾相识???
她的访问应该跟
2
/ \
4 5
一致
哪么最终遍历的顺序也出来了
4-2-5-1-6-3-7
-----------------------------
花了10多分钟
希望对你有所帮助
顺便自己也复习下
呵呵
应该是EACBDGF.
遍历算法
1.中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
2.先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
3.后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。
过程:
第一步先根据后序遍历的最后一个结点是根结点,判断E为根,根据中序则ABCD在E的右侧,FG在E的左侧。
第二步根据中序ABCD和后序BDCA,判断A为这四个字母的根,并且BCD都在A的右侧,进一步根据中序BCD,后序BDC,判断C为这三个字母的根,且B在C的左侧,D在C的右侧。
第三步根据中序FG和后序BDC,判断B为三个字母的根,且CD都在左侧,进一步根据中序CD和后序DC,判断C为两个字母的根,且D在C的右侧。
最后根据上面得出的二叉树的图,得出前序应该是
EGFACDB
A
/ \
B C
/ \ \
D E F
/ \ \ / \
G H I J K
\
L
转化为森林:
A C F K
/ | \ |
B E I J
/ \
D H
/ \
G L
已知一棵二叉树的前序序列为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的右子树,依次进行判断,最后的出二叉树的序列。二叉树图,如下图:...
二叉树先知道后序和中序,求先序
后序DABEC 中序DEBAC;由后序最后一个字母知:整个树的开始结点为C;由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树;所以经过第一次推理,C为根结点,DEBA为其左子树;然后去掉C,考虑下面的左子树。后序DABE 中序DEBA由后序最后一个字母知:整个左子树的开始结点为E;由...
设一颗二叉树的中序遍历结果是DBEAFC,前序遍历结果是ABDECF,则后序便利...
结果如下:A B FC D E 下面再看FC两个节点,他们在前序遍历结果中的结果是CF,所以C是这两个节点中的根节点,再根据他们在中序遍历结果中的顺序FC,则F将他们本身划分为左子树(此时为空)和右子树C,则二叉树示意图如下:A B C D E 空 F ...
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(...
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(...序:A B C D E F G H I J 中序:C B E D A G H F J I 确定根是A,C B E D在A的左子树上,G H F J I在A的右子树上。先序:B C D E 中序:C B E D 确...
某二叉树,先序ABDGCEFH,中序DGBAECHF,求后续遍历的解题思路有哪些...
分析过程:以下面的例题为例进行讲解:已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列。分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序...
已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEI...
根据先序遍历和中序遍历,我们可以将这颗二叉树画出来,如下图。所以,根据图片,得出层次遍历序列为:ABCDEFGHI。
已知二叉树的中序遍历结果: BDCEAFHG。后序遍历结果:DECBHGFA,画出此二 ...
中序遍历按左子树、根结点、右子树的顺序;后序遍历按左子树、右子树、根结点的顺序。后序结果中A最后访问,所以A是根结点,结合中序结果可知,BDCE则都在二叉树的左边。后序结果中DECB最后访问B,则B就是A的左子树;中序最先访问B,说明B没有左子树,只有右子树……总之结合中后序遍历的结果,...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
(1)先序遍历(D L R):访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历(L D R):中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历(L R D):后序遍历左子树;后序遍历右子树;访问根结点。一棵二叉树不论哪种遍历算法,有以下要点:①所有叶子节点先后顺序不...
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉...
已知一棵二叉树前序遍和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为DBGE。去掉根节点和左子树节点,右子数节点为CHF。前序遍历的第二个节点...
某二叉树的中序遍历为CBADE,后序遍历序列为CBEDA,则前序遍历序列为?
后序遍历中最后一个就是树根结点,即A结点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为CB。去掉根节点和左子树节点,右子数节点为DE。在二叉树中,求前序遍历,先根后左再右,即首先访问根结点,然后遍历左子树,最后访问遍历右子树。则该二叉树的前序遍历是ABCDE。
永栋紫丹: 中序序列 BDCEAFHG 后序序列 DECBHGFA1、BDCEAFHG在后序序列中最后出现的元素为A,BDCE|A|FHG 2、BDCE在后序序列中最后出现的元素为B,|B|DCE|A|FHG 3、FHG在后序序列中最后出现的元素为F,|B|DCE|A||F|HG 4、DCE在后序序列中最后出现的元素为C,|B|D|C|E|A||F|HG 5、HG在后序序列中最后出现的元素为G,|B|D|C|E|A||F|H|G| 6、所有元素都已经定位,二叉树求解完成. 如上图
唐河县17521903986: 已知一棵二叉树的中序序列和后序序列分别为c,b,e,d,a,h,g,i,j,f 和 c,e,d,b,h,j,i,g,f,a画出该二叉树 - ?
永栋紫丹:[答案] 1.从后序知,最后一个结点a必定是根,就可从中序把左右子树分开; 2.a左子树中序 cbed,右hgijf 3.a左子树后序 cedb,右hjigf,这就变成同样的两个新问题而已; 4.如此递归,问题就可解决
唐河县17521903986: 已知一棵二叉树的中序序列和后序序列,请画出该二叉树 中序序列 DIGJLKBAECHF 后序序列 ILKJGDBEHFCA - ?
永栋紫丹:[答案] 先画出二叉树: 前序为:ABDGIJKLCEHF
唐河县17521903986: 已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA,写出这颗二叉树并转化为森林! - ?
永栋紫丹: 二叉树:A/ \B C/ \ \D E F/ \ \ / \ G H I J K\L 转化为森林:A C F K/ | \ |B E I J/ \D H/ \ G L
唐河县17521903986: 已知一棵二叉树的中序序列和后序序列分别为c,b,a,e,d,h,g,j,i,f 和 c,b,e,h,j,i,g,f,d,a画出这棵二叉树,并写出其前序遍历序列 - ?
永栋紫丹:[答案] 这个问题我答了几次,搜一下就有答案了: 很简单.这也是个递归过程. 知道后序,就能找到“根”,是最后一个节点. 知道“根”节点,就好办了,从中序中把根结点找到,它左边是左子树的中序, 右边是右子树的中序,知道这两子树的中序,就能...
唐河县17521903986: 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,画出这棵二叉树. - ?
永栋紫丹:[答案] 2、BDCE在后序序列中最后出现的元素为B,|B|DCE|A|FHG\x0d3、FHG在后序序列中最后出现的元素为F,|B|DCE|A||F|HG\x0d4、DCE在后序序列中最后出现的元素为C,|B|D|C|E|A||F|HG\x0d5、HG在后序序列中最后出现的元素为G,|B|D|C|E|A||F|H|G|\x0...
唐河县17521903986: 已知某二叉树的后序遍历和中序遍历的序列分别为? - ?
永栋紫丹: 您好,你的问题,我之前好像也遇到过,以下是我原来的解决思路和方法,希望能帮助到你,若有错误,还望见谅!展开全部 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前...
唐河县17521903986: 已知二叉树的后序和中序序列如下,画出该二叉树.后序序列:DEABFCR 中序序列:DAERBCF - ?
永栋紫丹:[答案] 已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:1.根据后序序列的最后一个元素建立根结点; 2.在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3.在后序序列中确定左右子树的后序序列; 4....
唐河县17521903986: 已知一棵二叉树的中序遍历序列为BAFDHGCE,后序遍历序列为BFHGDCA,请构造出这棵二叉树 - ?
永栋紫丹: 后序遍历少了一个结点E......后序遍历的 结果是 BFGHDECA整个二叉树的结构是:AB CD EF GH B,C是A的左右结点. D,E是C的左右结点. F,G是D的左右结点 H是G的左结点
唐河县17521903986: 一棵二叉树的先序、中序和后序序列分别如下,其中有一部分为显示出来,试求出空格处的内容,画出该二叉树 - ?
永栋紫丹: 一棵二叉树的先序、中序和后序序列分别如下,其中有一部分为显示出来,试求出空格处的内容,(1)画出该二叉树.(2)将这棵二叉树转换成对应的树(或森林). 先序:_B_E_FHG_J 中序:E_BHFD_JGA 后序:_C_FJIGD_A因为根据先序...