Ruby で Tree構造（その３）

これまでとは別の実装をしてみました（前回）。前回はノードは何でもよかったのですが、今度は Node クラスを作っています。そして、Node インスタンスとその値（value）を別にしています。Tree クラスに Node インスタンスを登録していて、Node インスタンスの重複は認められませんが、その value の重複は許します。

tree1.rb

class Node
  def initialize(value, parent)    #根（root）のノードは、parentをnilにしておくこと
    @value = value
    @parent = parent
    @children = []
  end
  attr_accessor :value, :parent, :children
  
  def to_s
    "#{@value}"
  end
  
  def inspect
    pa_v = @parent ? "'#{@parent.value}'" : "nil"
    "<#Node: value='#{@value}', parent=#{pa_v}, children.size=#{@children.size}>"
  end
end

class Tree
  def initialize(root)
    @root = root
    @nodes = [@root]
  end
  attr_reader :root, :nodes
  
  def add(parent, value)
    raise "The parent does not exist." unless @nodes.include?(parent)
    @nodes << (n = Node.new(value, parent))
    parent.children << n
    n
  end
  
  def add_node(node)
    parent = node.parent
    raise "The parent does not exist." unless @nodes.include?(parent)
    raise "The node already exists." if @nodes.include?(node)
    @nodes << node
    parent.children << node
    node
  end
  
  def get_nodes(start, goal)
    raise "The start node does not exits." unless @nodes.include?(start)
    raise "The goal node does not exits." unless @nodes.include?(goal)
    ar = [goal]
    return ar if start == goal
    node = goal
    until node == start
      node = node.parent
      return ar unless node
      ar.unshift(node)
    end
    ar
  end
  
  #すべての祖先を返す
  def ancestors(node)
    get_nodes(@root, node)[0..-2]
  end
  
  #値valueをもつ最も近い祖先を返す
  def ancestor_has_value(node, value)
    return nil unless (pa = node.parent)
    return pa if pa.value == value
    ancestor_has_value(pa, value)
  end
  
  def self.make(ar)
    raise "Argument is not Array." if ar.class != Array
    t = Tree.new(ar[0][0])
    ar.each do |ar1|
      ar1[1].each {|child_value| t.add(t.node_has_value(ar1[0]), child_value)}
    end
    t
  end
  
  #値valueをもつノードを返す。valueは唯一でなければならない。そうでなければ不定値が返る。
  def node_has_value(value)
    @nodes.each {|node| return node if node.value == value}
    nil
  end
  alias :nhv :node_has_value
  
  def put_out
    po2(@root, 0)
    puts
  end
  
  def po2(node, l)
    st = "--#{node} "
    print st
    nc = node.children
    return if nc.empty?
    nc.each_with_index do |child, i|
      if i.zero?
        l += st.length
      else
        puts
        print " " * l
      end
      po2(child, l)
    end
  end
  private :po2
  
  def max_depth(node=@root)
    max = 0
    bfs(node) {|nd, d| max = d if max < d}
    max
  end
  
  def delete(node)
    raise "can not delete: no node" unless @nodes.include?(node)
    q = [node]
    begin
      node = q.pop
      @nodes.delete(node)
      node.parent.children.delete(node)
      chi = node.children
      unless chi.empty?
	chi.each {|c| q.push(c)}
      end
    end until q.empty?
  end
  
  #ノードstartから値goal_valueを深さ優先探索する。存在すれば深さを、存在しなければfalseを返す。
  def dfs(start=@root, goal_value=nil)
    q = [[start, 0]]
    while !q.empty?
      node, depth = q.pop
      yield(node, depth) if block_given?
      return depth if node.value == goal_value
      node.children.reverse_each do |child|
        q.push([child, depth + 1])
      end
    end
    false
  end
  
  #幅優先探索
  def bfs(start=@root, goal_value=nil)
    start = @root unless start
    q = [[start, 0]]
    while !q.empty?
      node, depth = q.shift
      yield(node, depth) if block_given?
      return depth if node.value == goal_value
      node.children.each do |child|
        q.push([child, depth + 1])
      end
    end
    false
  end
end