解説 6月14日B

今回の学習項目です。


キューと横型探索

6月7日Aの講義で、 先行順、中間順、後行順という3通りの二進木のなぞりを学びました。 ここでは「横型探索」という新しい木のなぞり方を学びます。
木の横型探索では、深さ順に頂点が探索されます。つまり最初に深さ0である根の頂点、 次に深さ1である根の子頂点、深さ2である根の孫頂点...というように探索されます。 木のなぞり方が頂点を深さごとに横になぞっていくように見えます。

課題1-1

二進木の頂点を表すためのクラスNodeをRubyで次のように表すとします:
   class Node   # クラスの定義の始まり
        def initialize(l, x=nil, y=nil)  # インスタンスを作るためのメソッド
            @label = l      # label(頂点のラベル)を表す「要素」を定義
            @left = x       # left son(左の子)を表す「要素」を定義
            @right = y      # right son(右の子)を表す「要素」を定義
        end  # of def
        attr_accessor :label, :left, :right   # インスタンス変数へのアクセスを可能にする
       def breadthFirst  # 横型探索
           nodes = [ ]    # 答えを返すための配列
           agenda = Queue.new(100)  # 大きさ100のキュー
           agenda.enqueue(self)       # キューに自分自身をいれる
           while (! agenda.empty)   # キューに要素がある限り
             x = agenda.dequeue  # キューから要素を取り出す
             nodes = nodes + [x.label]   # 要素のラベルを記録
             agenda.enqueue(x.left) if x.left != nil   # 左の子頂点をキューにいれる
             agenda.enqueue(x.right) if x.right != nil  # 右の子頂点をキューにいれる
          end   # while
         return nodes   # 頂点のラベルの配列を返す
       end  # def of breadthFirst
   end  # of Class
これはVertexクラスと異なり、親頂点や兄弟頂点へのポインタは持たず、 それぞれの頂点の左の子頂点と右の子頂点へのポインタだけをもつ定義となっています。

6月7日Bの講義課題1-2で書いた二進木を、 このNodeクラスを用いて表しなさい。ただし、 この根頂点が変数rの値となっているとします。
[ヒント]

例で示します。
例えば 12 + 4という数式をNodeクラスを使って表すには、次のようにします。 ここで、根頂点が変数rの値です。また、書き方の順番があることに注意 してください。つまり、葉の頂点(のインスタンス)から作らないといけません。
 leftSon = Node.new("12", nil, nil)       # 12をラベルとし、左も右も子なし
 rightSon = Node.new("4", nil, nil)       # 4をラベルとし、左も右も子もなし
 r = Node.new("+",leftSon, rightSon)      # +が根、12が左、4が右の子

課題1-2

この課題では、6月14日Aの講義課題2-2で定義したクラスQueueをここで使います。
課題1-1で作成した二進木r.breadthFirstの結果はどのようなものでしょうか、予想して書きなさい。 また、プログラムを実行して、その結果と比較しなさい。
注意: Queue クラスが完成していないとエラーになります。 ちゃんと完成させてからこの課題に取り組んでください。

課題1-3

課題1-2では二進木に対して横型探索を行いましたが、 この課題では一般の木に対して横型探索を行ってみましょう。そのために 5月10日Bの講義で扱った「木の頂点を表すためのクラスVertex」 を用います。以下に再掲します:

   class Vertex   # クラスの定義の始まり
        def initialize(l, p = nil, b = nil, f = nil)  # インスタンスを作るためのメソッド
            @label = l      # label(頂点のラベル)を表す「要素」を定義
            @parent = p        # parent(親)を表す「要素」を定義
            @nextBrother = b   # nextBrother(次の兄弟)を表す「要素」を定義
            @firstChild = f    # firstChild(第1子)を表す「要素」を定義
        end  # of def
        attr_accessor :label,:parent, :firstChild, :nextBrother   # インスタンス変数へのアクセスを可能にする
   end  # of Class
横型探索を行う breadthFirst関数をこのクラスのメソッドとして書きなさい。 また、適当な大きさの木をこのクラスを用いて表現し、その根頂点に対してbreadthFirstを実行した時に、 横型探索がちゃんと行われることを確かめなさい。
[ヒント(1)]
この問題を解くには、「(ある頂点にたいする)子頂点すべてからなる配列」を求めるメソッドを作っておくとよい。そのメソッドの名前をchildrenとすると、その定義は以下のようになるだろう:
   class Vertex   # クラスの定義の始まり
        def initialize(l, p = nil, b = nil, f = nil)  # インスタンスを作るためのメソッド
             # 内容を省略
        end  
        attr_accessor :label,:parent, :firstChild, :nextBrother   # インスタンス変数へのアクセスを可能にする
        def children()   # 子頂点の配列を返す
           nodes = []
           c = @firstChild   # 第1子の頂点
           while c != nil    # 子頂点がある限りくり返し
               nodes << c         # 頂点を記録
               c = c.nextBrother  # 兄弟頂点
           end # while
           return nodes
        end  # of def
   end  # of Class
[ヒント(2)]
横型探索を行う breadthFirstメソッドは概略以下のようになるだろう(二進木の場合と比較せよ):
   class Vertex   # クラスの定義の始まり
        def initialize(l, p = nil, b = nil, f = nil)  # インスタンスを作るためのメソッド
             # 内容を省略
        end  
        attr_accessor :label,:parent, :firstChild, :nextBrother   # インスタンス変数へのアクセスを可能にする
        def children()   # 子頂点の配列を返す
             # 内容を省略
        end  # of def
       def breadthFirst  # 横型探索
           nodes = [ ]    # 答えを返すための配列
           agenda = Queue.new(100)  # 大きさ100のキュー
           agenda.enqueue(self)       # キューに自分自身をいれる
           while (! agenda.empty)   # キューに要素がある限り
                   # (コードを書く)キューから要素を取り出し、その値をxとする
             nodes = nodes + [x.label]   # 要素のラベルを記録
             for v in x.children()  # xの子頂点それぞれ(v)に対して
                       #  (コードを書く)子頂点をキューにいれる
             end # for
          end   # while
          return nodes
       end  # def of breadthFirst
   end  # of Class

「アルゴリズムとデータ構造」のホームに戻る