Site Overlay

数据结构:前序+中序序列确定树

pre = ADCBFKHIGJE
in  = BCDKFHAGIJE

pre = A DCBFKH IGJE    // 找出根(第一个)和左右(按照 in 行左右两部分含有的字母)
in  = BCDKFH A GIJE

        A
DCBFKH      IGJE       // 得到大致结构
                       // 后面对左右递归如此操作
for DCBFKH
    BCDKFH

    D CB FKH
    BC D KFH

            D
        CB      KFH

        for CB
            BC

            C B
            B C

                    C
                B
        for FKH
            KFH

            F K H
            K F H

                        F
                    K       H

for IGJE
    GIJE

    I G JE
    G I JE

            I
          G   JE

          for JE
              JE

              J NULL E
              NULL J E

                J
                    E
return 
       A 
      / \
     /   \
    D     I
   / \   / \
  C   F G   J
 /   / \     \
B   K   H     E

发表评论

电子邮件地址不会被公开。 必填项已用*标注