Ruby で Tree 構造を作る

これは非常に未熟な記事です。特に初心者の方はあまりこの記事を真に受けないで下さい。（2019/5/22）

---

※注意
ここでさらに一般的な Tree の例を与えてあります。そちらをどうぞ。

Rubyクックブック ―エキスパートのための応用レシピ集

p.51-52

Tree#addchild メソッドで、親から子を作り出します。Tree#each メソッドで、そこからのすべての子孫をトラバースします。

class Tree
  def initialize(value)
    @value = value
    @children = []
  end
  attr_reader :children
  
  def addchild(value1)
    child = Tree.new(value1)
    @children << child
    return child
  end
  
  def each
    yield(@value)
    @children.each do |child|     #ここはArray#each
      child.each {|c| yield(c)}   #ここはTree#eachで、再帰する
    end
  end
end

pa = Tree.new("Taro")
child1 = pa.addchild("Masao")
child2 = pa.addchild("Ryouko")
child1.addchild("Kimiko")
child2.addchild("Tamaki")
cld = child1.addchild("Toshi").addchild("Hazuki")

pa.each {|person| p person}

結果

"Taro"
"Masao"
"Kimiko"
"Toshi"
"Hazuki"
"Ryouko"
"Tamaki"

親は Taro、その子供は Masao, Ryouko です。Masao の子供が Kimiko, Toshi、Toshi の子供が Hazuki です。また、Ryouko の子供が Tamaki です。直系から先に出力されます。図式化すると下のようになります。

"Taro"　--"Masao" --"Kimiko"
                  --"Toshi" --"Hazuki"
        --"Ryouko" --"Tamaki"

なお、Ruby の変数は動的型付けなので、入れるデータは文字列とは限りません。任意のものが入ります。データや子孫オブジェクトにアクセスしたければ、クラス内に attr_accessor : value, :children を加えればよいです。

ただこれ、子のもっている情報の中に、親に関する情報が一切入っていないのですよね。だから、子からその親のオブジェクトを得ることができない（※追記）。これは原理的な問題ですね。子の中に親の情報を含めると、その親の情報の中には子の情報が入っているので、情報がネストしてしまう。

ではいちばん上の親（pa）にはすべての子孫の情報が入っているから、これを与えておいて、さらに任意の子孫の親を出力することはできる筈。というのでやってみた。上のスクリプトにさらに以下を追加。

class Tree
  def get_parent(root)
    gp = proc do |par, s|
      par.children.each {|child| return par if child == s}
      par.children.each {|child| gp.call(child, s)}
    end
    
    return nil if root == self
    gp.call(root, self)
  end
end

p cld.get_parent(pa)    #"Hazuki"の親のオブジェクトを与える
##<Tree:*** @value="Toshi", @children=[#<Tree:*** @value="Hazuki", @children=[]>]>

確かに可能になりました。

※追記
親の情報を子に持たせるのは簡単でした。上を以下のとおりに書き換えればよいです。インスタンス変数 @parent を追加しました。例では "Hazuki" の親をすべて出力します。

class Tree
  def initialize(value)
    @value = value
    @children = []
    @parent = nil
  end
  attr_reader :children, :value
  attr_accessor :parent
  
  def addchild(value1)
    child = Tree.new(value1)
    @children << child
    child.parent = self
    return child
  end
end

child = cld
while c = child.parent
  p c.value
  child = c
end

結果

"Toshi"
"Masao"
"Taro"