

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]


CC BY-SA 3.0
2015-01-17T10:30:37.790
4739
2015-01-25T10:09:40.730
2017-05-23T12:38:56.467
-1
2987
question
ruby アルゴリズム binary-tree
2 分木を ascii art で表示する方法は?


[C#ですが書いてみました](http://ideone.com/ZZFKym)。リンク先の46行目～97行目が表示処理です。出力は横向きです。

[code]

    61--62
    └--63--02--04
        │  └--14
        └--10--45
            └--68
    
[/code]

処理としてはスタックにノードの値を左深さ優先で追加しながら、該当ノードの値を表示するまでに必要な罫線を順次書き込んでいます。あと各ノードの子を探索済みかどうかの情報を持つスタックも用意しています。C#特有のAPIは`Console.Write`と`Console.WriteLine`を使用していますが、これはコンソール出力メソッドで`{0:D2}`には数字二桁が出力されます。

注意として上記のように全ノードの値が2桁以内という条件で実装しているので100以上の値が混じるとずれが発生します。


CC BY-SA 3.0
2015-01-17T11:40:41.503
4741
2015-01-17T11:53:00.113
2015-01-17T11:53:00.113
5750
5750
4739
answer


[２分木のデータ追加、サーチ、削除について](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
のおかげ、ですね。おそらく、この方法を他のプログラミング言語で書き下した場合はかなり煩雑になったのではないかと思われます(そうでもないかな？)。


CC BY-SA 3.0
2015-01-17T18:09:32.747
4761
2015-01-20T22:22:23.683
2015-01-20T22:22:23.683
4739
answer


縦型でノード位置を出力するコードです。盛大にずれていますが出力は下の様な感じです。

[code]

                                [node]
                  ┌------------┘  └------------┐
                [node]                          [node]
          ┌----┘  └----┐              ┌----┘  └----┐
        [node]          [node]          [node]          [node]
      ┌┘  └┐      ┌┘  └┐      ┌┘  └┐      ┌┘  └┐
    [node]  [node]  [node]  [node]  [node]  [node]  [node]  [node]
    
[/code]

コードは下記のとおりです。

[code]

    static void Main(string[] args)
    {
        var MAX_DEPTH = 5;
        var NODE_TEXT = "[node]";
        var NODE_WIDTH = NODE_TEXT.Length;
        var MIN_INTERVAL = 2;
    
        var LINE_LEAF_LEFT = "  ┌┘"; // TODO:ノード幅に合わせて変える必要あり
        var LINE_LEAF_RIGHT = "└┐  ";
        var LINE_LEFT = "  ┌--";
        var LINE_RIGHT = "--┐  ";
        var LINE_CENTER = "┘  └";
    
        var totalWidth = (1 << (MAX_DEPTH - 1)) * (NODE_WIDTH + MIN_INTERVAL) - MIN_INTERVAL;
    
        for (var d = 0; d < MAX_DEPTH; d++)
        {
            // ノード間の距離
            var interval = (1 << (MAX_DEPTH - d - 1)) * (NODE_WIDTH + MIN_INTERVAL) - NODE_WIDTH;
    
            // 階層全体の幅
            var levelWidth = (1 << d) * (NODE_WIDTH + interval) - interval;
    
            // 階層の開始位置
            var padding = (totalWidth - levelWidth) >> 1;
    
            var levelCount = 1 << d;
    
            // 線の描画
            if (d != 0)
            {
                Console.Write(new string(' ', padding));
    
                for (var j = 0; j < levelCount; j++)
                {
                    if (d == MAX_DEPTH - 1)
                    {
                        // 末端から上に伸びる線
                        Console.Write(j % 2 == 0 ? LINE_LEAF_LEFT : LINE_LEAF_RIGHT);
                    }
                    else
                    {
                        // その他の節から上に伸びる線
                        Console.Write(j % 2 == 0 ? LINE_LEFT : LINE_RIGHT);
                    }
    
                    if (j == levelCount - 1)
                    {
                        break;
                    }
    
                    if (d == MAX_DEPTH - 1 || j % 2 != 0)
                    {
                        // ノード間の空白
                        Console.Write(new string(' ', interval));
                    }
                    else
                    {
                        // ノード間に親ノードがある場合
                        Console.Write(new string('-', (interval - NODE_WIDTH) / 2));
                        Console.Write(LINE_CENTER);
                        Console.Write(new string('-', (interval - NODE_WIDTH) / 2));
                    }
                }
                Console.WriteLine();
            }
    
            Console.Write(new string(' ', padding));
    
            for (var j = 0; j < levelCount; j++)
            {
                // TODO:ノード値の出力
                Console.Write(NODE_TEXT);
                if (j == levelCount - 1)
                {
                    break;
                }
                // ノード間の空白
                Console.Write(new string(' ', interval));
    
            }
            // 改行
            Console.WriteLine();
        }
        Console.ReadKey();
    }
    
[/code]


CC BY-SA 3.0
2015-01-18T02:12:15.290
4769
2015-01-18T02:12:15.290
5750
4739
answer


サンプルを書いてみました。順を追って作った経緯を説明します。

ソース: <https://gist.github.com/snipsnipsnip/0e267f6a39cc2397da3d>  
動作: ~~<http://ideone.com/Yaw8k3>~~ <http://ideone.com/9iuF6e>

## レイアウト

[code]

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

katoyさんの例からレイアウトの仕様を考えてみます。

  * 縦方向は以下の内容を交互に表示します。  
  

    1. 下線と数字からなる行 (`__9__` や `2 6 12 17`)
  

    2. 斜線の行 (`/\ / \`)
  

  * 横方向には、以下のルールで数字を配置します。  
  

    1. 親ノードの数字より左に、左の子ノードの数字を置く
  

    2. 親ノードの数字より右に、右の子ノードの数字を置く
  

    3. 一つの桁には数字を一つだけ置く（数字の上下に数字は現れない）
  

この仕様だと、横幅は次のように再帰的に計算できます。

  * ノードの描画に必要な横幅 ＝  
ノードの持つ数値の桁数 +  
左手の子ノードの描画幅 (なければ0) +  
右手の子ノードの描画幅 (なければ0)

つまり、AA全体の横幅はすべての数値の桁数を合計したものになります。

## 座標の計算

ノードひとつひとつを描画するには、X座標とY座標を計算します。

  * ノードのX座標 = そのノードよりも左にあるノードの横幅の合計
  * ノードのY座標 = ノードの深さ

データ構造は以前の質問から引き継ぎます。

[code]

    class Node
      attr_accessor :value, :left, :right
      def initialize(val)
        @value = val   # ノードが保持する値
        @left = nil    # 左側のノード
        @right = nil   # 右側のノード
      end
    end
    
[/code]

### 横幅とX座標の計算

通りがけ順（左ノード→自身→右ノード）で深さ優先探索をすれば、ノードを左下から順に巡ってゆくことができるので、足しあわせてゆけばX座標の計算ができます。

横幅の計算とノードのX座標の計算は同時に行えます。

[code]

    # 描画に必要な横幅を計算
    def width(node, x = 0)
      # 左のノードがあれば、そのノード以下の木の横幅を計算
      if node.left != nil
        x = width(node.left, x)
      end
    
      # このノードの桁数を計算
      w = node.value.to_s.size
    
      puts "#{node.value} のX座標は #{x}"
      puts "#{node.value} の横幅は #{w}"
    
      # 右手の子ノードの開始位置までxを移動
      x += w
    
      # 右のノードがあれば、そのノード以下の木の横幅を計算
      if node.right != nil
        x = width(node.right, x)
      end
    
      puts "#{value} 以下の描画の横幅は #{x}"
    
      # 呼び出した親のために横幅を返す
      return x
    end
    
[/code]

### 縦幅とY座標の計算

同じく縦幅の計算とノードのY座標の計算は同時に行えます。

Y座標はノードの深さを調べるだけです。(斜線を挟むなら2倍にすればOK)

[code]

    # 描画に必要な縦幅の計算
    def height(node, y = 1)
      if node.left != nil
        left_height = height(node.left, y + 1)
      else
        left_height = 1
      end
    
      puts "#{value} のY座標は #{y}"
    
      if node.right != nil
        right_height = height(node.right, y + 1)
      else
        right_height = 1
      end
    
      [left_height, right_height].max
    end
    
[/code]

### 座標計算を配列にまとめる

上の`width`、`height`ではプリントするだけでしたが、代わりに配列にまとめる関数を作ります。

ついでに、X座標とY座標を同時に計算してしまうようにします。

[code]

    # 描画に必要な情報を計算
    def render_info(canvas, node, x, y)
      # 左のノードがあれば、そのノード以下の木の横幅を計算
      x = render_info(canvas, node.left, x, y + 1) if node.left
    
      # このノードの分の描画に必要な情報(X座標, Y座標, そのもの)を追加
      canvas << [x, y, node]
    
      # このノードの桁数を計算
      x += node.value.to_s.size
    
      # 右のノードがあれば、そのノード以下の木の横幅を計算
      x = render_info(canvas, node.right, x, y + 1) if node.right
    
      # 呼び出した親のために横幅を返す
      x
    end
    
    # render_infoで描画情報を集めて返す
    def render(root)
      canvas = []
      render_info(canvas, root, 0, 0)
      canvas
    end
    
[/code]

`render`は、例えば二分木をこのように座標データに変換します。

[code]

         __9__
        /     \
       4       15
      /\      / \
     2  6    12  17
          ↓ render
    [[0, 2, "2"], [1, 1, "4"], [2, 2, "6"], [3, 0, "9"], [4, 2, "12"], [6, 1, "15"], [8, 2, "17"]]
    
[/code]

## 座標データからプリント

座標データの計算ができたら、それを使ってY座標の順に上から出力すれば描画できます。

[code]

    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|
        # y座標が増えたら改行
        if y != last_y
          last_x = 0
          puts
        end
    
        # 必要な分だけスペースを入れてプリント
        print " " * (x - last_x)
        print node.value
    
        # カーソルを進める
        last_x = x + node.value.to_s.size
        last_y = y
      end
      puts
    end
    
[/code]

この`print_canvas`は単純化したもので、下線も斜線もありません。  
次のように出力されます。

[code]

       9
     4    15
    2 6 12  17
    
    # ツリーを短く書くために定義
    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)
    
[/code]

## 左右の下線の追加

次に、下線をつけます。上の例ではこうついてほしいと思います。

[code]

    >> print_canvas2 render(tree)
      _9__
     4    15
    2 6 12  17
    
[/code]

下線は左右の子ノードの数値に沿うように伸ばします。

[code]

    def print_canvas2(canvas)
        # ...
        # 数字左側の下線
        if node.left
          # 下線の長さの計算: 次の行の数字で、この数字のすぐ左にあるものを探してX座標をとる
          iright = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx }
          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
        # ...
        # 数字右側の下線
        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
        # ...
      end
      puts
    end
    
[/code]

空白の表示部分に下線をプリントする処理を加えて、下線が引けました。

[code]

                   _____30___
      ___________9__        _9__
     4              15     4    15
    2 6___        12  17  2 6 12  17
         _9__
        4    15
       2 6 12  17
    
[/code]

## 斜線の追加

最後に斜線を入れます。一重ループでは同じ行を二度舐めるような処理がしにくいので、データ構造を変えて行ごとにグループ分けします。

[code]

    # Y座標ごとにグループ分け
    canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line.sort }
    
[/code]

`canvas_lines`は、このようなデータ構造に変換したものです。

[code]

         __9__
        /     \
       4       15
      /\      / \
     2  6    12  17
    
          ↓
    # canvas
    [[0, 2, "2"], [1, 1, "4"], [2, 2, "6"], [3, 0, "9"], [4, 2, "12"], [6, 1, "15"], [8, 2, "17"]]
          ↓
    # canvas_lines
    [
      [[3, 0, "9"]], # 1行目
      [[1, 1, "4"], [6, 1, "15"]], # 2行目
      [[0, 2, "2"], [2, 2, "6"], [4, 2, "12"], [8, 2, "17"]] # 3行目
    ]
    
[/code]

これで行ごとにループができます。  
斜線の位置の計算は下線の両端に伸ばすだけなので、下線の計算結果をそのまま利用します。

[code]

    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|
          # ...
          # 数字左側の下線
          if node.left
            # ...
              # 下線の左端を欠けさせる (スペースにする)
              print " "
              print "_" * (x - left_x_end - 1)
    
              # 斜線の描画を予約 (左手ノードなのでスラッシュ)
              slashes << [left_x_end, '/']
          else
            print " " * (x - last_x)
          end
          # ...
          # 数字右側の下線
          if node.right
            # ...
    
            if x < right_x
              # 下線の右端を欠けさせる (スペースにする)
              print "_" * (right_x - x - 1)
              print " "
              # 斜線の描画を予約 (右手ノードなのでバックスラッシュ)
              slashes << [right_x - 1, '\\']
            end
            x = right_x
          end
          # ...
        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
    
[/code]

これで表示すると、寸詰まりな結果が出てきます。下線を欠けさせて表示するようにしたので、下線が一本も入らない時には斜線も入らないという動作です。

[code]

    >> print_canvas3 render(tree)
       9_
      /  \
     4    15
    2 6 12  17
    
[/code]

## 余白

常に斜線をいれるようにもしてみましたが、見た目が微妙だったのでやめました。代わりに`render`でノードの左右に余白を入れられるようにしました。([gist](https://gist.github.com/snipsnipsnip/0e267f6a39cc2397da3d)をご覧ください)

[code]

    >> print_canvas3 render(tree, 1)
        __9___
       /      \
      4        15
     / \      /  \
    2   6   12    17
    >> print_canvas3 render(tree, 2)
         ____9_____
        /          \
      _4_          _15_
     /   \        /    \
    2     6     12      17
    
[/code]

## 追記: バグ修正＋リファクタリング

すみません、上のコードでは`Node(30, tree, nil)` のように左手にしかノードがない場合に落ちます…。(`next_line.index
{|nx, *| x <= nx } - 1` で`nil`が出ることを考えていませんでした。回避には`(next_line.index {|nx, *|
x <= nx } || next_line.size) - 1` のようにします)  
修正のついでに処理を小分けしました。

ソース: <https://gist.github.com/snipsnipsnip/0e267f6a39cc2397da3d#file-
aa_tree_refactored-rb>  
実行: <http://ideone.com/oU2VUF>

## まとめ

座標計算で通りがけ順の深さ優先探索をするところがコツだと思います。  
表示自体にはあまり木構造らしい処理は必要ありませんでした。


CC BY-SA 3.0
2015-01-18T06:12:42.973
4777
2015-01-20T18:27:20.523
2015-01-20T18:27:20.523
5910
5910
4739
answer


ここに投稿されていた Ruby のソース読んでいたら面白かったので、私も Go 言語で書いたバージョンを作りました。

  * 基本構造は、[SO の質問](https://stackoverflow.com/a/4973083)を参考
  * ツリー構造は、[golang チュートリアル](http://golang.org/doc/play/tree.go)を参考

と、上２点の資料を元にしてあります、汚いが動きます。

  * [Go Playground](https://play.golang.org/p/TO0Q1IR3Td)

## 意図したこと

### レイアウト目標

[code]

        161 
      ---|---  
     /       \   
    146     182  
            -|-                   
           /   \  
          162 185 
    
[/code]

### 動作目標

出力する前に、

  * 二分木の再深度
  * 二分木の最大値

の二つをDFSで求め、それで出力する木の大きさを決めうちしBFSでプロットしていきます。木は横に長く、左右対称になります。伸縮具合はかーなり適当ですが、大きな桁数でなければ対応します。

## ソースコード

bitree_print.go: (1 ファイル)

[code]

    package main
    
    import (
      "math/rand"
      "strconv"
      "time"
    )
    
    // The main function
    func main() {
      // Generate a random tree
      rand.Seed(time.Now().UTC().UnixNano())
      rootNode := NewPopulatedTree(20, 999)
      // Print the tree
      PrintNode(rootNode)
    }
    
    //
    // Binary tree printers
    //
    
    // Prints the given binary tree
    func PrintNode(root *Tree) {
      PrintNodeWithPrinter(root, defaultTreeToStringFunc())
    }
    
    // Prints the given binary tree
    func PrintNodeWithPrinter(root *Tree, treeToString TreeToStringFunc) {
      printNodeInternal([]*Tree{root}, 1, maxLevel(root), Digits(maxValue(root))/2-1, treeToString)
    }
    
    func getPrintTreeBranchFunc(printLeft func(int), printCenter func(int), printRight func(int),
      printSpace func(int), leftistLetter rune, rightestLetter rune) func(*Tree, int) {
      return func(node *Tree, i int) {
        if node.Left == nil {
          printSpace(i)
        } else if i > 0 {
          print(string(leftistLetter))
          printLeft(i - 1)
        }
        if node.Left == nil && node.Right == nil {
          printSpace(1)
        } else {
          printCenter(1)
        }
        if node.Right == nil {
          printSpace(i)
        } else if i > 0 {
          printRight(i - 1)
          print(string(rightestLetter))
        }
      }
    }
    
    func getPrintLetters(letter rune) func(int) {
      return func(count int) {
        for i := 0; i < count; i++ {
          print(string(letter))
        }
      }
    }
    
    var printWhitespaces = getPrintLetters(rune(' '))
    var printHorizontalLine = getPrintLetters(rune('-'))
    var printVirticalLine = getPrintLetters(rune('|'))
    var printTreeBranchUpper = getPrintTreeBranchFunc(
      printHorizontalLine, printVirticalLine, printHorizontalLine, printWhitespaces,
      rune('-'), rune('-'))
    var printTreeBranchLower = getPrintTreeBranchFunc(
      printWhitespaces, printWhitespaces, printWhitespaces, printWhitespaces,
      rune('/'), rune('\\'))
    
    func printNodeInternal(nodes []*Tree, level int, maxLevel int, floorElev int, treeToString TreeToStringFunc) {
      if len(nodes) == 0 || isElementsNull(nodes) {
        return
      }
    
      floor := maxLevel - level + floorElev + 1
      edgeLines := Pow(2, Max(floor-1, 0))
      firstSpaces := Pow(2, floor) - 1
      betweenSpaces := Pow(2, floor+1) - 1
    
      var newNodes []*Tree
      var prevPostDigits = 0
      for i, node := range nodes {
        var relativeLeft, relativeRight *Tree
        var value string
        var digits int
        if node != nil {
          relativeLeft, relativeRight = node.Left, node.Right
          value = treeToString(node)
        } else {
          relativeLeft, relativeRight = nil, nil
          value = " "
        }
        digits = len(value)
    
        var preDigits, postDigits = (digits / 2), (digits / 2) + (digits % 2)
    
        if i == 0 {
          printWhitespaces(firstSpaces - (preDigits + prevPostDigits))
        } else {
          printWhitespaces(betweenSpaces - (preDigits + prevPostDigits) + 1)
        }
        newNodes = append(newNodes, relativeLeft)
        newNodes = append(newNodes, relativeRight)
        print(value)
    
        prevPostDigits = postDigits
      }
      println()
    
      startEdgeLine := edgeLines
      if maxLevel != level-1 {
        startEdgeLine = startEdgeLine - 1
      }
      for i := startEdgeLine; i <= edgeLines; i++ {
        for j := 0; j < len(nodes); j++ {
          printWhitespaces(firstSpaces - i)
          if nodes[j] == nil {
            printWhitespaces(edgeLines + edgeLines + i + 1)
            continue
          }
          if i == startEdgeLine {
            printTreeBranchUpper(nodes[j], i)
          } else {
            printTreeBranchLower(nodes[j], i)
          }
          printWhitespaces(edgeLines + edgeLines - i)
        }
        println()
      }
      printNodeInternal(newNodes, level+1, maxLevel, floorElev, treeToString)
    }
    
    //
    // Binary Tree
    //
    
    type Tree struct {
      Left  *Tree
      Value int
      Right *Tree
    }
    
    func NewPopulatedTree(n int, k int) *Tree {
      var t *Tree
      for i := 0; i < n; i++ {
        t = insert(t, int(rand.Float32()*float32(k)))
      }
      return t
    }
    
    func insert(t *Tree, v int) *Tree {
      if t == nil {
        return &Tree{nil, v, nil}
      }
      if v < t.Value {
        t.Left = insert(t.Left, v)
      } else {
        t.Right = insert(t.Right, v)
      }
      return t
    }
    
    type TreeToStringFunc func(*Tree) string
    
    func defaultTreeToStringFunc() TreeToStringFunc {
      return func(node *Tree) string { return strconv.Itoa(node.Value) }
    }
    
    func maxLevel(node *Tree) int {
      if node == nil {
        return 0
      }
      return Max(maxLevel(node.Left), maxLevel(node.Right)) + 1
    }
    
    func maxValue(node *Tree) int {
      var max = node.Value
      if node.Left != nil {
        max = Max(max, maxValue(node.Left))
      }
      if node.Right != nil {
        max = Max(max, maxValue(node.Right))
      }
      return max
    }
    
    func isElementsNull(list []*Tree) bool {
      for _, object := range list {
        if object != nil {
          return false
        }
      }
      return true
    }
    
    //
    // Math Utilities for Integer (Pow, Max for int)
    //
    
    func Pow(x, y int) (r int) {
      if x == r || y < r {
        return
      }
      r = 1
      if x == r {
        return
      }
      if x < 0 {
        x = -x
        if y&r == r {
          r = -r
        }
      }
      for y > 0 {
        if y&1 == 1 {
          r *= x
        }
        x *= x
        y >>= 1
      }
      return
    }
    
    func Max(a, b int) int {
      if a > b {
        return a
      }
      return b
    }
    
    func Digits(a int) int {
      if a == 0 {
        return 1
      }
      var c int
      for c = 0; a != 0; c++ {
        a /= 10
      }
      return c
    }
    
[/code]

## 出力

### Output 1 (n: 16, range: 0...9)

[code]

                             7
              ---------------|---------------                 
             /                               \                
             1                               7
      -------|-------                                         
     /               \                                        
     0               3                                
     |---         ---|---                                     
         \       /       \                                    
         0       2       5                                
         |-     -|      -|-                                   
           \   /       /   \                                  
           0   1       4   5                                
               |       |   |                                  
                \     / \   \                                 
                1     3 4   5                         
    
[/code]

### Output 2 (n: 20, range: 1...999)

[code]

                                                                  662
                                    -------------------------------|-------------------------------                                 
                                   /                                                               \                                
                                  247                                                             749
                    ---------------|---------------                                 ---------------|---------------                 
                   /                               \                               /                               \                
                  132                             491                             735                             943
            -------|-------                 -------|-------                                                 -------|                
           /               \               /               \                                               /                        
          59              242             322             519                                             937               
        ---|---         ---|            ---|---            |---                                         ---|                        
       /       \       /               /       \               \                                       /                            
      27      82      150             273     467             564                                     784                       
                                       |-                                                                                           
                                         \                                                                                          
                                        280                                                                                        
    
[/code]

### Output 3 (n: 10, range: 1...123456)

[code]

                                                     23619
                        -------------------------------|-------------------------------                                 
                       /                                                               \                                
                     10211                                                           99879
        ---------------|---------------                                 ---------------|---------------                 
       /                               \                               /                               \                
     1296                            15501                           96855                          118543
                                -------|                        -------|                        -------|                
                               /                               /                               /                        
                             13676                           58204                          112828          
    
[/code]

## デバッグ時の様子

[code]

    zzzzzzzzzzzzzzzzzzzzzzzzzzzzzz42
    ffffffffffffffff---------------|---------------eeeeeeeeeeeeeeeee
    fffffffffffffff/lllllllllllllllcrrrrrrrrrrrrrrr\eeeeeeeeeeeeeeee
    zzzzzzzzzzzzzzz3==============================86
    ffffffff-------|-------eeeeeeeeeffffffff-------|-------eeeeeeeee
    fffffff/lllllllcrrrrrrr\eeeeeeeefffffff/lllllllcrrrrrrr\eeeeeeee
    zzzzzzz1==============27==============47==============96
    ffff_______eeeeeffff---|---eeeeeffff---|---eeeeeffff---|___eeeee
    fff_________eeeefff/lllcrrr\eeeefff/lllcrrr\eeeefff/lllc____eeee
    zzz ======= ======22======37======42======74======89======= 
    ffnnnnnnffnnnnnnff___eeeff___eeeff___eeeff-|-eeeff-|-eeeffnnnnnn
    fnnnnnnnfnnnnnnnf_____eef_____eef_____eef/lcr\eef/lcr\eefnnnnnnn
    z === === === === === === === === === ==48==85==88==90=== === 
    fnnnfnnnfnnnfnnnfnnnfnnnfnnnfnnnfnnnfnnnf_eef_eef_eef_eefnnnfnnn
    nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn___e___e___e___ennnnnnnn
    
[/code]


CC BY-SA 3.0
2015-01-20T14:26:58.637
4927
2015-01-20T14:26:58.637
2017-05-23T12:38:56.083
-1
4978
4739
answer


なるべく横幅も狭い絵を出力するものを作ってみました。(コードの末尾に出力結果を引用してあります。)  
<https://gist.github.com/katoy/9faf8b2362313e72340e>

[code]

    # coding: utf-8
    
    # See http://ja.stackoverflow.com/questions/4739
    #     https://gist.github.com/snipsnipsnip/0e267f6a39cc2397da3d
    #
    # 2 分木をコンソールにアスキーアートで出力する。
    #
    
    class Node
      attr_accessor :value, :left, :right
      def initialize(val)
        @value = val
        @left = nil
        @right = nil
      end
    end
    
    class Canvas
      def initialize(width, height)
        @canvas = Array.new(width){ Array.new(height, ' ') }  # 描画キャンバス
        @w, @h = [width, height]                              # canvas の幅, 高さ
      end
    
      # canvas の大きさを拡大させる。
      def expand(inc_x, inc_y)
        inc_x = 0 if inc_x < 0
        inc_y = 0 if inc_y < 0
        new_canvas = Array.new(@w + inc_x) { Array.new(@h + inc_y, ' ') }
        (0...@w).each do |x|
          (0...@h).each do |y|
            new_canvas[x][y] = @canvas[x][y]
          end
        end
        @canvas = new_canvas
        @w, @h = [@canvas.size, @canvas[0].size]
      end
    
      # canvas を STDOUT に表示する。
      def show
        (0...@h).each { |y| STDOUT.puts "|#{line(y)}|\n" }
      end
    
      def put_string(str, x, y)
        # 描画がはみ出るようなら、事前に canvas の大きさを拡張する。
        if (x + str.length >= @w) || y >= @h
          inc_x, inc_y = [0, 0]
          inc_x = 1 + (x + str.length - @w) if (x + str.length) >= @w
          inc_y = 1 + y - @h if y >= @h
          expand(inc_x, inc_y)
        end
    
        pos = x
        str.each_char do |c|
          @canvas[pos][y] = c
          pos += 1
        end
      end
    
      # 描画をする際に、既存の文字列を上書きしてしまわないかを調べる。
      def put_string?(str, x, y)
        return true if y < 0
        return true if y >= @h
        return true if x >= @w
    
        (0...str.length).each do |dx|
          return true if x + dx >= @w
          return false if (x + dx >= 0) && @canvas[x + dx][y] != ' '
        end
        true
      end
    
      def copy_area(x0, y0, dx, dy, fill = nil)
        strs = Array.new(dy, ' ')
        idx = 0
        (0...dy).each do |y|
          line = ''
          (0...dx).each do |x|
            line += "#{@canvas[x0 + x][y0 + y]}"
            @canvas[x0 + x][y0 + y] = fill if fill
          end
          strs[idx] = line
          idx += 1
        end
        strs
      end
    
      def clear(x0 = 0, y0 = 0, dx = @w, dy = @h)
        copy_area(x0, y0, dx, dy, ' ')
      end
    
      def fill_rect(c, x0, y0, dx, dy)
        copy_area(x0, y0, dx, dy, c)
      end
    
      def line(y)
        str = ''
        return '' if y < 0 || y >= @h
        (0...@w).each do |x|
          str += @canvas[x][y]
        end
        str
      end
    end
    
    # ツリーの宣言を短く書くために定義
    def Node(val, left = nil, right = nil)
      node = Node.new(val)
      node.left = left
      node.right = right
      node
    end
    
    # ノードを描画できるかを調べる。(既存描画文字を壊さないかを知らべる)
    def put_node?(canvas, str, x, y)
      return true if y < 0
      return false if x < 1
      return false unless canvas.put_string?('*' * (str.length + 1), x - 1, y)
    
      line_right = canvas.line(y)[x..-1]
      if line_right
        line_right.each_char do |c|
          return false if c != ' '
        end
      end
      true
    end
    
    # 2 分木を描画する。
    def print_tree(canvas, tree, x = 0, y = 0)
      return x unless tree
    
      val_s          = "#{tree.value}"
      val_s_len      = val_s.length
      val_s_len_half = val_s_len / 2
    
      d_left = x - 2
      d_left = 0 if d_left < 0
      d_left = print_tree(canvas, tree.left,  d_left, y + 2) if tree.left
    
      sx = d_left + val_s_len + 1
      loop do
        break if put_node?(canvas, val_s, sx, y) && put_node?(canvas, val_s, sx, y - 2)
        sx += 1
      end
    
      d_right = sx
      d_right  = print_tree(canvas, tree.right,  d_right,  y + 2) if tree.right
    
      dx = (d_left + d_right) / 2
      sx = dx - val_s_len_half
      loop do
        break if put_node?(canvas, val_s, sx, y) && put_node?(canvas, val_s, sx, y - 2)
        dx += 1
        sx += 1
      end
    
      if tree.right.nil? && tree.left.nil?
        canvas.put_string(val_s, sx, y)
      else
        connect = ''
        connect += ('_' * (dx - d_left - val_s_len_half - 1)) if !tree.left.nil? && (dx - d_left - val_s_len_half - 1 >= 0)
        connect += val_s
        connect += ('_' * (d_right - dx - val_s_len))         if !tree.right.nil? && (d_right - dx - val_s_len >= 0)
    
        canvas.put_string(connect, d_left + 1,  y)
        canvas.put_string("/",   d_left,  y + 1) if tree.left
        canvas.put_string("\\",  d_right, y + 1) if tree.right
      end
      dx
    end
    
    canvas = Canvas.new(10, 5)
    tree = Node(5,
                Node(4, Node(3, Node(2, Node(1)))),
                Node(9, Node(8, Node(7, Node(5)))))
    print_tree(canvas, tree)
    canvas.show
    puts
    
    tree = Node(5,
                Node(4, Node(3, Node(2, Node(1)))),
                Node(9, Node(80000,
                             Node(7, Node(5)),
                             Node(3)
                            )
                    )
               )
    canvas.clear
    print_tree(canvas, tree)
    canvas.show
    puts
    
    canvas = Canvas.new(10, 6)
    tree_s = Node(9,
                  Node(4, Node(2), Node(6)),
                  Node(15, Node(12), Node(17))
                 )
    tree = Node(4, tree_s, Node(3, tree_s))
    canvas.clear
    print_tree(canvas, tree)
    canvas.show
    puts
    
    tree = Node(9,
                Node(4, Node(2), Node(6)),
                Node(15, Node(12), Node(17))
               )
    canvas.clear
    print_tree(canvas, tree)
    canvas.show
    puts
    
    __END__
    |     5_   |
    |    /  \  |
    |    4  9  |
    |   /  /   |
    |   3  8   |
    |  /  /    |
    |  2  7    |
    | /  /     |
    | 1  5     |
    
    |     _5__   |
    |    /    \  |
    |    4    9  |
    |   /    /   |
    |   3  80000 |
    |  /  /    \ |
    |  2  7    3 |
    | /  /       |
    | 1  5       |
    
    |     ____4_____      |
    |    /          \     |
    |   _9__        3     |
    |  /    \      /      |
    |  4    15    _9__    |
    | / \  /  \  /    \   |
    | 2 6 12 17  4    15  |
    |           / \  /  \ |
    |           2 6 12 17 |
    
    |   _9__              |
    |  /    \             |
    |  4    15            |
    | / \  /  \           |
    | 2 6 12 17           |
    |                     |
    |                     |
    |                     |
    |                     |
    
[/code]

更新：  
* 2015-01-25  
次の様な出力になってしまうことがあったのを修正。

[code]

    |     _5__     |
    |    /    \    |
    |    4    9    |
    |   /    /     |
    |   3  __80000 |
    |  /  / \      |
    |  2  7 3      |
    | /  /         |
    | 1  5         |
    
[/code]

修正後は次の様な出力になります。

[code]

    |     _5__   |
    |    /    \  |
    |    4    9  |
    |   /    /   |
    |   3  80000 |
    |  /  /    \ |
    |  2  7    3 |
    | /  /       |
    | 1  5       |
    
[/code]

  * 2015-01-25 その２  
ー gist の方だけを更新 <https://gist.github.com/katoy/9faf8b2362313e72340e>  
ー gviz をつかって dot レイアウトでの画像を表示させるようにした。(node の表示位置は gviz にまかせている)  
*node の値の両脇に '_' をつける処理を Strong#ceneter で行うようにした。 right の表示位置を微調整した。

修正後の出力

[code]

    |     _5__    |
    |    /    \   |
    |    4    9   |
    |   /    /    |
    |   3  80000  |
    |  /  /     \ |
    |  2  7     3 |
    | /  /        |
    | 1  5        |
    
[/code]


CC BY-SA 3.0
2015-01-24T12:23:56.293
5209
2015-01-25T10:09:40.730
2015-01-25T10:09:40.730
2987
2987
4739
answer