二分木のAA http://ja.stackoverflow.com/questions/4739/ http://ideone.com/Yaw8k3

aa_tree.rb

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

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

#    9
#  4    15
# 2 6 12  17
 
# このメソッドはクラス外でOK
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|
    text = node.value.to_s
 
    # y座標が増えたら改行
    if y != last_y
      last_x = 0
      puts
    end
 
    # 必要な分だけスペースを入れてプリント
    print " " * (x - last_x)
    print text
 
        # カーソルを進める
    last_x = x + text.to_s.size
    last_y = y
  end
  puts
end
 
#   _9__
#  4    15
# 2 6 12  17
 
def print_canvas2(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }
 
  last_x = 0
  last_y = 0
 
  # 各ノードをループで描画
  canvas.each do |x, y, node|
    text = node.value.to_s
 
    if y != last_y
      last_x = 0
      puts
    end
 
    if node.left
       # 「次の行の数字で、この数字のすぐ左にあるもの」を探してX座標をとる
      ileft = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx } - 1
      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
 
    print text
 
    x += text.to_s.size
 
    # 数字右側の下線
    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
 
    last_x = x
    last_y = y
  end
  puts
end
 
#    9_
#   /  \
#  4    15
# 2 6 12  17
 
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|
      text = node.value.to_s
 
      # 数字左側の下線
      if node.left
        next_line = canvas_lines[y + 1]
        ileft = next_line.index {|nx, *| x <= nx } - 1
        left_x, * = next_line[ileft]
        left_x_end = left_x + node.left.value.to_s.size
        print " " * (left_x_end - last_x)
        if left_x_end < x
          # 下線の左端を欠けさせる (スペースにする)
          print " "
          print "_" * (x - left_x_end - 1)
          # 斜線の描画を予約 (左手ノードなのでスラッシュ)
          slashes << [left_x_end, '/']
        end
      else
        print " " * (x - last_x)
      end
 
      print text
 
      x += text.to_s.size
 
      # 数字右側の下線
      if node.right
        next_line = canvas_lines[y + 1]
        iright = next_line.index {|nx, *| x <= nx }
        right_x, * = next_line[iright]
 
        if x < right_x
          # 下線の右端を欠けさせる (スペースにする)
          print "_" * (right_x - x - 1)
          print " "
          # 斜線の描画を予約 (右手ノードなのでバックスラッシュ)
          slashes << [right_x - 1, '\\']
        end
        x = right_x
      end
 
      last_x = x
    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
 
# ツリーの宣言を短く書くために定義
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)
print_canvas3 render(tree)
print_canvas3 render(Node(4, tree, tree))
print_canvas3 render(Node(4, tree, tree), 2)
print_canvas3 render(Node(4, Node(4), tree), 1)

# バグ: 右手にノードがないと落ちる
# print_canvas3 render(Node(4, tree, nil), 1) 

aa_tree_refactored.rb

# 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

output.txt

   9
 4    15
2 6 12  17
  _9__
 4    15
2 6 12  17
   9_
  /  \
 4    15
2 6 12  17
     _____4__
    /        \
   9_         9_
  /  \       /  \
 4    15    4    15
2 6 12  17 2 6 12  17
        _________4______
       /                \
    __9___             __9___
   /      \           /      \
  4        15        4        15
 / \      /  \      / \      /  \
2   6   12    17   2   6   12    17
                          _4__________
                         /            \
           _____________9          ____9_____
          /                       /          \
     ____9_____                 _4_          _15_
    /          \               /   \        /    \
  _4_          _15_           2     6     12      17
 /   \        /    \
2     6     12      17
              _________________4______________
             /                                \
      ______9_______                     ______9_______
     /              \                   /              \
  __4__            __15__            __4__            __15__
 /     \          /      \          /     \          /      \
2       6       12        17       2       6       12        17