天泣記

再帰を使わないで深さ優先探索と幅優先探索は、データ構造がスタックかキューかだけの違い、と昔習った

しかし、ふと、そうやって深さ優先探索を行うと、帰りがけ順に処理を行うことができないことに気がついた

例えば、再帰を使わない深さ優先探索は以下のように実装できるだろう

% cat preorder.rb
Node = Struct.new(:value, :left, :right)

def n(v, l=nil, r=nil)
  Node.new(v, l, r)
end

tree =
  n(1,
    n(2,
      n(3),
      n(4)),
    n(5,
      n(6),
      n(7)))

stack = [tree]
until stack.empty?
  n = stack.pop
  p n.value
  stack.push n.right if n.right
  stack.push n.left if n.left
end
% ruby preorder.rb
1
2
3
4
5
6
7

ここで、この実装で p n.value というのは行きがけ順に実行される

では、帰りがけ順に処理を行いたいときにはどうしたらいいだろうか

再帰を使う深さ優先探索ならこれは簡単で、子ノードを再帰的に処理した後に処理を行えばよい (行きがけ順に行う処理は子ノードを再帰的に処理する前に行う)

しかし、再帰を使わない場合は、そういう帰りがけ順の処理になるちょうどいい場所がない

考えてみると、子ノードを再帰的に処理した後に行う、というのは、最後の子ノードを処理した後の継続 (帰りがけ順の処理をした後に上のノードに return する) がマシンスタックとして表現されているわけで、データとしてスタックを表現する場合でもその継続と同じ意味のデータが必要なのだろう

というわけで実装してみると、以下のようにすれば、再帰を使わずに、深さ優先探索で帰りがけ順の処理を行える

% cat postorder.rb
Node = Struct.new(:value, :left, :right)

def n(v, l=nil, r=nil)
  Node.new(v, l, r)
end

tree =
  n(1,
    n(2,
      n(3),
      n(4)),
    n(5,
      n(6),
      n(7)))

stack = [[:pre, tree]]
until stack.empty?
  tag, n = stack.pop
  case tag
  when :pre
    stack.push [:post, n]
    stack.push [:pre, n.right] if n.right
    stack.push [:pre, n.left] if n.left
  when :post
    p n.value
  end
end
% ruby postorder.rb
3
4
2
6
7
5
1

天泣記

2021-04-29 (Thu)