list, tree
リスト，ツリー

12章つづき

12.4 連結リスト

連結リストでは，スタックやキューと異なり，途中への要素の挿入， 途中の要素の削除ができる．そのぶんアルゴリズムは複雑であるが，基本は 前々回のプログラムlist12x6.c の，リストの内容を先頭から順に出力する関数 printList での処理の cPtr が NULL でない間 cPtr = cPtr->nextPtr を続けるループ である．これによりリストをスキャンするヘッドの役割をするポインタ変数 cPtr を最初の要素のポインタから最後の要素のポインタまで順に変更する ことができる．

リスト 12.1 は各要素が char 型の連結リスト を扱うプログラムで，リスト中の要素の文字コードが 小さいものから順に格納されているという性質を常に満たすようになっている． 実行し，リスト 12.2 を参考にテストせよ．

スタック，キューと比較して追加された機能はリスト途中への挿入， 途中からの削除である．どちらの場合でも最初にリストをスキャンするヘッド用の ポインタ変数 currentPtr について， currentPtr = currentPtr->nexpPtr の代入を繰り返しながら 処理すべきところまでリストを読み進める構造が基本となる． 挿入する場合と削除する場合のポインタのつなぎかえは教科書の図 12.3, 12.4 を参照せよ．

insert, delete いずれも 挿入，削除すべき位置の要素のポインタを知っただけでは不足で， その前の順番の要素のポインタも必要となる．今回説明している たん方向リストでは一つ前の要素に簡単にアクセスすることはできないので， 最初からメインのヘッダである currentPtr の他に，常に currentPtr の一つ前を指すヘッダ用のポインタ変数 previousPtr を利用している． previousPtr と currentPtr を 1 個づつ進めるには， previousPtr には古い currentPtr の値を代入した後 currentPtr には次の要素の位置である　currentPtr->nextPtr を代入することで行っている．

delete の場合は削除すべき位置の前の要素の値を書き換える必要がある． （削除要素の前の要素の nextPtr フィールドを書き換えて， 削除要素の次にあった要素へのポインタの値に変更する） 先頭要素の削除の場合だは削除すべき位置は *sPtr となり， その前に相当するものは sPtr となる． これは LISTNODEPTR 型へのポインタ型で， LISTNODEPTR　型変数である previousPtr を使うことができない． リスト 12.1 の delete 関数ではこの理由で削除要素が先頭だったときの 処理だけループとは別に行っている．

教科書 p.445 の scanf("\n%c", &item); の処理につていて説明する． もし \n が無ければ，前に処理番号 1 から 3 を選んだときに入力された改行を この scanf で読み込んでしまい，文字型変数 item に改行文字が読み込まれてしまう． これは scanf で char 型を読み込むときは空白，改行などの文字を読み飛ばされない からである．scanf には書式制御文字列に読み飛ばしたい文字列を書いておけば 読み飛ばすという機能があるのでこれを利用して前回の入力の残りであり不要な \n を読み飛ばしている．

12.7 ツリー

連結リストでは「次の要素」は 1 つであるため，一直線の構造になるが， 木は「左の子」，「右の子」という 2 つの「次の要素」をもつ． 教科書図 12.11 がそれを図示したものである．このように枝分かれの数が たかだか 2 である木を二分木とよぶ．木の用語で重要なものを以下に挙げる．

親

自分を直接の子としてもつノード．

根

先頭のノード．どのノードの子でもない．

葉

子をもたないノード

動的メモリ配置を用いて木を構成するには，木のノードに対応する要素一つのための データ型として，以下のフィールドをもつ構造体を用いる．

• 左の子へのポインタ
• そのノードに格納されている値
• 右の子へのポインタ

リスト12.7 では以下のように実装されている．

struct treeNode { /* 自己参照構造体 */
   struct treeNode *leftPtr;
   int data;
   struct treeNode *rightPtr;
};

リスト 12.7 では二分探索木という特殊な性質をもった木を扱う 二分探索木は計算機の分野で非常によく使われており，重要である． 二分探索木を理解するために部分木の概念を定義する．

ノード x の左部分木

x の左の子を新たな根とし，その下に接続されたすべてのノードと一緒に 切り出されたもの

ノード x の右部分木

x の右の子を新たな根とし，その下に接続されたすべてのノードと一緒に 切り出されたもの

図 12-15 は部分木の定義を理解するための図である．例えば 47 が書かれているノードの右部分木は B であり， 25 と書かれているノードの左部分木は C である．

二分探索木は以下の二分探索条件を満たす木のことをいう．

二分探索条件

木の全てのノード x について，左部分木のすべてのノードの値 は x より小さく，右部分木のすべてのノードの値は x より大きい．

