# 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=