二分探索木 木構造において、各節点の子の数が２以下であり、左の子と右の子を区別して扱う時、その木を 二分木 +% という。二分木の各節点に互いに異なる要素を対応付けるものとする。こ とするとき、その左部分木（左の子を根とする部分木）内の要素はすべ て より小さく、右部分木（右の子を根とする部分木）内の要素はすべて より大きいものとす の時、ある節点の要素を る。このような二分木を二分探索木 +% という。 ここでは、二分探索木を用いて、与えられた英語のテキストファイルに含まれる異なる単語の個 数と、異なる単語の一覧を辞書式順序で出力するプログラムを考える。 例えば、英語のテキストファイルの内容が )$ $ # であった場合、 9 )$ # $ と出力するものとする。ここで 行目の「M」はファイルに含まれる異なる単語の個数、続いて M 個の異なる単語を辞書式順に出力している。 これを実現するために、まず要素として単語を持つ二分探索木を以下のようにして構築する。 最初、空の二分探索木を用意し、それに最初の単語「 」を追加する。.図 &.// $ この二分探索木に二番目の単語「」を追加する。辞書式順において「」+「 」なの で、「」は「 」の左側の子として追加される。.図 &. // % 次の単語「」は、「」+「 」なので、「 」の左側の子「」と比較する。「」, 「」なので「」は「」の右側の子として追加される。.図 &.// & 次の単語「 "」は、「 "」+「 」、「 」の左側の子「」+「 "」、「」の右側の 子「」+「 "」なので、「」の右側の子として追加される。.図 &.*// ' 次の単語「」は、 「」,「 」なので、 「 」の右側の子として追加される。.図 &. // ( 次の単語「 "」は、「 "」+「 」、「 」の左側の子「」+「 "」、「」の右側の 子「」+「 "」、 「」の右側の子は「 "」であり「 "」は既に登録されているので、何 もしない。 M 次の単語「」は、「」+「 」、「 」の左側の子は「」であり「」は既に登録 されているので、何もしない。 「茨木俊秀著：0 によるアルゴリズムとデータ構造、6 節、オーム社」参照 (a) (b) (c) (d) this this this this is < this my < this this is pen < this is is is is < my is < pen my my my < pen my pen (e) (f) (g) this this this pen < this is < this this < your is there < this over < this is your is < pen your my pen your my my < over my < pen your pen is is is < there is < over my pen my < there pen pen pen over < pen pen < there over over over there there 図 ) 単語の二分探索木 次の単語「0 」は、「0 」+「 」、「 」の左側の子「」+「0 」、「」の右 側の子「」+「0 」、 「」の右側の子「 "」,「0 」なので「 "」の左側の子とし て追加される。.図 &.// 最後の単語「 」は、「 」+「 」、「 」の左側の子「」+「 」、「」 の右側の子「」+「 」、 「」の右側の子「 "」+「 」なので「 "」の右側の 子として追加される。.図 &.// ( 番目と M 番目の単語のように、既に二分探索木に登録されている単語が出てきたときは何もしな いので、この二分探索木には異なる単語だけが登録されることになる。 単語を要素として持つ二分探索木の節点は、次のような構造体で表せる。 <$ * <$ <$ L , この節点に登録する単語 &文字列なので 型へのポインター' 左側の子節点へのポインター。無い場合は HIGG 右側の子節点へのポインター。無い場合は HIGG また、二分探索木は、その根節点へのポインターとして表せばよい。 <$ 構造体 <$ へのポインターを値とする変数。 二分探索木の根節点へのポインターを入れる。 値 HIGG は空の二分探索木を表す。 単語を追加するアルゴリズムを 節点へのポインター ), 追加する単語 . としてま とめると、 が JKK なら、* を要素として持つ節点を作成し、それを根節点として戻る。 $ が指す節点に登録されている単語を * とする。 % * と * が等しければ何もせず戻る。 & * + * の時、左側の子が存在すれば再帰的に " .左側の子節点へのポインター# */ を呼び出して戻る。左側の子が存在しなければ、* を要素として持つ節点を作成 し、それを左側の子として戻る。 ' * , * の時、右側の子が存在すれば再帰的に " .右側の子節点へのポインター# */ を呼び出して戻る。右側の子が存在しなければ、* を要素として持つ節点を作成 し、それを右側の子として戻る。 のようになる。 二つの文字列の比較は標準ライブラリにある関数 " . -# -$/ で行え る。この関数は、文字列 が文字列 $ より小さいときは負の値、文字列 が文字列 $ より大 きいときは正の値、文字列 と文字列 $ が同じ文字列の時は を返す。 二分探索木の節点数を求める関数を 節点へのポインター ) とすると、これは が JKK なら を返す。 $ が JKK でないなら、". が指す節点の左側の子へのポインター/ : ". が 指す節点の右側の子へのポインター/ : を返す。 比較は文字コードによる辞書式比較となる。D # の =>/ では、半角英語大文字の文字コードは半角英語小 文字の文字コードよりも小さいため、大文字と小文字が混じった文字列を $5 で比較する場合、現実の辞書の中で並 ぶ順番とは異なる結果になる場合がある。 のように計算できる。 二分探索木に登録されている単語を大きさの順に出力するためには、二分探索木を深さ優先探索 し、"* で節点に登録されている単語を出力すれば良い。これを実現する関数を )節点 へのポインター ) とすると、これは が JKK なら何もせずにもどる。 $ ". が指す節点の左側の子節点へのポインター/ を呼び出す。 % が指す節点に登録されている単語を出力する。 & ". が指す節点の右側の子節点へのポインター/ を呼び出す。 のように実現できる。 演習 %% 上記で説明したプログラムを作成し、 4 4 4 に適用せよ。な お、単語の長さは 以下で英小文字のみからなると仮定しても良い。 ヒント 関数 " や " は、読み込むデータが無くなった場合 D を返す。また、「文字 列 .6/」として読み込む場合、空白文字や改行文字は単語の区切りと解釈され、単語単位で 読み込まれる。したがって、適当な大きさの文字型の配列 を用意しておけば、 ! .".464# / O5 D/2 " .# /3 ; で、入力された単語を一つずつ二分探索木に登録していくことができる。 ヒント 新しい節点を作成する方法は、第 ( 章 リスト構造 の <** 関数が参考になる。 左側の部分木に登録されている単語を ' で出力し、次に自分自身に登録されている単語を出力し、最後に右側 の部分木に登録されている単語を ' で出力する。
© Copyright 2024 ExpyDoc
