今日は、昼から避難訓練があるので、授業が短縮授業であった。 しかし来週には保護者面談を実施するので、 自分の授業 の前に、進路希望調査の用紙を配る。 様式は、就職用と進学用で表は履歴書っぽい書式で、裏面は就職先・進学先・業種や、 それに伴う意欲を確認するようなものとした。 これを、保護者面談までor面談当日に提出してもらう予定。

しかしながら、まだ夢のような希望を言ってくる人もいそうなので、 「夢を語る時間はもう終わった」と明言する。

先週は2分木の概念の理解と検索処理の話をしたので、 今日は実際に木の全要素に対する処理などを再帰を交えて説明を行った。

2分木の前に、簡単な再帰に慣れてもらうために、 単純リストでのループを使った処理を再帰で記述する練習。 以下のようなcount()を示した後、単純リストの全データ表示と、全データ合計を書いてもらう。 この際に、再起でプログラムを書くコツとして、「処理できない問題は小さく分けて考える」 という定番の説明をおこなう。

// ひとまず再帰に慣れるために線形リストで...
int count( struct List* p )
{
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ;
}

この後、実際に2分木のデータ処理として、リストに対する全データ表示を記述してもらう。 あらかじめ単純リストの説明の後だったので、意外とすんなり理解してくれた様子。 この説明のあと、全データ件数count(struct Tree*)や、全データ合計sum( struct Tree* )や、 ループで記述可能であるけれどあえて、find( struct Tree* p , int key ) なども考えてもらう。

// 2分木で全データを昇順に表示
void print( struct Tree* p )
{
if ( p != NULL ) {
print( p->left ) ;
printf( "%d" , p->data ) ;
print( p->right ) ;
}
}

この話の関連として、print() は、深さ優先探索であり、記述は手間だけど別な探索では、 幅優先探索といった用語を紹介する。 また、2分木のcount(),sum(),print()などは、通常再帰でなければ記述できない処理であり、 find()はループでも記述可能で、この違いは末尾再帰呼び出しになっているかの 違いであることを紹介する。