2分木データの処理

先週は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()はループでも記述可能で、この違いは末尾再帰呼び出しになっているかの 違いであることを紹介する。