作者fish0835 (以无用为大用)
看板Grad-ProbAsk
标题Re: [理工] 资结 tree
时间Sat Apr 4 02:09:11 2009
※ 引述《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