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

2025-03-29 15:39:54
推荐回答(1个)
回答1:

用前序遍历结果去分割中序遍历结果,还原二叉树,然后再依此写出后序遍历结果。

  1. 前序遍历结果第一位为E,说明根节点为E,以E分割中序遍历结果,得左子树为ABCD,右子树为FGHIJK:

             E

          /       \

    ABCD   FGHIJK

  2. 前序遍历第二位为B,说明B为左子树父节点,以B分割中序遍历,得A为左子树,CD为右子树:

             E

           /    \

         B    FGHIJK

        /   \

     A   CD

  3. 前序遍历第三位为A,说明A为左节点,但2中B的左子树只有A,所以无需再分割;    

  4. 前序遍历第四位为D,说明D为C的父节点,据此分割中序遍历,得C为D的左子树:


             E

           /    \

         B    FGHIJK

        /   \

     A     D

           /

         C

  5. 前序遍历第五位为C,同3,无需再分割;

  6. 前序遍历第六位为F,以F分割中序遍历,得F左子树为空,右子树为GHIJK:


             E

           /    \

         B      F

       /   \       \

     A     D    GHIJK

           /

         C

  7. 前序遍历第七位为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