首页 > 试题广场 >

已知一个二叉树的中序遍历为DCBAGEH，前序遍历为ABCD

[单选题]

已知一个二叉树的中序遍历为DCBAGEH，前序遍历为ABCDEGH，则其后续遍历为（ ） 

  • DBEGFCA  
  • DCBGHEA 
  • DBGECFA
  • DEBFCGA
查看正确选项
添加回答
Aaron_Bin头像 Aaron_Bin
由前序遍历可知A作为根结点，由中序遍历可知DCB为A的左子树，GEH为A的右子树
            于是有                    A
                                        /      \
                                  (DCB) (GEH)
对于左子树DCB：由前序BCD可知B为父节点，由中序可知DC为B的左子树
            于是有                    A
                                        /      \
                                     B     (GEH)
                                    /
                                (DC)
                               由前序CD可知C为父节点，由中序可知D为C的左子节点
            于是有                    A
                                        /      \
                                     B     (GEH)
                                    /
                                 C
                                /
                             D
对于右子树GEH：由前序EGH可知E为父节点，由中序可知G为E的左子节点，H为E的右子节点
            于是有                    A
                                        /      \
                                     B         E
                                    /          /    \
                                 C         G     H
                                /
                             D
发表于 2021-03-27 12:38:19 回复(0)
瑞257头像 瑞257
是这样一颗树：
                     A
                B       E
            C        G     H
         D
发表于 2021-03-27 11:20:27 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 金山WPS 2020
来自：金山办公2020校招i...
上传者：小小
难度：
2条回答 2488浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号