回覆列表
  • 1 # 使用者1943641456485

    假設某二叉樹的先序遍歷序列是abdgcefh,中序遍歷序列是dgbaechf,畫出二叉樹,並給出其後序遍歷序列。

    分析過程:

    以下面的例題為例進行講解:

    已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別是abdgcefh、dgbaechf,求二叉樹及後序遍歷序列。

    分析:先序遍歷序列的第一個字元為根結點。對於中序遍歷,根結點在中序遍歷序列的中間,左邊部分是根結點的左子樹的中序遍歷序列,右邊部分是根結點的右子樹的中序遍歷序列。

    先序:abdgcefh --> a bdg cefh

    中序:dgbaechf --> dgb a echf

    得出結論:a是樹根,a有左子樹和右子樹,左子樹有bdg結點,右子樹有cefh結點。

    先序:bdg --> b dg

    中序:dgb --> dg b

    得出結論:b是左子樹的根結點,b無右子樹,有左子樹。

    先序:dg --> d g

    中序:dg --> d g

    得出結論:d是b的左子樹的根結點,d無左子樹,有右子樹。

    先序:cefh --> c e fh

    中序:echf --> e c hf

    得出結論:c是右子樹的根結點,c有左子樹(只有e結點),有右子樹(有fh結點)。

    先序:fh --> f h

    中序:hf --> h f

    得出結論:f是c的右子樹的根結點,f有左子樹(只有h結點),無右子樹。

    還原二叉樹為:

    a

    b c

    d e f

    g h

    後序遍歷序列:gdbehfca

  • 中秋節和大豐收的關聯?
  • 比埃拉戴帽,張稀哲點射!國安4-1勝一方,7連勝破紀錄。如何評價國安本場的表現?