# print_canvas3のバグを修正して整理しました
class Node
attr_accessor :value, :left, :right
def initialize(val)
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
end
# 描画位置の決まったノード
RenderedNode = Struct.new(:x, :y, :node) do
# ノードの描画に必要な幅
def width
node.value.to_s.size
end
end
# 各ノードの位置を計算する
class Renderer
def initialize(margin=0)
@margin = margin
end
# render_infoで描画情報を集めて返す (外部用)
def render(root)
@nodes = []
render_info(root, 0, 0)
@nodes
end
private
# 描画に必要な情報を計算 (内部用)
def render_info(node, x, y)
# 左のノードがあれば、そのノード以下の木の横幅が返ってくる
x = render_info(node.left, x, y + 1) + @margin if node.left
# このノードの分の描画に必要な情報を追加
@nodes << RenderedNode.new(x, y, node)
# このノードの分の描画に必要な情報を追加
x += node.value.to_s.size
x = render_info(node.right, x + @margin, y + 1) if node.right
# 呼び出した親のために横幅を返す
x
end
end
# Rendererの返した座標データから二分木のAAを表示する
class Printer
# コンストラクタで座標データをうけとる
def initialize(nodes)
@lines = group_by_line(nodes)
@slashes = nil
end
# 旧print_canvas
def run
@slashes = []
@lines.each do |line|
print_numbers(line)
print_slashes
@slashes.clear
end
end
private
# 座標データを行ごとにグループ分け
def group_by_line(nodes)
nodes.group_by {|n| n.y }.sort.map {|_, line| line.sort_by {|n| n.x } }
end
# 数字と下線からなる行の表示
def print_numbers(line)
last_x = 0
line.each do |n|
x = print_left_space(n, last_x)
x = print_node(n, x)
x = print_right_space(n, x)
last_x = x
end
puts
end
# 数字左の空白と下線の表示
# 右端の座標(現在のカーソル位置)を返す
def print_left_space(n, last_x)
x = n.x
if left_child = find_left_child(n)
left_x_end = left_child.x + left_child.width
print " " * (left_x_end - last_x)
if left_x_end < x
print " ", "_" * (x - left_x_end - 1)
# 斜線の描画を予約 (左手ノードなのでスラッシュ)
@slashes << [left_x_end, '/']
end
else
print " " * (x - last_x)
end
x
end
# 数字本体の表示
# 右端の座標(現在のカーソル位置)を返す
def print_node(n, x)
print n.node.value
x + n.width
end
# 数字右の空白と下線の表示
# 右端の座標(現在のカーソル位置)を返す
def print_right_space(n, x)
if right_child = find_right_child(n)
right_x = right_child.x
if x < right_x
print "_" * (right_x - x - 1), " "
# 斜線の描画を予約 (右手ノードなのでバックスラッシュ)
@slashes << [right_x - 1, '\\']
end
x = right_x
end
x
end
# 斜線からなる行の表示
def print_slashes
last_x = 0
@slashes.each do |x, char|
print " " * (x - last_x)
print char
last_x = x + 1
end
puts unless @slashes.empty?
end
# 右手の子ノードを探す
def find_right_child(n)
@lines[n.y + 1][index_right_child(n)] if n.node.right
end
# 左手の子ノードを探す
def find_left_child(n)
if n.node.left
next_line = @lines[n.y + 1]
# * バグ修正部分 *
# 右手のノードを探してからそのすぐ左を取る方法なので
# 右手にノードがない場合に失敗する
i = index_right_child(n)
if i
next_line[i - 1]
else
next_line.last
end
end
end
# 右手の子ノードの添字を見つける
def index_right_child(n)
next_line = @lines[n.y + 1]
next_line.index {|m| n.x <= m.x }
end
end
# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
node = Node.new(val)
node.left = left
node.right = right
node
end
# AAを描画
def draw_tree(root_node, margin)
nodes = Renderer.new(margin).render(root_node)
Printer.new(nodes).run
end
tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
draw_tree Node(4, tree, Node(3, tree, nil)), 1
__END__
_________4_________________
/ \
__9___ _________3
/ \ /
4 15 __9___
/ \ / \ / \
2 6 12 17 4 15
/ \ / \
2 6 12 17
IyBwcmludF9jYW52YXMz44Gu44OQ44Kw44KS5L+u5q2j44GX44Gm5pW055CG44GX44G+44GX44GfCmNsYXNzIE5vZGUKICBhdHRyX2FjY2Vzc29yIDp2YWx1ZSwgOmxlZnQsIDpyaWdodAogIGRlZiBpbml0aWFsaXplKHZhbCkKICAgIEB2YWx1ZSA9IHZhbCAgICMg44OO44O844OJ44GM5L+d5oyB44GZ44KL5YCkCiAgICBAbGVmdCA9IG5pbCAgICAjIOW3puWBtOOBruODjuODvOODiQogICAgQHJpZ2h0ID0gbmlsICAgIyDlj7PlgbTjga7jg47jg7zjg4kKICBlbmQKZW5kCiAKIyDmj4/nlLvkvY3nva7jga7msbrjgb7jgaPjgZ/jg47jg7zjg4kKUmVuZGVyZWROb2RlID0gU3RydWN0Lm5ldyg6eCwgOnksIDpub2RlKSBkbwogICMg44OO44O844OJ44Gu5o+P55S744Gr5b+F6KaB44Gq5bmFCiAgZGVmIHdpZHRoCiAgICBub2RlLnZhbHVlLnRvX3Muc2l6ZQogIGVuZAplbmQKIAojIOWQhOODjuODvOODieOBruS9jee9ruOCkuioiOeul+OBmeOCiwpjbGFzcyBSZW5kZXJlcgogIGRlZiBpbml0aWFsaXplKG1hcmdpbj0wKQogICAgQG1hcmdpbiA9IG1hcmdpbgogIGVuZAogCiAgIyByZW5kZXJfaW5mb+OBp+aPj+eUu+aDheWgseOCkumbhuOCgeOBpui/lOOBmSAo5aSW6YOo55SoKQogIGRlZiByZW5kZXIocm9vdCkKICAgIEBub2RlcyA9IFtdCiAgICByZW5kZXJfaW5mbyhyb290LCAwLCAwKQogICAgQG5vZGVzCiAgZW5kCiAKICBwcml2YXRlCiAKICAjIOaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkuioiOeulyAo5YaF6YOo55SoKQogIGRlZiByZW5kZXJfaW5mbyhub2RlLCB4LCB5KQogICAgIyDlt6bjga7jg47jg7zjg4njgYzjgYLjgozjgbDjgIHjgZ3jga7jg47jg7zjg4nku6XkuIvjga7mnKjjga7mqKrluYXjgYzov5TjgaPjgabjgY/jgosKICAgIHggPSByZW5kZXJfaW5mbyhub2RlLmxlZnQsIHgsIHkgKyAxKSArIEBtYXJnaW4gaWYgbm9kZS5sZWZ0CiAKICAgICMg44GT44Gu44OO44O844OJ44Gu5YiG44Gu5o+P55S744Gr5b+F6KaB44Gq5oOF5aCx44KS6L+95YqgCiAgICBAbm9kZXMgPDwgUmVuZGVyZWROb2RlLm5ldyh4LCB5LCBub2RlKQogCiAgICAjIOOBk+OBruODjuODvOODieOBruWIhuOBruaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkui/veWKoAogICAgeCArPSBub2RlLnZhbHVlLnRvX3Muc2l6ZQogICAgeCA9IHJlbmRlcl9pbmZvKG5vZGUucmlnaHQsIHggKyBAbWFyZ2luLCB5ICsgMSkgaWYgbm9kZS5yaWdodAogCiAgICAjIOWRvOOBs+WHuuOBl+OBn+imquOBruOBn+OCgeOBq+aoquW5heOCkui/lOOBmQogICAgeAogIGVuZAplbmQKIAojIFJlbmRlcmVy44Gu6L+U44GX44Gf5bqn5qiZ44OH44O844K/44GL44KJ5LqM5YiG5pyo44GuQUHjgpLooajnpLrjgZnjgosKY2xhc3MgUHJpbnRlcgogICMg44Kz44Oz44K544OI44Op44Kv44K/44Gn5bqn5qiZ44OH44O844K/44KS44GG44GR44Go44KLCiAgZGVmIGluaXRpYWxpemUobm9kZXMpCiAgICBAbGluZXMgPSBncm91cF9ieV9saW5lKG5vZGVzKQogICAgQHNsYXNoZXMgPSBuaWwKICBlbmQKIAogICMg5pencHJpbnRfY2FudmFzCiAgZGVmIHJ1bgogICAgQHNsYXNoZXMgPSBbXQogICAgQGxpbmVzLmVhY2ggZG8gfGxpbmV8CiAgICAgIHByaW50X251bWJlcnMobGluZSkKICAgICAgcHJpbnRfc2xhc2hlcwogICAgICBAc2xhc2hlcy5jbGVhcgogICAgZW5kCiAgZW5kCiAKICBwcml2YXRlCiAKICAjIOW6p+aomeODh+ODvOOCv+OCkuihjOOBlOOBqOOBq+OCsOODq+ODvOODl+WIhuOBkQogIGRlZiBncm91cF9ieV9saW5lKG5vZGVzKQogICAgbm9kZXMuZ3JvdXBfYnkge3xufCBuLnkgfS5zb3J0Lm1hcCB7fF8sIGxpbmV8IGxpbmUuc29ydF9ieSB7fG58IG4ueCB9IH0KICBlbmQKICAKICAjIOaVsOWtl+OBqOS4i+e3muOBi+OCieOBquOCi+ihjOOBruihqOekugogIGRlZiBwcmludF9udW1iZXJzKGxpbmUpCiAgICBsYXN0X3ggPSAwCiAgICAKICAgIGxpbmUuZWFjaCBkbyB8bnwKICAgICAgeCA9IHByaW50X2xlZnRfc3BhY2UobiwgbGFzdF94KQogICAgICB4ID0gcHJpbnRfbm9kZShuLCB4KQogICAgICB4ID0gcHJpbnRfcmlnaHRfc3BhY2UobiwgeCkKICAgICAgbGFzdF94ID0geAogICAgZW5kCiAgICAKICAgIHB1dHMKICBlbmQKIAogICMg5pWw5a2X5bem44Gu56m655m944Go5LiL57ea44Gu6KGo56S6CiAgIyDlj7Pnq6/jga7luqfmqJko54++5Zyo44Gu44Kr44O844K944Or5L2N572uKeOCkui/lOOBmQogIGRlZiBwcmludF9sZWZ0X3NwYWNlKG4sIGxhc3RfeCkKICAgIHggPSBuLngKICAgIAogICAgaWYgbGVmdF9jaGlsZCA9IGZpbmRfbGVmdF9jaGlsZChuKQogICAgICBsZWZ0X3hfZW5kID0gbGVmdF9jaGlsZC54ICsgbGVmdF9jaGlsZC53aWR0aAogICAgICAKICAgICAgcHJpbnQgIiAiICogKGxlZnRfeF9lbmQgLSBsYXN0X3gpCiAgICAgIGlmIGxlZnRfeF9lbmQgPCB4CiAgICAgICAgcHJpbnQgIiAiLCAiXyIgKiAoeCAtIGxlZnRfeF9lbmQgLSAxKQogICAgICAgIAogICAgICAgICMg5pac57ea44Gu5o+P55S744KS5LqI57SEICjlt6bmiYvjg47jg7zjg4njgarjga7jgafjgrnjg6njg4Pjgrfjg6UpCiAgICAgICAgQHNsYXNoZXMgPDwgW2xlZnRfeF9lbmQsICcvJ10KICAgICAgZW5kCiAgICBlbHNlCiAgICAgIHByaW50ICIgIiAqICh4IC0gbGFzdF94KQogICAgZW5kCiAgICAKICAgIHgKICBlbmQKICAKICAjIOaVsOWtl+acrOS9k+OBruihqOekugogICMg5Y+z56uv44Gu5bqn5qiZKOePvuWcqOOBruOCq+ODvOOCveODq+S9jee9rinjgpLov5TjgZkKICBkZWYgcHJpbnRfbm9kZShuLCB4KQogICAgcHJpbnQgbi5ub2RlLnZhbHVlCiAgICB4ICsgbi53aWR0aAogIGVuZAogIAogICMg5pWw5a2X5Y+z44Gu56m655m944Go5LiL57ea44Gu6KGo56S6CiAgIyDlj7Pnq6/jga7luqfmqJko54++5Zyo44Gu44Kr44O844K944Or5L2N572uKeOCkui/lOOBmQogIGRlZiBwcmludF9yaWdodF9zcGFjZShuLCB4KQogICAgaWYgcmlnaHRfY2hpbGQgPSBmaW5kX3JpZ2h0X2NoaWxkKG4pCiAgICAgIHJpZ2h0X3ggPSByaWdodF9jaGlsZC54CiAgICAgIGlmIHggPCByaWdodF94CiAgICAgICAgcHJpbnQgIl8iICogKHJpZ2h0X3ggLSB4IC0gMSksICIgIgogICAgICAgIAogICAgICAgICMg5pac57ea44Gu5o+P55S744KS5LqI57SEICjlj7PmiYvjg47jg7zjg4njgarjga7jgafjg5Djg4Pjgq/jgrnjg6njg4Pjgrfjg6UpCiAgICAgICAgQHNsYXNoZXMgPDwgW3JpZ2h0X3ggLSAxLCAnXFwnXQogICAgICBlbmQKICAgICAgeCA9IHJpZ2h0X3gKICAgIGVuZAogICAgeAogIGVuZAogCiAgIyDmlpznt5rjgYvjgonjgarjgovooYzjga7ooajnpLoKICBkZWYgcHJpbnRfc2xhc2hlcwogICAgbGFzdF94ID0gMAogICAgQHNsYXNoZXMuZWFjaCBkbyB8eCwgY2hhcnwKICAgICAgcHJpbnQgIiAiICogKHggLSBsYXN0X3gpCiAgICAgIHByaW50IGNoYXIKICAgICAgbGFzdF94ID0geCArIDEKICAgIGVuZAogICAgcHV0cyB1bmxlc3MgQHNsYXNoZXMuZW1wdHk/CiAgZW5kCiAgCiAgIyDlj7PmiYvjga7lrZDjg47jg7zjg4njgpLmjqLjgZkKICBkZWYgZmluZF9yaWdodF9jaGlsZChuKQogICAgQGxpbmVzW24ueSArIDFdW2luZGV4X3JpZ2h0X2NoaWxkKG4pXSBpZiBuLm5vZGUucmlnaHQKICBlbmQKIAogICMg5bem5omL44Gu5a2Q44OO44O844OJ44KS5o6i44GZCiAgZGVmIGZpbmRfbGVmdF9jaGlsZChuKQogICAgaWYgbi5ub2RlLmxlZnQKICAgICAgbmV4dF9saW5lID0gQGxpbmVzW24ueSArIDFdCiAgICAgIAogICAgICAjICog44OQ44Kw5L+u5q2j6YOo5YiGICoKICAgICAgIyDlj7PmiYvjga7jg47jg7zjg4njgpLmjqLjgZfjgabjgYvjgonjgZ3jga7jgZnjgZDlt6bjgpLlj5bjgovmlrnms5Xjgarjga7jgacKICAgICAgIyDlj7PmiYvjgavjg47jg7zjg4njgYzjgarjgYTloLTlkIjjgavlpLHmlZfjgZnjgosKICAgICAgaSA9IGluZGV4X3JpZ2h0X2NoaWxkKG4pCiAgICAgIGlmIGkKICAgICAgICBuZXh0X2xpbmVbaSAtIDFdCiAgICAgIGVsc2UKICAgICAgICBuZXh0X2xpbmUubGFzdAogICAgICBlbmQKICAgIGVuZAogIGVuZAogCiAgIyDlj7PmiYvjga7lrZDjg47jg7zjg4njga7mt7vlrZfjgpLopovjgaTjgZHjgosKICBkZWYgaW5kZXhfcmlnaHRfY2hpbGQobikKICAgIG5leHRfbGluZSA9IEBsaW5lc1tuLnkgKyAxXQogICAgbmV4dF9saW5lLmluZGV4IHt8bXwgbi54IDw9IG0ueCB9IAogIGVuZAplbmQKIAojIOODhOODquODvOOBruWuo+iogOOCkuefreOBj+abuOOBj+OBn+OCgeOBq+Wumue+qQpkZWYgTm9kZSh2YWwsIGxlZnQ9bmlsLCByaWdodD1uaWwpCiAgbm9kZSA9IE5vZGUubmV3KHZhbCkKICBub2RlLmxlZnQgPSBsZWZ0CiAgbm9kZS5yaWdodCA9IHJpZ2h0CiAgbm9kZQplbmQKIAojIEFB44KS5o+P55S7CmRlZiBkcmF3X3RyZWUocm9vdF9ub2RlLCBtYXJnaW4pCiAgbm9kZXMgPSBSZW5kZXJlci5uZXcobWFyZ2luKS5yZW5kZXIocm9vdF9ub2RlKQogIFByaW50ZXIubmV3KG5vZGVzKS5ydW4KZW5kCiAKdHJlZSA9IE5vZGUoOSwgTm9kZSg0LCBOb2RlKDIpLCBOb2RlKDYpKSwgTm9kZSgxNSwgTm9kZSgxMiksIE5vZGUoMTcpKSkKZHJhd190cmVlIE5vZGUoNCwgdHJlZSwgTm9kZSgzLCB0cmVlLCBuaWwpKSwgMQogCl9fRU5EX18KICAgICAgICBfX19fX19fX180X19fX19fX19fX19fX19fX18KICAgICAgIC8gICAgICAgICAgICAgICAgICAgICAgICAgICBcCiAgICBfXzlfX18gICAgICAgICAgICAgICAgIF9fX19fX19fXzMKICAgLyAgICAgIFwgICAgICAgICAgICAgICAvCiAgNCAgICAgICAgMTUgICAgICAgICAgX185X19fCiAvIFwgICAgICAvICBcICAgICAgICAvICAgICAgXAoyICAgNiAgIDEyICAgIDE3ICAgICA0ICAgICAgICAxNQogICAgICAgICAgICAgICAgICAgIC8gXCAgICAgIC8gIFwKICAgICAgICAgICAgICAgICAgIDIgICA2ICAgMTIgICAgMTc=