アルゴリズムとデータ構造の要点メモ in ruby（二分木）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f
キュー https://qiita.com/tsnb/items/588afe675ad830ff1fc6

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

二分木（データ構造）

要点

二分木とは、葉以外のすべての節が、２つ以下の子を持つような木構造、
必ず２つの子を持つようならば、全二分木、
どの葉も同じ深さにある場合は、完全二分木

struct Node_tag {
    int                   value;
    struct Node_tag*      left;
    struct Node_tag*      right;
};

• 木構造は、親をたどる必要性がない場合もよくある

アルゴリズム

走査（トラバース）

「すべてをもらさず」「同じものを重複せず」に、二分木に含まれるすべての節を調べたい

• 探索方法
  • 深さ優先探索
    • 行きがけ順探索 pre
    • 通りがけ順探索 in => 結果がソートされている
    • 帰りがけ順探索 post
  • 幅優先探索

深さ優先探索の実装

• まずは深さ優先探索を実装
• add_left, add_rightで木を追加
• pre, in, postを実装
• 再帰で実装、スタックとループは余力があれば・・

class Node
  attr_accessor :val, :left, :right

  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end

  def add_left(val)
    self.left = Node.new(val)
  end

  def add_right(val)
    self.right = Node.new(val)
  end
end

class BinaryTree
  attr_reader :head, :list

  def initialize(val)
    @head = Node.new(val)
    @list = []
  end

  def pre
    @list = []
    traverse(@head, :pre)
    @list
  end

  def in
    @list = []
    traverse(@head, :in)
    @list
  end

  def post
    @list = []
    traverse(@head, :post)
    @list
  end

private
  def traverse(node, type=:pre)
    @list << node.val             if type == :pre
    traverse(node.left, type)     if !!node.left
    @list << node.val             if type == :in
    traverse(node.right, type)    if !!node.right
    @list << node.val             if type == :post
  end
end

手動で木を作って、探索〜
以下の資料の木構造と同じように作って結果も一致することを確認した
http://www-ikn.ist.hokudai.ac.jp/~arim/pub/algo/algo6.pdf

irb(main):270:0> bt = BinaryTree.new(7)
=> #<BinaryTree:0x00007fa0cf86fc78 @head=#<Node:0x00007fa0cf86fc50 @val=7, @left=nil, @right=nil>, @list=[]>
irb(main):271:0> bt.head.add_left(3)
=> #<Node:0x00007fa0cf86c4b0 @val=3, @left=nil, @right=nil>
irb(main):272:0> bt.head.left.add_left(1)
=> #<Node:0x00007fa0cf864648 @val=1, @left=nil, @right=nil>
irb(main):273:0> bt.head.left.add_right(4)
=> #<Node:0x00007fa0d082c648 @val=4, @left=nil, @right=nil>
irb(main):274:0> bt.head.left.right.add_right(6)
=> #<Node:0x00007fa0cf85ff80 @val=6, @left=nil, @right=nil>
irb(main):275:0> bt.head.left.right.right.add_left(5)
=> #<Node:0x00007fa0cf853000 @val=5, @left=nil, @right=nil>
irb(main):276:0> bt.head.add_right(10)
=> #<Node:0x00007fa0ce8cb858 @val=10, @left=nil, @right=nil>
irb(main):277:0> bt.head.right.add_left(8)
=> #<Node:0x00007fa0d0827490 @val=8, @left=nil, @right=nil>
irb(main):278:0> bt
=> #<BinaryTree:0x00007fa0cf86fc78 @head=#<Node:0x00007fa0cf86fc50 @val=7, @left=#<Node:0x00007fa0cf86c4b0 @val=3, @left=#<Node:0x00007fa0cf864648 @val=1, @left=nil, @right=nil>, @right=#<Node:0x00007fa0d082c648 @val=4, @left=nil, @right=#<Node:0x00007fa0cf85ff80 @val=6, @left=#<Node:0x00007fa0cf853000 @val=5, @left=nil, @right=nil>, @right=nil>>>, @right=#<Node:0x00007fa0ce8cb858 @val=10, @left=#<Node:0x00007fa0d0827490 @val=8, @left=nil, @right=nil>, @right=nil>>, @list=[]>
irb(main):279:0> bt.pre
=> [7, 3, 1, 4, 6, 5, 10, 8]
irb(main):280:0> bt.in
=> [1, 3, 4, 5, 6, 7, 8, 10]
irb(main):281:0> bt.post
=> [1, 5, 6, 4, 3, 8, 10, 7]

幅優先探索の実装

• キューと再帰で実装

class Node
  attr_accessor :val, :left, :right

  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end

  def add_left(val)
    self.left = Node.new(val)
  end

  def add_right(val)
    self.right = Node.new(val)
  end
end

class BinaryTree
  attr_reader :head, :list

  def initialize(val)
    @head = Node.new(val)
    @list = []
    @queue = []
  end

  def bfs
    @list = []
    traverse(@head)
  end

private
  def traverse(node)
    return @list if node.nil?

    @list << node.val
    @queue << node.left if !!node.left
    @queue << node.right if !!node.right
    node = @queue.shift
    traverse(node)
  end
end

irb(main):136:0> bt = BinaryTree.new(7)
=> #<BinaryTree:0x00007fbd20833850 @head=#<Node:0x00007fbd20833828 @val=7, @left=nil, @right=nil>, @list=[], @queue=[]>
irb(main):137:0> bt.head.add_left(3)
=> #<Node:0x00007fbd20841220 @val=3, @left=nil, @right=nil>
irb(main):138:0> bt.head.left.add_left(1)
=> #<Node:0x00007fbd2082aa70 @val=1, @left=nil, @right=nil>
irb(main):139:0> bt.head.left.add_right(4)
=> #<Node:0x00007fbd1f0c3f08 @val=4, @left=nil, @right=nil>
irb(main):140:0> bt.head.left.right.add_right(6)
=> #<Node:0x00007fbd1f0b8d38 @val=6, @left=nil, @right=nil>
irb(main):141:0> bt.head.left.right.right.add_left(5)
=> #<Node:0x00007fbd1f0a8870 @val=5, @left=nil, @right=nil>
irb(main):142:0> bt.head.add_right(10)
=> #<Node:0x00007fbd1f093d30 @val=10, @left=nil, @right=nil>
irb(main):143:0> bt.head.right.add_left(8)
=> #<Node:0x00007fbd1f080708 @val=8, @left=nil, @right=nil>
irb(main):144:0> bt.bfs
=> [7, 3, 10, 1, 4, 8, 6, 5]