回复 孙玥:亲爱哒
不好意思,刚刚才看到题
我们说:后序序列是左右根,根结点为A;中序序列是左根右,二叉树只有左子树。按照遍历的顺序规则排列得出前序序列为ABCD。(注意:中序是左根右的遍历 后序是左右根的遍历 树的形式:)
所以画图如下:
A
B
C
D
Darling,望采纳哟,如果还有那些地方不懂我们还可以进行讨论哟,么么哒亲爱哒!
中序还是DCBA呀,中序的顺序是左中右.
在你上传的那个图片里面我们可以从下往上看先看DCB,左是D,中是C,右没有;然后再看DCB,左是DC,中是B,右没有(在往后看的时候不要把之前的给忽略了)就是这么个方法
可能我说的比较抽象,你要也可以这么想在整个二叉树中,最左边的是D然后是C其次是B根节点是A,中序就是DCBA
回复 孙玥:
亲爱哒,图片可以显示啊。
亲爱哒
你在做完之后会发现,如果:前序推出是:ABCD,那么中序不就是DCBA了吗?可是题目中哒已知是:中序是BDCA,后序才是DCBA呀,这是怎么回事呢?
其实呀,这就让我想到高中时数学中就的证明题中的”反证法“了,我们反的证明一下看看中序到底是不是DCBA不就行了吗!
那么这道题就变成了”已知二叉树中的前序是:ABCD,后序是DCBA,那我们来求一下中序就可以了(亲,这里要注意:必须是“两个”序遍历才能推出另一个,就好像我们说哒两点确定一条直线是一样哒道理,所以这里告了我们前序和后序求中序【而你刚刚哒问题中:我知道前序,那么求中序显然是不可能哒,除非这道题中就没有后序,但是如果一个二叉树没有后序遍历还能成为二叉树吗?显然是不行哒,我们说:二叉树中必须有:前,中,后序遍历,可以没有左子树或者右子树,这个要特别注意】
那我们接着按刚刚哒思路“已知前序是ABCD后序是DCBA求中序不就行了吗?【但是你在做过的那么多题里可以发现,在二叉树中:根本就木有告诉前序和后序让你求中序哒(因为我们“ 由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历序列不能唯一确定一棵二叉树”也就是说:如果题中告诉你:前序和后序让你求中序,那么这道题根本就求不出了,是一道“废题”,因为我们知道前序和后序能知道他的根,但是他的左子树和右子树我们根本就判断不了。也就是说:只有告了你中序是多少你才能继续判断。那么我们说:这道题就不能论证中字数是多少了吗?我们说:NO,NO,NO,天无绝人之路,办法还是有滴(思路:我们不是知道前序和后序了吗想推中序到底是:DCBA还是BDCA呢?但是由于我们二叉树离不开中序,那么我们可以换个思路:知道前序,然后把那两个中序带进去看看那个能推出后序是:DCBA来不就知道那个中序是“真美猴王”那个中序是“假美猴王”了吗?】(亲爱哒,亲原谅我是一个逗比,嘿嘿!)
解:我们说前序是:根左右——而我们已知:前序是:ABCD——就可以推出:根是:A
那我们接着来看有两个美猴王(中序:DCBA和中序:BDCA)让我们来请如来佛祖(后序:DCBA)验一验谁有火眼金睛(谁能推出:后序是DCBA来)谁就是真的。
我们先看第一个美猴王(中序:DCBA)
我们前面不是说:前序是:根左右——而我们已知:前序是:ABCD——就可以推出:根是:A然后,如果中序是——左根右:DCBA——又因为根是A,所以我们能知道:这个二叉树中只有左子树,没有右子树。然后以中序遍历为切入点,可以看出DCB为A的左子树——进而我们就推出:A为根。DCB为二叉树的左子树。
接着我们看后序是多少(是不是和已知的后序DCBA一样呢):我们说后序是:左右根
而刚刚我们推出:根为A。没有右子树,只有左子树:DCB——那么就能推出后序为:左右根——DCBA
所以我们说:真正哒美猴王是:中序DCBA(此时是特殊情况:即,只有左子树而且中序和后序是相同哒)所以中序就是:DCBA也是正确哒
亲爱哒,我形象哒讲解只是为了让你更好哒理解(请原谅我是一个逗比)望采纳哟,以后有问题我们还可以一起讨论哟,么么哒亲爱哒!
刚开始我看错了,以为题目上面的中序是DCBA,不好意思。实际上的二叉树应该是我上面画的那样的。
这样的遍历后序也是DCBA,后序是左右中,每一个的中都在最后,很容易就知道后序是DCBA。再分析中序BDCA,就知道这样的二叉树就是满足题目条件的。前序就是ABCD
回复 孙玥:
亲爱哒
不好意思,刚刚讲解时有一些失误,以下是正确详细的讲解过程,还望谅解
我们说:后序序列——左右根——DCBA——我们可以推出:二叉树哒根为A,因为A只有左边有元素,所以我们说二叉树中只有左子树,其中B,C,D都属于以A为节点的左子树,接下来我们再根据中序看看他们的位置是怎么样哒:
中序序列——左根右——BDCA——我们可以发现:A为根,B为A的左子树,C在B的右面所以C是B的右子树,因为D在C的左边,所以D是C 的左子树
所以图示为:
所以我们说:前序是——根左右——又因为没有右子树——所以即为:根左——A BCD(BCD都是以A为根节点的左子树)
所以答案选择:C选项就可以了
亲爱哒“望采纳哟!”如果以后还有什么不懂哒问题我们还可以一起讨论哟,相信我们一定会把问题解决哒。
亲爱哒:“新年快乐哟!”祝你在新哒一年里开开心心乐常在,健康幸福永相随,么么哒亲爱哒*^_^**^_^**^_^*
某二叉树的中序序列为BDCA,后序序列为DCBA,则前序序列为( )
A. DCBA
B. BDCA
C. ABCD
D. BADC
答案:C
解析:后序序列是左右中,根结点为A;中序序列是左中右,二叉树只有左子树。按照遍历的顺序规则排列得出前序序列为ABCD。所以选择C。