後期に入ったということで、中間試験までと期末試験までの予定を 簡単に説明した後で、2分木の説明を行う。
2分木
比較として、最初に配列での高速なデータ検索として、 2分探索法について説明し、データ検索が O(log(N))で表せること、 データの追加の処理などは、配列で実装すれば、O(N)となり、 あまり高速ではないことを説明する。
一方、リスト構造は、シーケンシャルアクセスしかできないから、 中央値を取り出すのには、O(N)の時間を要するため、 2分探索法が出来ないことを説明する。
そこで、2分木のデータ例を図示し、目的のデータを探すのに 要する比較回数を検討してもらう。これにより、 2分木のピラミッド構造の段数が、データ検索の際のループ回数である ことを説明し、段数 m と、データ件数 2m = N より、 O(log(N))などの説明を行う。
structd Tree {
int data ;
struct Tree *left ;
struct Tree *right ;
} ;
struct Tree* tcons( int x , struct Tree*l , struct Tree*r )
{
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->data = x ;
n->left = l ;
n->right = r ;
}
return n ;
}
struct Tree* top = // 静的にデータを生成
tcons( 50 ,
tcons( 75 , NULL , NULL ) ,
tcons( 25 , NULL , NULL ) ) ;
例題
2分木データ挿入処理のプログラムは複雑になりそうだし、 いきなりポインタのポインタでは、混乱をすると思われるので、 簡単に検索、データ件数カウントなどの例題を示す。
int find( struct Tree* p , int key )
{
while( p != NULL ) {
if ( p->data == key )
return 1 ;
else if ( p->data > key )
p = p->left ;
else
p = p->right ;
}
return 0 ; // 見つからない
}
int count( struct Tree* p )
{ if ( p == NULL )
return 0 ;
else
return 1 + count( p->left ) + count( p->right ) ;
}