Re: [理工] [資結]-postorder和preorder

[fef92 (濃妝短裙騙不倒我的)]

※ 引述《fj90406 (阿亮)》之銘言：
:  preorder:9,8,6,1,4,7,5,3,2
: postorder:1,4,6,7,8,3,2,5,9
: (a)Draw binary tree
: (b)Is tree unique? why?

  第一篇題目抄錯整個錯了 0rz

              9
            /   \
           8     5
          / \   / \
         6   7 3   2
        / \
       1   4               本題是唯一的

   pre : ABC    post : CBA   這樣的情況才會有多個binary tree

        A      A     A       A
       /      /       \       \
      B      B        B        B
     /        \      /         \
    C          C    C           C     這4種   ABC可看成子樹  遞迴去看

   本題為整個為  pre : ABC   post : BCA  這種情況就能決定唯一的binary tree

               {9}{86147}{532}            {14678}{325}{9}
                  /         \               /       \
           {8}{614}{7}   {5}{3}{2}   {146}{7}{8}   {3}{2}{5}
                /                      /
            {6}{1}{4}              {1}{4}{6}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.209.5
※ 編輯: fef92           來自: 114.43.209.5         (03/05 19:39)
※ 編輯: fef92           來自: 114.43.209.5         (03/05 19:46)
推 stevenwin:你講得沒錯
→ chris750630:感謝
推 fj90406:打成這樣應該花了不少時間吧...  非常謝謝你的解說!!
→ skipandsnow:以9為頂點其餘點分別放左子樹就可以變化成恨多種樹了
→ skipandsnow:怎麼會是唯一呢...只有INORDER與POSTORDER才能決定唯
→ skipandsnow:一的BINARY TREE
→ skipandsnow:毆!我錯了 大哥是對的!