在籍している大学の「アルゴリズム」科目の教科書である『基礎から学ぶデータ構造とアルゴリズム』を読んでいる。1月に試験があるのだ。

この記事は「2.4.3 木の走査」の勉強メモです。

走査する二分木

木構造

深さ優先探索のコード例(example.rb)

class Node
  attr_accessor :data, :left, :right
  def initialize(data)
    @data = data
  end
end

# 先行順
def preorder(node)
  return if node.nil?
  print node.data
  preorder(node.left)
  preorder(node.right)
end

# 中間順
def inorder(node)
  return if node.nil?
  inorder(node.left)
  print node.data
  inorder(node.right)
end

# 後行順
def postorder(node)
  return if node.nil?
  postorder(node.left)
  postorder(node.right)
  print node.data
end

# 二分木を作る
a = Node.new("A")
b = Node.new("B")
c = Node.new("C")
d = Node.new("D")
e = Node.new("E")
f = Node.new("F")
g = Node.new("G")
a.left = b; a.right = c
b.left = d; b.right = e
c.left = f; c.right = g

preorder  a; puts
inorder   a; puts
postorder a; puts

実行結果

$ ruby example.rb
ABDECFG
DBEAFCG
DEBFGCA