2 分木を ascii art で表示する方法は?


2 分木を ascii art で表示するには、どのようにプログラムを組めばよいですか？  
(ruby での回答が望みですが、他の言語でも可です)

出力イメージ：（あくまでイメージ。これと異なっていても構いません。）

[code]

         __9__
        /     \
       4       15
      /\      / \
     2  6    12  17
    
[/code]

2 分木の操作プログラム例が以下にあります。このコード中での tree 表示結果を上のようなものにしたいのです。  
[２分木へのデータの追加について](https://ja.stackoverflow.com/questions/4704) 中の回答例  
[２分木のデータ追加、サーチ、削除について](https://ja.stackoverflow.com/questions/4721) 中の回答例

追記: (2015-01-21)

次のような偏った木の時に, なるべく 表示の横幅を最小にするには ?  
( 頂点の 10 より左に 15 のような node の水平位置が左になるように詰められるケースがあり得るハズ)

[code]

           10  
          / \  
         9   19  
        /   /  
        8   18  
       /   /  
       7   17  
      /   /  
      6   16  
     /   /  
     5   15  
    
[/code]

追記： (2015-01-18)

  * 次のページを見つけた。詳細を検討中 ...  
・ [Print a Binary
Tree](https://codegolf.stackexchange.com/questions/849/print-a-binary-
tree/42633#42633)  
・ [How to print binary tree
diagram?](https://stackoverflow.com/questions/4965335/)

  * 表示向きは縦、ノードを結ぶ線の表示は必須条件とします。  
ノード値の桁数は最大２桁までに制限しても構いません。(4桁程度まで対応できるのが望ましいけど)

私自身としては、tree の深さ(たとえば 4)をあたえたら以下のような出力をえられる方法が作成できれば、それを元にして x
の部分を値に置換したり、node が無い部分を空白化するという案も検討中です...

[code]

                x
          /----- -----\
          x           x
       /-- --\     /-- --\
      x      x     x     x
     / \    / \   / \   / \
     x x    x x   x x   x x
    
[/code]




[２分木のデータ追加、サーチ、削除について](https://ja.stackoverflow.com/questions/4721)
のコードに追加する形で書いてみました。

[code]

    class Node
      attr_accessor :value, :left, :right
      def initialize(val)
        @value = val
        @left = nil
        @right = nil
      end 
    end
    
    def create_new_node(val)
      newNode = Node.new(val)
      return newNode
    end
    
    def insert_tree(num, node)
      if ! node
        @tree_root = create_new_node(num)
        return
      end 
      if node.value > num
        if node.left
          insert_tree(num, node.left)
        else
          node.left = create_new_node(num)
        end
      else
        if node.right
          insert_tree(num, node.right)
        else
          node.right = create_new_node(num)
        end
      end
    end
    
    def show_btree (btree)
      if btree == nil then return end
    
      ## Convert btree to 2-dim array
      @node_array = Hash.new { |hash, key| hash[key] = Hash.new {} }
      def bt2arr (node, depth, n)
        @node_array[depth][n] = node.value 
        if node.left then
          bt2arr(node.left, depth + 1, 2 * n)
        end
        if node.right then
          bt2arr(node.right, depth + 1, 2 * n + 1)
        end
      end
    
      ## Show link from a node to another node
      def put_arrow (i, j, w)
        _w = (w / 4 - 1)
        if @node_array[i+1][2*j] then
          _arrow = "/" + (_w > 2 ? "-" * (_w - 1) : "")
        else
          _arrow = if _w > 0 then " " * _w else "" end
        end
        _arrow += " "
        if @node_array[i+1][2*j+1] then
          _arrow += (_w > 2 ? "-" * (_w - 1) : "") + "\\"
        else
          _arrow += if _w > 0 then " " * _w else "" end
        end
        return _arrow
      end
    
      bt2arr(btree, 0, 0)
    
      ## Justification
      depth = @node_array.length
      width = @node_array.map {|h| h[1].values.max}.max.to_s.length
      if depth < 4 then
        width += ( width.even? ? 1 : 0 )
      end
      rlen = 2 ** (depth - 1) * (width + 1)
      row_num = 2 * depth - 1
      row = Array.new(row_num)
      for i in 0..(depth-1)
        row_str = arrow = ""
        w = rlen / (2 ** i)
        for j in 0..(2 ** i - 1)
          if @node_array[i][j] then
            row_str += @node_array[i][j].to_s.center(w)
            arrow += put_arrow(i, j, w).center(w)
          else
            row_str += " " * w
            arrow +=  " " * w
          end
        end
        row[2*i] = row_str.center(rlen).rstrip
        if 2*i+1 < row_num then row[2*i+1] = arrow.rstrip end
      end
    
      ## Get rid of spaces at left side
      room = row.map {|r| r.gsub(/^( *).*$/, '\1').length }.min
      if room > 1 then
        row.each{|r| r.gsub!(/^[ ]{#{room-1}}/, '')}
      end
    
      ## Lift up underscores
      row.each_with_index do |r, n|
        r.split(//).each_with_index do |c, i|
          if c == "-" then
            if row[n-1][i] == " " || ! row[n-1][i] then
              row[n-1][i] = "_"
            end
            row[n][i] = " "
          end
        end
      end
    
      ## Shrink loose spaces
      col = 1
      while true do
        col_str = (0..(row_num-1)).map {|r| row[r][col] ? row[r][col] : ""}.join
        if col_str == "" then break end
        if col_str =~ /^[ _]*$/ then
          (0..(row_num-1)).each {|r| row[r].slice!(col)}
        else
          col += 1
        end
      end
    
      row.each{|r| puts r}
    end
    
    # Now testing...
    @tree_root = nil
    [9, 4, 15, 2, 6, 12, 17].each {|n| insert_tree(n, @tree_root) }
    show_btree(@tree_root)
    puts ""
    
    @tree_root = nil
    [3234, 5678, 2235, 1799, 3205,
     7851, 1280, 2100, 2850, 3220,
     4000, 3800, 4920, 6602, 9999].each {|n| insert_tree(n, @tree_root) }
    show_btree(@tree_root)
    puts ""
    
    @tree_root = nil
    [10, 9, 19, 8, 18, 7, 17].each {|n| insert_tree(n, @tree_root) }
    show_btree(@tree_root)
    puts ""
    
    @tree_root = nil
    for _ in 0..3
    insert_tree(rand(101..1000), @tree_root)
    insert_tree(rand(11..100), @tree_root)
    insert_tree(rand(1001..10000), @tree_root)
    end
    show_btree(@tree_root)
    
[/code]

btree を2次元配列に置き換えて表示位置を調整しています。
~~ただし、ノードとノードを結ぶ線分を表示していません。。。(すみません、面倒くさくなってしまいました)  
場合によってはかなり「横長」になりますので、`less -S` などにパイプで繋いでご覧ください。~~  
実行結果は以下の様になります。

[code]

         _9_
        /   \
       4     15
      / \   / \
     2   6 12  17
    
               _______3234______
              /                 \
          __2235_             __5678_
         /       \           /       \
       1799      3205      4000      7851
       / \       / \       / \       / \
    1280 2100 2850 3220 3800 4920 6602 9999
    
          10___
         /     \
        9       19
       /       /
      8      18
      /      /
     7     17
    
    
           ___________929____________
          /                          \
         86___                  _____8901
        /     \                /      
       85     162           _5109
      /      /   \         /     \
     69    100   646     3753    7972
                   \
                    706
    
[/code]

![Binary Tree](https://i.stack.imgur.com/CiTNl.gif)

今回は一旦、「btree 全体を描いて」から、不要なスペースを削り取る方法(コメントの `shrink loose spaces`
の部分)で処理しました。意外と(プログラミングを)楽しむ事ができた課題ではありましたが、それは ruby
のおかげ、ですね。おそらく、この方法を他のプログラミング言語で書き下した場合はかなり煩雑になったのではないかと思われます(そうでもないかな？)。

