已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?麻烦再画下这二叉树.

问题描述:

已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?麻烦再画下这二叉树.
楼下这位很我大概知道了,目前停留在几个地方依旧不懂,请耐心解释下,新人学习没办法
你说的
----------
a
/----\
EDCB--HFG
到这里应该都懂吧
那接下来就着重讲一下左子树的确定
右子树同理可得了
-----------------
请问右子树同理?为什么确定中序根右HFG和后序左根DBCEFGH中是去HFG,而不是EDCB?
问题是不是有点白?但是别什么同理啊,具体写一个都不能少啊,我是从来没接触过,直接学习,无基础知识,所以只有靠你们详细点啊,麻烦了!

后续遍历的顺序是左右根,中序遍历的顺序是左根右 
这点应该懂吧 
由后续访问序列可以看出最后一个被访问的必定是这个树的根 
而中序遍历的序列可以看出,一棵树当根确定后,在根前面被访问的是他的左子树,后边的是他的右子树元素 
弄懂了上边两点就开始做题吧 
由后序遍历序列是DBCEFGHA 
为了方便,我写小写字母了啊 
可以看出整棵树的根节点是a 
再看中序遍历序列EDCBAHFG 
a是根节点 
左子树由a左边的元素EDCB构成 
右子树由a右边的元素HFG构成 
也就是 

/----\ 
EDCB--HFG 
到这里应该都懂吧 
那接下来就着重讲一下左子树的确定 
右子树同理可得了 
看左子树有4个元素EDCB 
后序遍历序列是DBCE 
最后访问e 
可以确定a下边连接的是e 
根据中序遍历序列EDCB 
最先访问e 
由于中序遍历e前面没有元素 
可以确定e左子树为空 
即下面的样子 

/\ 


dbc 
也就是还剩下dbc的顺序没理好 
后序遍历序列是dbc 
最后访问c 
则c为根节点 
连接e 
中序遍历序列dcb 
c前边有d 
后边有b 
哪么可以确定dcb这棵树为 

/\ 
d b 
哪么整棵树的左子树就确定了 
为 



/\ 
d b 
同理 
右子树应为 





则整棵树就出来了 
为下图所示 
得出整棵树 
前序遍历自然不在话下 
为aecdbhgf 
------------------------
晕了,想偷下懒都不行呵
同理就是要你自己照着刚才的方法再推右边啊
左边在上边已经说了
那我们来看右边
右边剩下HFG
后序遍历序列是fgh
h最后被访问
可以确定h是右子树的根
也就是与a连着的是h
接下来看中序遍历顺序是HFG
h前面没有元素
说明h的左子树为空
剩下的g和f都是他的右子树的元素
再看后续遍历序列FG
g最后被访问
可以确定g是根节点连接h
然后看中序遍历序列fg
f在前
哪么f应该为g的左子树
整棵树就出来了
再不懂我也不知道怎么解释了

------------------------- 
好久没做类似的题 
有点生疏了 
若果有错 
欢迎指出