Re: [理工] 資結 tree

[fish0835 (以無用為大用)]

※ 引述《walks (蹦蹦跳跳)》之銘言：
: The following lists are the traverse orders of a binary search:
: ˙preorder: 6,7,4,8,5,2,3,1,9,11,10,13,12
: ˙inorder:8,4,5,7,2,6,9,1,11,3,13,10,12
: 我只有推得 root 6
: 然後  4
:      /
:     8
: 其他不敢確定   ~"~

rule: 先由preorder找出root，再由inorder找出左右子樹的data

steps :

1.
preorder: "6"(7,4,8,5,2)(3,1,9,11,10,13,12)
inorder:  (8,4,5,7,2)"6"(9,1,11,3,13,10,12)

可知tree為

              6
            /   \
  (8,4,5,7,2)   (9,1,11,3,13,10,12)

2.

preorder: 6("7"(4,8,5)(2))("3"(1,9,11)(10,13,12))
inorder:  ((8,4,5)"7"(2))6((9,1,11)"3"(13,10,12))

可知tree為

                  6
              /      \
           7            3
         /   \       /     \
      (8,4,5)  2 (9,1,11)   (13,10,12)

3.

preorder: 6(7("4"(8)(5))(2))(3("1"(9)(11))("10"(13)(12)))
inorder:  (((8)"4"(5))7(2))6(((9)"1"(11))3((13)"10"(12)))

可知tree為

                 6
              /     \
            7         3
          /   \     /   \
        4     2    1      10
       /  \       / \     /  \
      8    5     9   11  13   12

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.229.77.190