(33)王道数据结构-遍历序列构造二叉树

构造方法

如果只给出一棵二叉树的前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树，构造分以下三种情况
①前序 + 中序遍历序列
②后续 + 中序遍历序列
③层序 + 中序遍历序列

遍历序列

前序+中序

前序遍历: 根节点、前序遍历左子树、前序遍历右子树
中序遍历: 中序遍历左子树、根节点、中序遍历右子树

左子树的前序遍历序列 = 左子树的中序遍历序列
右子树的前序遍历序列 = 右子树的中序遍历序列

例子一:

前序序列: A D B C E
中序遍历: B D C A E

graph TD;
    A(("A"));
    BCD(("BDC"));
    C(("E"));
    A-->BCD;
    A-->C;

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    A-->D;
    A-->E;
    D-->B;
    D-->C;

例子二:

前序序列: D A E F B C H G I
中序遍历: E A F D H C B G I

graph TD;
    D(("D"));
    EAF(("EAF"));
    HCBGI(("HCBGI"));
    D-->EAF;
    D-->HCBGI;

graph TD;
    D(("D"));
    A(("A"));
    E(("E"));
    F(("F"));
    HCBGI(("HCBGI"));
    D-->A;
    D-->HCBGI;
    A-->E;
    A-->F;

graph TD;
    D(("D"));
    A(("A"));
    E(("E"));
    F(("F"));
    B(("B"));
    HC(("HC"));
    GI(("GI"));
    D-->A;
    A-->E;
    A-->F;
    D-->B;
    B-->HC;
    B-->GI;

graph TD;
    D(("D"));
    A(("A"));
    E(("E"));
    F(("F"));
    B(("B"));
    H(("H"));
    C(("C"));
    G(("G"));
    I(("I"));
    D-->A;
    A-->E;
    A-->F;
    D-->B;
    B-->C;
    B-->G;
    C-->H;
    C-->N1(( ));
    G-->N2(( ));
    G-->I;
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    linkStyle 7 stroke:#0ff,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px

后序+中序

前序遍历: 前序遍历左子树、前序遍历右子树、根节点
中序遍历: 中序遍历左子树、根节点、中序遍历右子树
左子树的后序遍历序列 = 左子树的中序遍历序列
右子树的后序遍历序列 = 右子树的中序遍历序列

例子一:

前序序列: E F A H C I G B D
中序遍历: E A F D H C B G I

graph TD;
    D(("D"));
    EAF(("EAF"));
    HCBGI(("HCBGI"));
    D-->EAF;
    D-->HCBGI;

graph TD;
    D(("D"));
    E(("E"));
    F(("F"));
    A(("A"));
    HCBGI(("HCBGI"));
    D-->A;
    D-->HCBGI;
    A-->E;
    A-->F;

graph TD;
    D(("D"));
    E(("E"));
    F(("F"));
    A(("A"));
    B(("B"));
    HC(("HC"));
    GI(("GI"));
    D-->A;
    D-->B;
    A-->E;
    A-->F;
    B-->HC;
    B-->GI;

graph TD;
    D(("D"));
    E(("E"));
    F(("F"));
    A(("A"));
    B(("B"));
    H(("H"));
    C(("C"));
    G(("G"));
    I(("I"));

    D-->A;
    D-->B;

    A-->E;
    A-->F;
    B-->C;
    B-->G;

    C-->H;
    C-->N1(( ));
    G-->N2(( ));
    G-->I;
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    linkStyle 7 stroke:#0ff,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px

层次+中序

层次序列: 根节点、左子树的根、右子树的根
中序序列: 左子树的中序遍历序列、根节点、右子树的中序遍历序列

左子树的根 -> 左子树的中序遍历序列
右子树的根 -> 右子树的中序遍历序列

graph TD;
    D(("D"));
    EAF(("EAF"));
    HCBGI(("HCBGI"));
    D-->EAF;
    D-->HCBGI;

graph TD;
    D(("D"));
    A(("A"));
    E(("E"));
    F(("F"));
    B(("B"));
    HC(("HC"));
    GI(("GI"));
    D-->A;
    D-->B;
    A-->E;
    A-->F;
    B-->HC;
    B-->GI;

graph TD;
    D(("D"));
    A(("A"));
    E(("E"));
    F(("F"));
    B(("B"));
    H(("H"));
    C(("C"));
    G(("G"));
    I(("I"));
    D-->A;
    D-->B;
    A-->E;
    A-->F;
    B-->C;
    B-->G;
    C-->H;
    C-->N1(( ));
    G-->N2(( ));
    G-->I;
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    linkStyle 7 stroke:#0ff,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px