図 12-5 が二分探索木であることを確かめよ．

リスト 12.7 はコーディングの難易度からリスト12.8 に対して以下の順で説明する．

1. 二分探索木の定義から，どんな木が生成されるか
2. 出力関数 inOrder, preOrder, postOrder のコーディングの理解
3. insertNode のコーディングの理解

13, 11, 14, 8, 10, 3, 4, 5 の順に要素が入力されたときの木の 成長過程は以下の通りである．ノードを 1 つづつ二分探索木の条件を確認しながら 挿入していることを確認せよ．

出力関数 inOrder を例に，コーディングを説明する．inOrder は再帰関数である．

再帰型関数を理解する上で重要な点は以下の 3 点である．

1. 小さい規模の入力に対しては再帰せずに直接解く
2. 自分が受けた入力よりも小さい入力に対して再帰的に関数を呼び出す
3. 書いている最中の関数がすでに完成してあると思って書く

まず 1. は，引数である treePtr が NULL のときで， このときは「何も実行しない」として直接解いている．

2. については二カ所の inOrdern を再帰的に呼び出しているところに 注目すればよい．いずれも自分の子を根とする部分木を入力として呼び出している． これは自分を根とする部分木より小さい入力である．

3. については関数の外部仕様を意識することが重要である． inOrder は「与えられたノードを根とする部分木中順操作で出力する」 ことが定義である．図 12-23．の木に対して inOrder("13のノードへのポインタ") が実行されると以下の指示がなされたことになる．

以下は再帰的に解かれてゆく過程を示す．

リスト 12.7 は乱数で発生させた要素を 二分探索木へ挿入してゆき，色々な順序で節点のデータを出力するものである． 実行し，テストせよ．特に乱数で発生された値から， 頭の中でどんな木が生成されたかを考え， preOrder, inOrder, postOrder の出力を予想せよ． そしてその予想が正しいかどうか実際の出力と比較して確認せよ．

リスト 12.7 では二分探索条件を保ったまま木への挿入を行う insertNode を実装している．

図 12-15 へ 80 という値を挿入する場合を考える．以下の手順で正しい 位置へ挿入できる．

1. まず根(47)との大小関係を比較する．80 が 47よりも大きいことから 80 は(47)の右部分木に置かなければならないことがわかる．
2. (47)の右部分木の根である(77)と比較する．80 が 77 よりも大きいことから 80 は(77) のの右部分木に置かなければならないことがわかる．
3. (77)の右部分木の根である(93)と比較する．80 が 93 よりも小さいいことから 80 は(93) のの左部分木に置かなければならないことがわかる．
4. (93)の左部分木は存在しない．ここに新たに節点を作り，80 を記録して (93)の左部分木へのポインタがそこを指すようにする．

ここで注目すべきなのは

• 1. から　4. 全体で 「80 を (47)を根とする部分木に挿入する」処理になっている
• 2 から 4 では「80 を (77)を根とする部分木に挿入する」処理になっている
• 3 から 4 は「80 を (93)を根とする部分木に挿入する」処理になっている
• そして 4 は「80 を NULL が指す部分木，つまり何も無いころに挿入する」 処理になっている

ことである．これにより，「値をあるノードを根とする部分木に挿入する」 という形の再帰型関数で書くことができる．上の例では メインルーチンが「80 を (47)を根とする部分木に挿入せよ」とinsertNode 関数を呼び出し，その関数が 「80 を (77)を根とする部分木に挿入せよ」と再帰的に二重に insertNode関数を呼び出す．呼び出された関数が今度は 「80 を (93)を根とする部分木に挿入せよ」と再帰的に三重に呼び出すのである． 次に「80 を NULL を根とする部分木に挿入せよ」と再帰的に四重に呼び出され， 再帰は終了する．最後に呼び出された関数の実行が終了すれば順次外側の関数の実行が 終了する．

リスト 12.7 insertNode で再帰のポイントをチェックする.

上の 1. は insertNode の最初の if が成立したときの処理である． 部分木の根を示すポインタとして値が Null である変数が渡されると， まだ要素がない木に挿入することになり，if 成立時のブロックの処理 で正しく処理される．この関数も呼び出したほうの変数（子へのポインタ変数） の値を呼び出されたほうが変更するため，TREENODE 型要素へのポインタへの ポインタを引数としていることに注意せよ．

2. については二カ所の insertNode を再帰的に呼び出しているところに 注目すればよい．いずれも自分の子を根とする部分木を入力として呼び出している． これは自分を根とする部分木より小さい入力である．

1.2. が確認できれば 3. に従い「inserNode は完成している」と思って プログラムを読めばよい．