변경이력

돌아가기
3 558개 문자 추가 589개 문자 삭제

2016/11/22 21:54

권용훈

**Ruby** in-order 순회(LUR순서)를 따라 좌측순회를 마친 뒤 L,U 노드의 x값 계산, R순회 전에 R의 x를 계산함. 노드자신과 부모노드 두 가지 조건(정확히는 par&.x와 좌측순회를 마친 뒤 L(node.x), U(node.x), R(node.l&r.x) 에 의해 계산식 달리 적용순서로 x 계산. ```{.ruby} add = ->par,node do par ? node.y = par.y + 1 : (return node) chd = node.val < par.val ? par.l : par.r chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node) par end btree_info = ->tree_str do Node = Struct.new(:val, :x, :y, :l, :r) nodes = tree_str.chars.map {|c| Node.new(c, 0, 1)} btree = nodes.reduce(&add) [btree, nodes.max_by(&:y).y] end anal_x = ->par,node,max_y do if par&.x.nil? or (node.l && node.l.x > 0) calc_x = ->node,par,max_y do left_x = par.x + 2**(max_y-node.y) * (node == par.l ? -1 : 1) if par node.x = (node.l ? node.l.x + 2**(max_y-node.y-1) elsif : par&.x ==> 0 && node.l.nil? ? left_x : 1) elsif par&.x > 0 par.x + 2**(max_y-node.y) * (node == par.r ? 1 : -1) endnode.r.x = node.x + 2**(max_y-node.y-1) if node.r end layout = ->tree_str=gets.chop do btree, max_yNode = Struct.new(:val, :x, :y, :l, :r) nodes = btree_info[tree_str]str.chars.map {|c| Node.new(c, 0, 1) } btree, max_y = nodes.reduce(&add), nodes.max_by(&:y).y trav = ->node,par=nil do trav[node.l, node] if node.l node.x = ancalc_x[par, nodenode, par, max_y] puts node.values[0..2].join(" ") (node.r.x = node.x + 2**(max_y-node.y-1); trav[node.r, node]) if node.r end trav[btree] end ``` **Test** ```{.ruby} in_ordered = "a 1 4\n" + "c 3 3\n" + "d 4 5\n" + "e 5 4\n" + "g 6 5\n" + "k 7 2\n" + "m 11 3\n" + "n 15 1\n" + "p 19 3\n" + "q 21 4\n" + "u 23 2\n" expect{ layout["nkcmaedgupq"] }.to output(in_ordered).to_stdout ``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 3 3 d 4 5 e 5 4 g 6 5 k 7 2 m 11 3 n 15 1 p 19 3 q 21 4 u 23 2 ```
**Ruby** in-order 순회(LUR순서)를 따라 좌측순회를 마친 뒤 L,U 노드의 x값 계산, R순회 전에 R의 x를 계산함. 노드자신과 부모노드 두 가지 조건(정확히는 par&.x와 좌측순회를 마친 뒤 L(node.x), U(node.x), R(node.l&r.x) 에 의해 계산식 달리 적용순서로 x 계산. ```{.ruby} add = ->par,node do par ? node.y = par.y + 1 : (return node) chd = node.val < par.val ? par.l : par.r chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node) par end btree_info = ->tree_str do Node = Struct.new(:val, :x, :y, :l, :r) nodes = tree_str.chars.map {|c| Node.new(c, 0, 1)} btree = nodes.reduce(&add) [btree, nodes.max_by(&:y).y] end anal_x = ->par,node,max_y do if par&.x.nil? or (node.l && node.l.x > 0) calc_x = ->node,par,max_y do left_x = par.x + 2**(max_y-node.y) * (node == par.l ? -1 : 1) if par node.x = (node.l ? node.l.x + 2**(max_y-node.y-1) elsif : par&.x ==> 0 && node.l.nil? ? left_x : 1) elsif par&.x > 0 par.x + 2**(max_y-node.y) * (node == par.r ? 1 : -1) endnode.r.x = node.x + 2**(max_y-node.y-1) if node.r end layout = ->tree_str=gets.chop do btree, max_yNode = Struct.new(:val, :x, :y, :l, :r) nodes = btree_info[tree_str]str.chars.map {|c| Node.new(c, 0, 1) } btree, max_y = nodes.reduce(&add), nodes.max_by(&:y).y trav = ->node,par=nil do trav[node.l, node] if node.l node.x = ancalc_x[par, nodenode, par, max_y] puts node.values[0..2].join(" ") (node.r.x = node.x + 2**(max_y-node.y-1); trav[node.r, node]) if node.r end trav[btree] end ``` **Test** ```{.ruby} in_ordered = "a 1 4\n" + "c 3 3\n" + "d 4 5\n" + "e 5 4\n" + "g 6 5\n" + "k 7 2\n" + "m 11 3\n" + "n 15 1\n" + "p 19 3\n" + "q 21 4\n" + "u 23 2\n" expect{ layout["nkcmaedgupq"] }.to output(in_ordered).to_stdout ``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 3 3 d 4 5 e 5 4 g 6 5 k 7 2 m 11 3 n 15 1 p 19 3 q 21 4 u 23 2 ```
2 5개 문자 추가 93개 문자 삭제

2016/11/21 04:27

권용훈

1 Original

2016/11/21 04:22

권용훈

코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.