class Node
attr_accessor :value, :left, :right
def initialize(val)
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
# 描画に必要な情報を計算 (内部用)
def render_info(canvas, margin, x, y)
# 左のノードがあれば、そのノード以下の木の横幅が返ってくる
x = @left.render_info(canvas, margin, x, y + 1) + margin if @left
# このノードの分の描画に必要な情報を追加
canvas << [x, y, self]
# このノードの分の描画に必要な情報を追加
x += @value.to_s.size
x = @right.render_info(canvas, margin, x + margin, y + 1) if @right
# 呼び出した親のために横幅を返す
x
end
protected :render_info
# render_infoで描画情報を集めて返す (外部用)
def render(margin)
canvas = []
render_info(canvas, margin, 0, 0)
canvas
end
end
def print_canvas(canvas)
canvas = canvas.sort_by {|x, y, *| [y, x] }
last_x = 0
last_y = 0
canvas.each do |x, y, node|
text = node.value.to_s
if y != last_y
last_x = 0
puts
end
print " " * (x - last_x)
print text
last_x = x + text.to_s.size
last_y = y
end
puts
end
def print_canvas2(canvas)
canvas = canvas.sort_by {|x, y, *| [y, x] }
last_x = 0
last_y = 0
canvas.each do |x, y, node|
text = node.value.to_s
if y != last_y
last_x = 0
puts
end
if node.left
ileft = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx } - 1
left_x, * = canvas[ileft]
left_x_end = left_x + node.left.value.to_s.size
print " " * (left_x_end - last_x)
print "_" * (x - left_x_end)
else
print " " * (x - last_x)
end
print text
x += text.to_s.size
if node.right
iright = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx }
right_x, * = canvas[iright]
print "_" * (right_x - x)
x = right_x
end
last_x = x
last_y = y
end
puts
end
def print_canvas3(canvas)
canvas = canvas.sort_by {|x, y, *| [y, x] }
canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line }
canvas_lines.each do |line|
slashes = []
last_x = 0
line.each do |x, y, node|
text = node.value.to_s
if node.left
next_line = canvas_lines[y + 1]
ileft = next_line.index {|nx, *| x <= nx } - 1
left_x, * = next_line[ileft]
left_x_end = left_x + node.left.value.to_s.size
print " " * (left_x_end - last_x)
if left_x_end < x
print " "
print "_" * (x - left_x_end - 1)
slashes << [left_x_end, '/']
end
else
print " " * (x - last_x)
end
print text
x += text.to_s.size
if node.right
next_line = canvas_lines[y + 1]
iright = next_line.index {|nx, *| x <= nx }
right_x, * = next_line[iright]
if x < right_x
print "_" * (right_x - x - 1)
print " "
slashes << [right_x - 1, '\\']
end
x = right_x
end
last_x = x
end
puts
last_x = 0
slashes.each do |x, char|
print " " * (x - last_x)
print char
last_x = x + 1
end
puts unless slashes.empty?
end
end
# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
node = Node.new(val)
node.left = left
node.right = right
node
end
tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
print_canvas tree.render(0)
print_canvas2 tree.render(0)
print_canvas2 tree.render(3)
print_canvas3 tree.render(1)
print_canvas3 tree.render(2)
print_canvas3 tree.render(3)
print_canvas3 Node(4, tree, tree).render(0)
print_canvas3 Node(4, tree, tree).render(1)
print_canvas3 Node(4, Node(9, tree, nil), tree).render(2)
print_canvas3 Node(4, tree, tree).render(3)
Y2xhc3MgTm9kZQogIGF0dHJfYWNjZXNzb3IgOnZhbHVlLCA6bGVmdCwgOnJpZ2h0CiAgZGVmIGluaXRpYWxpemUodmFsKQogICAgQHZhbHVlID0gdmFsICAgIyDjg47jg7zjg4njgYzkv53mjIHjgZnjgovlgKQKICAgIEBsZWZ0ID0gbmlsICAgICMg5bem5YG044Gu44OO44O844OJCiAgICBAcmlnaHQgPSBuaWwgICAjIOWPs+WBtOOBruODjuODvOODiQogIGVuZAoKICAjIOaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkuioiOeulyAo5YaF6YOo55SoKQogIGRlZiByZW5kZXJfaW5mbyhjYW52YXMsIG1hcmdpbiwgeCwgeSkKICAgICMg5bem44Gu44OO44O844OJ44GM44GC44KM44Gw44CB44Gd44Gu44OO44O844OJ5Lul5LiL44Gu5pyo44Gu5qiq5bmF44GM6L+U44Gj44Gm44GP44KLCiAgICB4ID0gQGxlZnQucmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIHgsIHkgKyAxKSArIG1hcmdpbiBpZiBAbGVmdAoKICAgICMg44GT44Gu44OO44O844OJ44Gu5YiG44Gu5o+P55S744Gr5b+F6KaB44Gq5oOF5aCx44KS6L+95YqgCiAgICBjYW52YXMgPDwgW3gsIHksIHNlbGZdCgogICAgIyDjgZPjga7jg47jg7zjg4njga7liIbjga7mj4/nlLvjgavlv4XopoHjgarmg4XloLHjgpLov73liqAKICAgIHggKz0gQHZhbHVlLnRvX3Muc2l6ZQogICAgeCA9IEByaWdodC5yZW5kZXJfaW5mbyhjYW52YXMsIG1hcmdpbiwgeCArIG1hcmdpbiwgeSArIDEpIGlmIEByaWdodAoKICAgICMg5ZG844Gz5Ye644GX44Gf6Kaq44Gu44Gf44KB44Gr5qiq5bmF44KS6L+U44GZCiAgICB4CiAgZW5kCiAgcHJvdGVjdGVkIDpyZW5kZXJfaW5mbwoKICAjIHJlbmRlcl9pbmZv44Gn5o+P55S75oOF5aCx44KS6ZuG44KB44Gm6L+U44GZICjlpJbpg6jnlKgpCiAgZGVmIHJlbmRlcihtYXJnaW4pCiAgICBjYW52YXMgPSBbXQogICAgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIDAsIDApCiAgICBjYW52YXMKICBlbmQKZW5kCgoKZGVmIHByaW50X2NhbnZhcyhjYW52YXMpCiAgY2FudmFzID0gY2FudmFzLnNvcnRfYnkge3x4LCB5LCAqfCBbeSwgeF0gfQoKICBsYXN0X3ggPSAwCiAgbGFzdF95ID0gMAoKICBjYW52YXMuZWFjaCBkbyB8eCwgeSwgbm9kZXwKICAgICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwoKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCgogICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICBwcmludCB0ZXh0CgogICAgbGFzdF94ID0geCArIHRleHQudG9fcy5zaXplCiAgICBsYXN0X3kgPSB5CiAgZW5kCiAgcHV0cwplbmQKCmRlZiBwcmludF9jYW52YXMyKGNhbnZhcykKICBjYW52YXMgPSBjYW52YXMuc29ydF9ieSB7fHgsIHksICp8IFt5LCB4XSB9CgogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCgogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwoKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCgogICAgaWYgbm9kZS5sZWZ0CiAgICAgIGlsZWZ0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0gLSAxCiAgICAgIGxlZnRfeCwgKiA9IGNhbnZhc1tpbGVmdF0KICAgICAgbGVmdF94X2VuZCA9IGxlZnRfeCArIG5vZGUubGVmdC52YWx1ZS50b19zLnNpemUKICAgICAgcHJpbnQgIiAiICogKGxlZnRfeF9lbmQgLSBsYXN0X3gpCiAgICAgIHByaW50ICJfIiAqICh4IC0gbGVmdF94X2VuZCkKICAgIGVsc2UKICAgICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICBlbmQKCiAgICBwcmludCB0ZXh0CgogICAgeCArPSB0ZXh0LnRvX3Muc2l6ZQoKICAgIGlmIG5vZGUucmlnaHQKICAgICAgaXJpZ2h0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0KICAgICAgcmlnaHRfeCwgKiA9IGNhbnZhc1tpcmlnaHRdCgogICAgICBwcmludCAiXyIgKiAocmlnaHRfeCAtIHgpCiAgICAgIHggPSByaWdodF94CiAgICBlbmQKCiAgICBsYXN0X3ggPSB4CiAgICBsYXN0X3kgPSB5CiAgZW5kCiAgcHV0cwplbmQKCmRlZiBwcmludF9jYW52YXMzKGNhbnZhcykKICBjYW52YXMgPSBjYW52YXMuc29ydF9ieSB7fHgsIHksICp8IFt5LCB4XSB9CiAgY2FudmFzX2xpbmVzID0gY2FudmFzLmdyb3VwX2J5IHt8eCwgeSwgKnwgeSB9LnNvcnQubWFwIHt8XywgbGluZXwgbGluZSB9CgogIGNhbnZhc19saW5lcy5lYWNoIGRvIHxsaW5lfAogICAgc2xhc2hlcyA9IFtdCgogICAgbGFzdF94ID0gMAogICAgbGluZS5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgICB0ZXh0ID0gbm9kZS52YWx1ZS50b19zCgogICAgICBpZiBub2RlLmxlZnQKICAgICAgICBuZXh0X2xpbmUgPSBjYW52YXNfbGluZXNbeSArIDFdCiAgICAgICAgaWxlZnQgPSBuZXh0X2xpbmUuaW5kZXgge3xueCwgKnwgeCA8PSBueCB9IC0gMQogICAgICAgIGxlZnRfeCwgKiA9IG5leHRfbGluZVtpbGVmdF0KICAgICAgICBsZWZ0X3hfZW5kID0gbGVmdF94ICsgbm9kZS5sZWZ0LnZhbHVlLnRvX3Muc2l6ZQogICAgICAgIHByaW50ICIgIiAqIChsZWZ0X3hfZW5kIC0gbGFzdF94KQogICAgICAgIGlmIGxlZnRfeF9lbmQgPCB4CiAgICAgICAgICBwcmludCAiICIKICAgICAgICAgIHByaW50ICJfIiAqICh4IC0gbGVmdF94X2VuZCAtIDEpCiAgICAgICAgICBzbGFzaGVzIDw8IFtsZWZ0X3hfZW5kLCAnLyddCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgZW5kCgogICAgICBwcmludCB0ZXh0CgogICAgICB4ICs9IHRleHQudG9fcy5zaXplCgogICAgICBpZiBub2RlLnJpZ2h0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlyaWdodCA9IG5leHRfbGluZS5pbmRleCB7fG54LCAqfCB4IDw9IG54IH0KICAgICAgICByaWdodF94LCAqID0gbmV4dF9saW5lW2lyaWdodF0KCiAgICAgICAgaWYgeCA8IHJpZ2h0X3gKICAgICAgICAgIHByaW50ICJfIiAqIChyaWdodF94IC0geCAtIDEpCiAgICAgICAgICBwcmludCAiICIKICAgICAgICAgIHNsYXNoZXMgPDwgW3JpZ2h0X3ggLSAxLCAnXFwnXQogICAgICAgIGVuZAogICAgICAgIHggPSByaWdodF94CiAgICAgIGVuZAoKICAgICAgbGFzdF94ID0geAogICAgZW5kCgogICAgcHV0cwoKICAgIGxhc3RfeCA9IDAKICAgIHNsYXNoZXMuZWFjaCBkbyB8eCwgY2hhcnwKICAgICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICAgIHByaW50IGNoYXIKICAgICAgbGFzdF94ID0geCArIDEKICAgIGVuZAogICAgcHV0cyB1bmxlc3Mgc2xhc2hlcy5lbXB0eT8KICBlbmQKZW5kCgojIOODhOODquODvOOBruWuo+iogOOCkuefreOBj+abuOOBj+OBn+OCgeOBq+Wumue+qQpkZWYgTm9kZSh2YWwsIGxlZnQ9bmlsLCByaWdodD1uaWwpCiAgbm9kZSA9IE5vZGUubmV3KHZhbCkKICBub2RlLmxlZnQgPSBsZWZ0CiAgbm9kZS5yaWdodCA9IHJpZ2h0CiAgbm9kZQplbmQKCnRyZWUgPSBOb2RlKDksIE5vZGUoNCwgTm9kZSgyKSwgTm9kZSg2KSksIE5vZGUoMTUsIE5vZGUoMTIpLCBOb2RlKDE3KSkpCnByaW50X2NhbnZhcyB0cmVlLnJlbmRlcigwKQpwcmludF9jYW52YXMyIHRyZWUucmVuZGVyKDApCnByaW50X2NhbnZhczIgdHJlZS5yZW5kZXIoMykKcHJpbnRfY2FudmFzMyB0cmVlLnJlbmRlcigxKQpwcmludF9jYW52YXMzIHRyZWUucmVuZGVyKDIpCnByaW50X2NhbnZhczMgdHJlZS5yZW5kZXIoMykKcHJpbnRfY2FudmFzMyBOb2RlKDQsIHRyZWUsIHRyZWUpLnJlbmRlcigwKQpwcmludF9jYW52YXMzIE5vZGUoNCwgdHJlZSwgdHJlZSkucmVuZGVyKDEpCnByaW50X2NhbnZhczMgTm9kZSg0LCBOb2RlKDksIHRyZWUsIG5pbCksIHRyZWUpLnJlbmRlcigyKQpwcmludF9jYW52YXMzIE5vZGUoNCwgdHJlZSwgdHJlZSkucmVuZGVyKDMpCg==