7

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

出力イメージ:(あくまでイメージ。これと異なっていても構いません。)

     __9__
    /     \
   4       15
  /\      / \
 2  6    12  17

2 分木の操作プログラム例が以下にあります。このコード中での tree 表示結果を上のようなものにしたいのです。
2分木へのデータの追加について 中の回答例
2分木のデータ追加、サーチ、削除について 中の回答例

追記: (2015-01-21)

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

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

追記: (2015-01-18)

  • 次のページを見つけた。詳細を検討中 ...
    Print a Binary Tree
    How to print binary tree diagram?

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

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

            x
      /----- -----\
      x           x
   /-- --\     /-- --\
  x      x     x     x
 / \    / \   / \   / \
 x x    x x   x x   x x
1
  • 1
    単純に考えて要素の最大表示幅(全ての要素を調べる必要がある)と深さを決定してからでないとバランスよく表示することはできないと思います。
    – BLUEPIXY
    Commented 2015年1月17日 12:14

6 件の回答 6

5

2分木のデータ追加、サーチ、削除について のコードに追加する形で書いてみました。

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)

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

実行結果は以下の様になります。

     _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

Binary Tree

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

4

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

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

レイアウト

     __9__
    /     \
   4       15
  /\      / \
 2  6    12  17

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

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

    1. 下線と数字からなる行 (__9__2 6 12 17)

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

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

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

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

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

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

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

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

座標の計算

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

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

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

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

横幅とX座標の計算

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

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

# 描画に必要な横幅を計算
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

縦幅とY座標の計算

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

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

# 描画に必要な縦幅の計算
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

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

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

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

# 描画に必要な情報を計算
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

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

     __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"]]

座標データからプリント

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

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

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

   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)

左右の下線の追加

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

>> print_canvas2 render(tree)
  _9__
 4    15
2 6 12  17

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

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

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

               _____30___
  ___________9__        _9__
 4              15     4    15
2 6___        12  17  2 6 12  17
     _9__
    4    15
   2 6 12  17

斜線の追加

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

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

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

     __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行目
]

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

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

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

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

余白

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

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

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

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

まとめ

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

2

C#ですが書いてみました。リンク先の46行目~97行目が表示処理です。出力は横向きです。

61--62
└--63--02--04
    │  └--14
    └--10--45
        └--68

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

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

1
  • 2分木へのデータの追加について ja.stackoverflow.com/questions/4704 の回答に横型で出力する例を追記しました。 こちらの出力書式の場合、node の値の桁数の影響は受けないようになってます。
    – katoy
    Commented 2015年1月18日 3:35
2

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

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

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

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();
}
2

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

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

意図したこと

レイアウト目標

    161 
  ---|---  
 /       \   
146     182  
        -|-                   
       /   \  
      162 185 

動作目標

出力する前に、

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

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

ソースコード

bitree_print.go: (1 ファイル)

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
}

出力

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

                         7
          ---------------|---------------                 
         /                               \                
         1                               7
  -------|-------                                         
 /               \                                        
 0               3                                
 |---         ---|---                                     
     \       /       \                                    
     0       2       5                                
     |-     -|      -|-                                   
       \   /       /   \                                  
       0   1       4   5                                
           |       |   |                                  
            \     / \   \                                 
            1     3 4   5                         

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

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

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

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

デバッグ時の様子

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
2

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

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

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

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

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

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

修正後の出力

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。