サンプルを書いてみました。順を追って作った経緯を説明します。
ソース: https://gist.github.com/snipsnipsnip/0e267f6a39cc2397da3d
動作: http://ideone.com/Yaw8k3 http://ideone.com/9iuF6e
レイアウト
__9__
/ \
4 15
/\ / \
2 6 12 17
katoyさんの例からレイアウトの仕様を考えてみます。
- 縦方向は以下の内容を交互に表示します。
- 下線と数字からなる行 (
__9__
や 2 6 12 17
)
- 斜線の行 (
/\ / \
)
- 横方向には、以下のルールで数字を配置します。
- 親ノードの数字より左に、左の子ノードの数字を置く
- 親ノードの数字より右に、右の子ノードの数字を置く
- 一つの桁には数字を一つだけ置く(数字の上下に数字は現れない)
この仕様だと、横幅は次のように再帰的に計算できます。
- ノードの描画に必要な横幅 =
ノードの持つ数値の桁数 +
左手の子ノードの描画幅 (なければ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
座標計算を配列にまとめる
上のwidth
、height
ではプリントするだけでしたが、代わりに配列にまとめる関数を作ります。
ついでに、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 } - 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
まとめ
座標計算で通りがけ順の深さ優先探索をするところがコツだと思います。
表示自体にはあまり木構造らしい処理は必要ありませんでした。