永发信息网

对某二叉树进行前序遍历的结果为EBADCFHGIKJ,中序遍历的结果为ABCDEFGHIJK,那后序遍历结果为

答案:1  悬赏:80  手机版
解决时间 2021-03-22 12:06
对某二叉树进行前序遍历的结果为EBADCFHGIKJ,中序遍历的结果为ABCDEFGHIJK,那后序遍历结果为
最佳答案
用前序遍历结果去分割中序遍历结果,还原二叉树,然后再依此写出后序遍历结果。
    前序遍历结果第一位为E,说明根节点为E,以E分割中序遍历结果,得左子树为ABCD,右子树为FGHIJK:
             E
          /      
    ABCD   FGHIJK
    前序遍历第二位为B,说明B为左子树父节点,以B分割中序遍历,得A为左子树,CD为右子树:
             E
           /    
         B    FGHIJK
        /  
     A   CD
    前序遍历第三位为A,说明A为左节点,但2中B的左子树只有A,所以无需再分割;    
    前序遍历第四位为D,说明D为C的父节点,据此分割中序遍历,得C为D的左子树:


             E
           /    
         B    FGHIJK
        /  
     A     D
           /
         C
    前序遍历第五位为C,同3,无需再分割;
    前序遍历第六位为F,以F分割中序遍历,得F左子树为空,右子树为GHIJK:


             E
           /    
         B      F
       /        
     A     D    GHIJK
           /
         C
    前序遍历第七位为H,以H分割中序遍历,得H左子树为G,右子树为IJK:
             E
           /    
         B       F
       /          
     A     D     H
           /      /    
         C     G    IJK
8.前序遍历第八位为G,同3,无需再分割;
9.前序遍历第九位为I,以I分割中序遍历,得I左子树为空,右子树为JK:
         E
       /    
     B       F
   /          
 A     D     H
       /      /    
     C     G     I
                     
                      JK
10.前序遍历第十位为K,以K分割中序遍历,得K左子树为J,右子树为空。到此,二叉树被完全还原:
         E
       /    
     B       F
   /          
 A     D     H
       /      /    
     C     G     I
                     
                       K
                      /
                    J
11.根据还原出的二叉树写出后序遍历:ACDBGJKIHFE
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
单选题细胞学说是现代生物学的基础。下列哪项
亲,这怎么写?
四季海棠花怎么修剪花枝
雪峰口杯在哪里啊,我有事要去这个地方
写大熊猫的句子,怎样形容熊猫的句子
克兰西名著-猎杀红十月号核潜艇电子书txt全集
学好三门主课
没有上过大学的人有什么根本区别不
— How do you like Guilin?— It is the mos
fifteen to
电视有一条横道从下向上移动是怎么回事
笔记本怎么升级硬件
什么叫定型和半定型包包
富昆休闲浴场地址在哪,我要去那里办事
邹姓家字辈男孩取名
推荐资讯
Can you provide memore information about P
下列四幅图中,正确表示地球自转方向的是A.甲
最新伤感诗句,悲伤的诗句
数学专业和金融业有什么关系
刘芸为什么撇清和李小璐的关系?
谢家河头在什么地方啊,我要过去处理事情
念奴娇赤壁怀古 与 念奴娇瓢泉酒酣 同为豪放
会计里的降七个税点是什么意思?比如说单价是
毕加猪经典语录英文,有关猪和羊的古诗词
富有文采的生日祝福语,写给领导又是朋友的生
画剪力墙是用探索者自带的好还是雨夜屠夫好
金中的扩招问题
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?