ホーム » スタッフ » 斉藤徹 » 2分木

2006年10月
« 9月   11月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木

先週のヒープによる2分木のイメージを、本当の2分木にて説明する。 最初に、データ構造のイメージ図を交えて、検索処理速度が O(log N) である要点を説明する。 次に、データ構造の宣言を見せ、直接木構造を作るコンストラクタ関数を使いながら、 検索処理のコードを示す。

struct Tree {
int data ;
struct Tree* left ;
struct Tree* right ;
} ;
struct Tree* tree( 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 ;
}
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 ;
}
}
void main() {
struct Tree* top = tree( 56 ,
tree( 35 ,
tree( 23 , NULL , NULL ) ,
tree( 44 , NULL , NULL ) ) ,
tree( 77 , NULL , NULL ) ) ;
if ( find( top , 44 ) )
printf( "Find!!\n" ) ;
}

最後に、挿入位置を探して枝を追加するデータ追加処理のコードを見せる。 挿入されるデータ順序が昇順だったりした場合に、 一方向に伸びる木が発生する可能性を説明する。