遍历如果是这样那中序不就是DCBA了?
孙玥 知名达人 2016-01-30 00:12:36
1096 9 0



问题来自: 二叉树的遍历
某二叉树的中序序列为BDCA,后序序列为DCBA,则前序序列为( )
A. DCBA
B. BDCA
C. ABCD
D. BADC
答案:C
解析:后序序列是左右中,根结点为A;中序序列是左中右,二叉树只有左子树。按照遍历的顺序规则排列得出前序序列为ABCD。所以选择C。

共 9 个回答

    孙玥 知名达人 1585天前



    孙玥 知名达人 1585天前

    图片为什么无法显示

    青栀如初 资深大师 1585天前

    回复 孙玥:亲爱哒

       不好意思,刚刚才看到题

          我们说:后序序列是左右根,根结点为A;中序序列是左根右,二叉树只有左子树。按照遍历的顺序规则排列得出前序序列为ABCD。(注意:中序是左根右的遍历 后序是左右根的遍历 树的形式:)

       所以画图如下:

     

                                    A

                              B

                       C

                D

      Darling,望采纳哟,如果还有那些地方不懂我们还可以进行讨论哟,么么哒亲爱哒!


    zy 资深达人 1584天前

    中序还是DCBA呀,中序的顺序是左中右.

    在你上传的那个图片里面我们可以从下往上看先看DCB,左是D,中是C,右没有;然后再看DCB,左是DC,中是B,右没有(在往后看的时候不要把之前的给忽略了)就是这么个方法

    可能我说的比较抽象,你要也可以这么想在整个二叉树中,最左边的是D然后是C其次是B根节点是A,中序就是DCBA

    青栀如初 资深大师 1584天前

    回复 孙玥

    亲爱哒,图片可以显示啊

      亲爱哒

        你在做完之后会发现,如果:前序推出是: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,所以我们能知道:这个二叉树中只有左子树,没有右子树。然后以中序遍历为切入点,可以看出DCBA的左子树——进而我们就推出:A为根。DCB为二叉树的左子树。

        接着我们看后序是多少(是不是和已知的后序DCBA一样呢):我们说后序是:左右根

        而刚刚我们推出:根为A。没有右子树,只有左子树:DCB——那么就能推出后序为:左右根——DCBA

        所以我们说:真正哒美猴王是:中序DCBA(此时是特殊情况:即,只有左子树而且中序和后序是相同哒)所以中序就是:DCBA也是正确哒

        亲爱哒,我形象哒讲解只是为了让你更好哒理解(请原谅我是一个逗比)望采纳哟,以后有问题我们还可以一起讨论哟,么么哒亲爱哒!

     

     

     

    zy 资深达人 1584天前

    你的二叉树画错了,如果按照你的这么画中序确实是DCBA。但是实际上的二叉树是这样的捕获.PNG

    zy 资深达人 1584天前

    刚开始我看错了,以为题目上面的中序是DCBA,不好意思。实际上的二叉树应该是我上面画的那样的。

    这样的遍历后序也是DCBA,后序是左右中,每一个的中都在最后,很容易就知道后序是DCBA。再分析中序BDCA,就知道这样的二叉树就是满足题目条件的。前序就是ABCD

    青栀如初 资深大师 1581天前

    回复 孙玥: 亲爱哒,望采纳哟,如果以后有不懂哒问题或者困惑哒地方我们还可以一起讨论哟,相信一定会把问题解决哒,么么哒亲爱哒!

    青栀如初 资深大师 1564天前

    回复 孙玥

     

    亲爱哒

        不好意思,刚刚讲解时有一些失误,以下是正确详细的讲解过程,还望谅解

         我们说:后序序列——左右根——DCBA——我们可以推出:二叉树哒根为A,因为A只有左边有元素,所以我们说二叉树中只有左子树,其中B,C,D都属于以A为节点的左子树,接下来我们再根据中序看看他们的位置是怎么样哒:

                    中序序列——左根右——BDCA——我们可以发现:A为根,B为A的左子树,C在B的右面所以C是B的右子树,因为D在C的左边,所以D是C 的左子树

                   

      所以图示为:                       

                                       blob.png

                           

               

    所以我们说:前序是——根左右——又因为没有右子树——所以即为:根左——A  BCD(BCD都是以A为根节点的左子树)

    所以答案选择:C选项就可以了

         亲爱哒“望采纳哟!”如果以后还有什么不懂哒问题我们还可以一起讨论哟,相信我们一定会把问题解决哒。

          亲爱哒:“新年快乐哟!”祝你在新哒一年里开开心心乐常在,健康幸福永相随,么么哒亲爱哒*^_^**^_^**^_^*

      

您还没有登录,所以不能回复该问题
我要回复

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题