已知二叉树先序遍历的结果是ABDHIECFGJK,中序遍右的结果是HDIBEAFCJKG,度画出该二叉树及其后序遍历结果??
后续遍历的顺序是左右根,中序遍历的顺序是左根右
这点应该懂吧
由后续访问序列可以看出最后一个被访问的必定是这个树的根
而中序遍历的序列可以看出,一棵树当根确定后,在根前面被访问的是他的左子树,后边的是他的右子树元素
弄懂了上边两点就开始做题吧
由后序遍历序列是DBCEFGHA
为了方便,我写小写字母了啊
可以看出整棵树的根节点是a
再看中序遍历序列EDCBAHFG
a是根节点
左子树由a左边的元素EDCB构成
右子树由a右边的元素HFG构成
也就是
a
/----\
EDCB--HFG
到这里应该都懂吧
那接下来就着重讲一下左子树的确定
右子树同理可得了
看左子树有4个元素EDCB
后序遍历序列是DBCE
最后访问e
可以确定a下边连接的是e
根据中序遍历序列EDCB
最先访问e
由于中序遍历e前面没有元素
可以确定e左子树为空
即下面的样子
a
/\
e
\
dbc
也就是还剩下dbc的顺序没理好
后序遍历序列是dbc
最后访问c
则c为根节点
连接e
中序遍历序列dcb
c前边有d
后边有b
哪么可以确定dcb这棵树为
c
/\
d b
哪么整棵树的左子树就确定了
为
e
\
c
/\
d b
同理
右子树应为
h
\
g
/
f
则整棵树就出来了
为下图所示
得出整棵树
前序遍历自然不在话下
为aecdbhgf
------------------------
晕了,想偷下懒都不行呵
同理就是要你自己照着刚才的方法再推右边啊
左边在上边已经说了
那我们来看右边
右边剩下HFG
后序遍历序列是fgh
h最后被访问
可以确定h是右子树的根
也就是与a连着的是h
接下来看中序遍历顺序是HFG
h前面没有元素
说明h的左子树为空
剩下的g和f都是他的右子树的元素
再看后续遍历序列FG
g最后被访问
可以确定g是根节点连接h
然后看中序遍历序列fg
f在前
哪么f应该为g的左子树
整棵树就出来了
再不懂我也不知道怎么解释了
额
-------------------------
好久没做类似的题
有点生疏了
若果有错
欢迎指出
1、先求原始二叉树,后序遍历中最后出现的是根,所以A是整棵树的根,在结合中序遍历来看
BDCE是A的左子树,而FHG是A的右子树;
2、BDCE序列中B是整个序列根,因为后序遍历中B最后出现。此时再看中序中根B左端没有左子
树,右端有DCE,所以DCE是B的右子树 ;
3、再看D、C、E在后序遍历中C结点最后出现,所以C是根,此时再到中序遍历看可以看到C的左
端是D,右端是E,所以C的左子树是D,右子树是E;
4、再看F、H、G三个结点,后序遍历序列F最后出现,所以F是根结点,再回去看中序HG在F右
端,所以HG是F的右子树;
5、由于H、G在后序遍历序列G最后出现,所以G是H, G中的根,再看 中序中G左端只有一个H,
所以H是G的左子树,得到最终原始二叉树。
需要注意的几点:
1、根是相对的,对于整棵树而言只有一个根,但对于每棵子树而言,又有自己的根。
2、前序遍历时,一棵树的根永远在左子树前面,左子树又永远在右子树前面。
3、二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序一样。
A
B C
D E F G
H I J
K
后序遍历:HIDEBFKJGCA
二叉树的前序遍历是什么?
中序遍历:访问根节点在左右子树之间,即左—根—右。来后序遍历:访问根结点在源左右子树之后,即左—右—根。由定义可以知道:1、后序遍历中最百后一个就是树根结点,即A结点。2、在中序遍历中,根结点左边的是左儿子集,右边的是右儿子集。所以二叉树应该为度A、\/\\、BD、\/\\、CE,所以前序...
已知一棵二叉树的先序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍...
【答案】:A 对于这种遍历序列问题,先根据遍历的性质排除若干项,若还无法确定答案,再根据遍历结果得到二叉树,找到对应遍历序列。如本题中,已知先序和中序遍历结果,可知本树根结点为A,左子树有C和B,其余为右子树,则后序遍历结果中,A一定在最后,并且C和B一定在前面,排除答案B和D。又因先...
二叉树前序中序后序口诀
先序:是二叉树遍历中的一种,即先访问根结点,然后遍历左子树,后遍历右子树。遍历左、右子树时,先访问根结点,后遍历左子树,后遍历右子树,如果二叉树为空则返回。中序:是二叉树遍历中的一种,即先遍历左子树,后访问根结点,然后遍历右子树。若二叉树为空则结束返回。后序:是二叉树遍历中的...
某二叉树的先序遍历序列为ABCDEF,中序遍历序列为BADCFE,则该二叉树...
【答案】:B先序遍历即先根后左子树再右子树,中序遍历为先左子树后跟再右子树。先序遍历的最开始结点A即为整棵树的根,结合中序遍历,A结点左侧B即为根节点A的左子树,右侧DCFE则为A的右子树,同理可以得出C为A的右子树的根节点,D为C的左子树,EF为C的右子树,F为E的左子树。可以得到如...
二叉树的前序、中序和后序遍历序列分别是什么?
则该二叉树的前序遍历序列为ABDECF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。先序遍历二叉树规则:根-左-右 1、访问根结点;2、先序遍历左子树;3、先序遍历右子树。中序遍历二叉树规则:左-根-右 1、先中序遍历左子树;2、再访问根节点;3、最后访问中序遍历右子树。后序遍历二叉树规则...
已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEI...
根据先序遍历和中序遍历,我们可以将这颗二叉树画出来,如下图。所以,根据图片,得出层次遍历序列为:ABCDEFGHI。
写出二叉树的先序遍历、中序遍历、后序遍历。
那么,根据后序的遍历规则,我们可以知道,后序遍历顺序为:AEFDHZMG 二叉树的一些介绍:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(...
二叉树的先序,中序,后序遍历是?
前序遍历就是先遍历根节点,然后遍历左节点,最后是右节点;中序遍历就是先遍历左节点,然后遍历中间的根节点,最后是右节点;后序遍历就是先遍历左节点,然后遍历是右节点,最后是中间的根节点。二叉树的这三种遍历方法,是按照每颗子树的根节点顺序遍历的。
已知二叉树的先序遍历序列为“ABDECFG”和中序遍历序列“DBEAGFC...
1 先序序列 顺序是 根左右 首先出现的是根 中序序列 是左根右 以 第一个为例 先序 中 A 是根 节点 再 看中序 A左边的是 左子树 (DBE)A 右边的是右子树 (GFC)。然后之后的都和这个差不多 不懂的话还可以看看我的这个回答,更加的详细。更多参考资料 3 二叉树实际图形 层次遍历: ...
已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAF...
然后遍历左子树,最后遍历右子树。中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回。因此,A是根结点,B是A的左子树,F是A的右子树。E是B的左子树,C是B的右子树,D是C的右子树。G是F的右子树。H是G的左子树,J是G的右子树。I是H的左子树。
郗烁破伤: 如果仅有“已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ”,则中序遍历的结果是不能确定的.
万柏林区15180718423: 某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出二叉树 并给出其后序遍历序列 最好解释 - ?
郗烁破伤: 分析过程: 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左...
万柏林区15180718423: 已知二叉树前序、中序遍历结果,求后序遍历结果? - ?
郗烁破伤: 例:若某二叉树的前遍历访问顺序是序abdgcefh,中序遍历顺序是dgbaechf (1)由前序遍历结果我们可知a为根结点,再看中序遍历结果,因为中序遍历顺序是左子树、根、右子树,因此由“中序遍历顺序是dgbaechf”可断定,dgb为该二叉树的...
万柏林区15180718423: 已知某二叉树的前序是abdgcefh,中序dgbaechf,则后序是? - ?
郗烁破伤: 首先我们知道,前序遍历的规则是:根结点→左子结点→右子结点 中序遍历是:左子结点→根结点→右子结点 后序遍历是:左子结点→右子结点→根结点 那么,对于一棵二叉树,前序遍历的第一个结点一定是这棵树的根结点,即根结点是a. ...
万柏林区15180718423: 若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是( - ?
郗烁破伤: gdbehfca 图为:a-->b(左) a-->c(右) b-->d(左) d-->g(右) c-->e(左) c-->f(右) f-->h(左)
万柏林区15180718423: 一个数据结构二叉树的问题:已知一个二叉树的先序遍历为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的左右); \ \
万柏林区15180718423: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么? - ?
郗烁破伤: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点.中序遍历的根节点前面的节点均为左子树的节点,所以左子树上...
万柏林区15180718423: 一棵二叉树的前序遍历序列为abdec,二叉树的根为什么? 答案和原因,谢谢 - ?
郗烁破伤: 根是a.因为二叉树前序遍历按 根左右的顺序,所以a就是二叉树的根节点.
万柏林区15180718423: 已知某二叉树的先序遍历序列为:A,B,D,E,G,C,F,H,I,J,中序序列为:D,B,G,E,A,H,F,I,J,C试给出该二叉树的先序序列和后序序列 - ?
郗烁破伤:[答案] 先序序列是A,B,D,E,G,C,F,H,I,J 后序序列是D,G,E,B,H,J,I,F,C,A
万柏林区15180718423: 一棵二叉树的先序遍历次序为ABDGECFH,中序遍历次序为DGBEAFHC,则其后序遍历次序为多少呢?(数据结构试题?
郗烁破伤: 先序遍历次序由:根+根的左子树先序遍历次序+根的右子树先序遍历次序构成; 中序遍历次序由:根的左子树中序遍历次序+根+根的右子树中序遍历次序构成; 由先序遍历次序为ABDGECFH可知,二叉树的根为A; 再由中序遍历次序为...