class Node
attr_accessor :value, :left, :right
def initialize(val)
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
end
# 描画に必要な情報を計算
def render_info(canvas, margin, node, x, y)
# 左のノードがあれば、そのノード以下の木の横幅を計算
x = render_info(canvas, margin, node.left, x, y + 1) + margin if node.left
# このノードの分の描画に必要な情報(X座標, Y座標, そのもの)を追加
canvas << [x, y, node]
# このノードの桁数を計算
x += node.value.to_s.size
# 右のノードがあれば、そのノード以下の木の横幅を計算
x = render_info(canvas, margin, node.right, x + margin, y + 1) if node.right
# 呼び出した親のために横幅を返す
x
end
# render_infoで描画情報を集めて返す
def render(root, margin=0)
canvas = []
render_info(canvas, margin, root, 0, 0)
canvas
end
# 9
# 4 15
# 2 6 12 17
# このメソッドはクラス外でOK
def print_canvas(canvas)
# X座標よりY座標を優先してソート
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
# y座標が増えたら改行
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
# _9__
# 4 15
# 2 6 12 17
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
# 「次の行の数字で、この数字のすぐ左にあるもの」を探してX座標をとる
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
# 「次の行の数字で、この数字のすぐ右にあるもの」を探してX座標をとる
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
# 9_
# / \
# 4 15
# 2 6 12 17
def print_canvas3(canvas)
# Y座標ごとにグループ分け
canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line.sort }
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 render(tree)
print_canvas2 render(tree)
print_canvas3 render(tree)
print_canvas3 render(Node(4, tree, tree))
print_canvas3 render(Node(4, tree, tree), 2)
print_canvas3 render(Node(4, Node(4), tree), 1)
# バグ: 右手にノードがないと落ちる
print_canvas3 render(Node(4, tree, nil), 1) rescue puts $!
Y2xhc3MgTm9kZQogIGF0dHJfYWNjZXNzb3IgOnZhbHVlLCA6bGVmdCwgOnJpZ2h0CiAgZGVmIGluaXRpYWxpemUodmFsKQogICAgQHZhbHVlID0gdmFsICAgIyDjg47jg7zjg4njgYzkv53mjIHjgZnjgovlgKQKICAgIEBsZWZ0ID0gbmlsICAgICMg5bem5YG044Gu44OO44O844OJCiAgICBAcmlnaHQgPSBuaWwgICAjIOWPs+WBtOOBruODjuODvOODiQogIGVuZAplbmQKIAojIOaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkuioiOeulwpkZWYgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUsIHgsIHkpCiAgIyDlt6bjga7jg47jg7zjg4njgYzjgYLjgozjgbDjgIHjgZ3jga7jg47jg7zjg4nku6XkuIvjga7mnKjjga7mqKrluYXjgpLoqIjnrpcKICB4ID0gcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUubGVmdCwgeCwgeSArIDEpICsgbWFyZ2luIGlmIG5vZGUubGVmdAogCiAgIyDjgZPjga7jg47jg7zjg4njga7liIbjga7mj4/nlLvjgavlv4XopoHjgarmg4XloLEoWOW6p+aomSwgWeW6p+aomSwg44Gd44Gu44KC44GuKeOCkui/veWKoAogIGNhbnZhcyA8PCBbeCwgeSwgbm9kZV0KIAogICMg44GT44Gu44OO44O844OJ44Gu5qGB5pWw44KS6KiI566XCiAgeCArPSBub2RlLnZhbHVlLnRvX3Muc2l6ZQogCiAgIyDlj7Pjga7jg47jg7zjg4njgYzjgYLjgozjgbDjgIHjgZ3jga7jg47jg7zjg4nku6XkuIvjga7mnKjjga7mqKrluYXjgpLoqIjnrpcKICB4ID0gcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUucmlnaHQsIHggKyBtYXJnaW4sIHkgKyAxKSBpZiBub2RlLnJpZ2h0CiAKICAjIOWRvOOBs+WHuuOBl+OBn+imquOBruOBn+OCgeOBq+aoquW5heOCkui/lOOBmQogIHgKZW5kCiAKIyByZW5kZXJfaW5mb+OBp+aPj+eUu+aDheWgseOCkumbhuOCgeOBpui/lOOBmQpkZWYgcmVuZGVyKHJvb3QsIG1hcmdpbj0wKQogIGNhbnZhcyA9IFtdCiAgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIHJvb3QsIDAsIDApCiAgY2FudmFzCmVuZAogCiMgICAgOQojICA0ICAgIDE1CiMgMiA2IDEyICAxNwogCiMg44GT44Gu44Oh44K944OD44OJ44Gv44Kv44Op44K55aSW44GnT0sKZGVmIHByaW50X2NhbnZhcyhjYW52YXMpCiAgIyBY5bqn5qiZ44KI44KKWeW6p+aomeOCkuWEquWFiOOBl+OBpuOCveODvOODiAogIGNhbnZhcyA9IGNhbnZhcy5zb3J0X2J5IHt8eCwgeSwgKnwgW3ksIHhdIH0KIAogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCiAKICAjIOWQhOODjuODvOODieOCkuODq+ODvOODl+OBp+aPj+eUuwogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwogCiAgICAjIHnluqfmqJnjgYzlopfjgYjjgZ/jgonmlLnooYwKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCiAKICAgICMg5b+F6KaB44Gq5YiG44Gg44GR44K544Oa44O844K544KS5YWl44KM44Gm44OX44Oq44Oz44OICiAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgIHByaW50IHRleHQKIAogICAgICAgICMg44Kr44O844K944Or44KS6YCy44KB44KLCiAgICBsYXN0X3ggPSB4ICsgdGV4dC50b19zLnNpemUKICAgIGxhc3RfeSA9IHkKICBlbmQKICBwdXRzCmVuZAogCiMgICBfOV9fCiMgIDQgICAgMTUKIyAyIDYgMTIgIDE3CiAKZGVmIHByaW50X2NhbnZhczIoY2FudmFzKQogIGNhbnZhcyA9IGNhbnZhcy5zb3J0X2J5IHt8eCwgeSwgKnwgW3ksIHhdIH0KIAogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCiAKICAjIOWQhOODjuODvOODieOCkuODq+ODvOODl+OBp+aPj+eUuwogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwogCiAgICBpZiB5ICE9IGxhc3RfeQogICAgICBsYXN0X3ggPSAwCiAgICAgIHB1dHMKICAgIGVuZAogCiAgICBpZiBub2RlLmxlZnQKICAgICAgICMg44CM5qyh44Gu6KGM44Gu5pWw5a2X44Gn44CB44GT44Gu5pWw5a2X44Gu44GZ44GQ5bem44Gr44GC44KL44KC44Gu44CN44KS5o6i44GX44GmWOW6p+aomeOCkuOBqOOCiwogICAgICBpbGVmdCA9IGNhbnZhcy5pbmRleCB7fG54LCBueSwgKnwgeSArIDEgPT0gbnkgJiYgeCA8PSBueCB9IC0gMQogICAgICBsZWZ0X3gsICogPSBjYW52YXNbaWxlZnRdCiAgICAgIGxlZnRfeF9lbmQgPSBsZWZ0X3ggKyBub2RlLmxlZnQudmFsdWUudG9fcy5zaXplCiAgICAgIHByaW50ICIgIiAqIChsZWZ0X3hfZW5kIC0gbGFzdF94KQogICAgICBwcmludCAiXyIgKiAoeCAtIGxlZnRfeF9lbmQpCiAgICBlbHNlCiAgICAgIHByaW50ICIgIiAqICh4IC0gbGFzdF94KQogICAgZW5kCiAKICAgIHByaW50IHRleHQKIAogICAgeCArPSB0ZXh0LnRvX3Muc2l6ZQogCiAgICAjIOaVsOWtl+WPs+WBtOOBruS4i+e3mgogICAgaWYgbm9kZS5yaWdodAogICAgICAjIOOAjOasoeOBruihjOOBruaVsOWtl+OBp+OAgeOBk+OBruaVsOWtl+OBruOBmeOBkOWPs+OBq+OBguOCi+OCguOBruOAjeOCkuaOouOBl+OBpljluqfmqJnjgpLjgajjgosKICAgICAgaXJpZ2h0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0KICAgICAgcmlnaHRfeCwgKiA9IGNhbnZhc1tpcmlnaHRdCiAKICAgICAgcHJpbnQgIl8iICogKHJpZ2h0X3ggLSB4KQogICAgICB4ID0gcmlnaHRfeAogICAgZW5kCiAKICAgIGxhc3RfeCA9IHgKICAgIGxhc3RfeSA9IHkKICBlbmQKICBwdXRzCmVuZAogCiMgICAgOV8KIyAgIC8gIFwKIyAgNCAgICAxNQojIDIgNiAxMiAgMTcKIApkZWYgcHJpbnRfY2FudmFzMyhjYW52YXMpCiAgIyBZ5bqn5qiZ44GU44Go44Gr44Kw44Or44O844OX5YiG44GRCiAgY2FudmFzX2xpbmVzID0gY2FudmFzLmdyb3VwX2J5IHt8eCwgeSwgKnwgeSB9LnNvcnQubWFwIHt8XywgbGluZXwgbGluZS5zb3J0IH0KIAogIGNhbnZhc19saW5lcy5lYWNoIGRvIHxsaW5lfAogICAgIyDmlpznt5rjga7mj4/nlLvjgpLoqJjmhrbjgZfjgabjgYrjgY/phY3liJcKICAgIHNsYXNoZXMgPSBbXQogCiAgICAjIOOBk+OBruihjOOBq+WxnuOBmeaVsOWtl+OCkuaPj+eUu+OBl+OBpuOBhOOBjwogICAgbGFzdF94ID0gMAogICAgbGluZS5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgICB0ZXh0ID0gbm9kZS52YWx1ZS50b19zCiAKICAgICAgIyDmlbDlrZflt6blgbTjga7kuIvnt5oKICAgICAgaWYgbm9kZS5sZWZ0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlsZWZ0ID0gbmV4dF9saW5lLmluZGV4IHt8bngsICp8IHggPD0gbnggfSAtIDEKICAgICAgICBsZWZ0X3gsICogPSBuZXh0X2xpbmVbaWxlZnRdCiAgICAgICAgbGVmdF94X2VuZCA9IGxlZnRfeCArIG5vZGUubGVmdC52YWx1ZS50b19zLnNpemUKICAgICAgICBwcmludCAiICIgKiAobGVmdF94X2VuZCAtIGxhc3RfeCkKICAgICAgICBpZiBsZWZ0X3hfZW5kIDwgeAogICAgICAgICAgIyDkuIvnt5rjga7lt6bnq6/jgpLmrKDjgZHjgZXjgZvjgosgKOOCueODmuODvOOCueOBq+OBmeOCiykKICAgICAgICAgIHByaW50ICIgIgogICAgICAgICAgcHJpbnQgIl8iICogKHggLSBsZWZ0X3hfZW5kIC0gMSkKICAgICAgICAgICMg5pac57ea44Gu5o+P55S744KS5LqI57SEICjlt6bmiYvjg47jg7zjg4njgarjga7jgafjgrnjg6njg4Pjgrfjg6UpCiAgICAgICAgICBzbGFzaGVzIDw8IFtsZWZ0X3hfZW5kLCAnLyddCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgZW5kCiAKICAgICAgcHJpbnQgdGV4dAogCiAgICAgIHggKz0gdGV4dC50b19zLnNpemUKIAogICAgICAjIOaVsOWtl+WPs+WBtOOBruS4i+e3mgogICAgICBpZiBub2RlLnJpZ2h0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlyaWdodCA9IG5leHRfbGluZS5pbmRleCB7fG54LCAqfCB4IDw9IG54IH0KICAgICAgICByaWdodF94LCAqID0gbmV4dF9saW5lW2lyaWdodF0KIAogICAgICAgIGlmIHggPCByaWdodF94CiAgICAgICAgICAjIOS4i+e3muOBruWPs+err+OCkuasoOOBkeOBleOBm+OCiyAo44K544Oa44O844K544Gr44GZ44KLKQogICAgICAgICAgcHJpbnQgIl8iICogKHJpZ2h0X3ggLSB4IC0gMSkKICAgICAgICAgIHByaW50ICIgIgogICAgICAgICAgIyDmlpznt5rjga7mj4/nlLvjgpLkuojntIQgKOWPs+aJi+ODjuODvOODieOBquOBruOBp+ODkOODg+OCr+OCueODqeODg+OCt+ODpSkKICAgICAgICAgIHNsYXNoZXMgPDwgW3JpZ2h0X3ggLSAxLCAnXFwnXQogICAgICAgIGVuZAogICAgICAgIHggPSByaWdodF94CiAgICAgIGVuZAogCiAgICAgIGxhc3RfeCA9IHgKICAgIGVuZAogCiAgICBwdXRzCiAgICAjIOaUueihjOOBl+OBpuaWnOe3muOCkuaPj+eUuwogICAgbGFzdF94ID0gMAogICAgc2xhc2hlcy5lYWNoIGRvIHx4LCBjaGFyfAogICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgcHJpbnQgY2hhcgogICAgICBsYXN0X3ggPSB4ICsgMQogICAgZW5kCiAgICBwdXRzIHVubGVzcyBzbGFzaGVzLmVtcHR5PwogIGVuZAplbmQKIAojIOODhOODquODvOOBruWuo+iogOOCkuefreOBj+abuOOBj+OBn+OCgeOBq+Wumue+qQpkZWYgTm9kZSh2YWwsIGxlZnQ9bmlsLCByaWdodD1uaWwpCiAgbm9kZSA9IE5vZGUubmV3KHZhbCkKICBub2RlLmxlZnQgPSBsZWZ0CiAgbm9kZS5yaWdodCA9IHJpZ2h0CiAgbm9kZQplbmQKIAp0cmVlID0gTm9kZSg5LCBOb2RlKDQsIE5vZGUoMiksIE5vZGUoNikpLCBOb2RlKDE1LCBOb2RlKDEyKSwgTm9kZSgxNykpKQpwcmludF9jYW52YXMgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczIgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczMgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgdHJlZSwgdHJlZSkpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgdHJlZSwgdHJlZSksIDIpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgTm9kZSg0KSwgdHJlZSksIDEpCiAKIyDjg5DjgrA6IOWPs+aJi+OBq+ODjuODvOODieOBjOOBquOBhOOBqOiQveOBoeOCiwpwcmludF9jYW52YXMzIHJlbmRlcihOb2RlKDQsIHRyZWUsIG5pbCksIDEpIHJlc2N1ZSBwdXRzICQh