2分木(2分探索木)
struct Tree { int data ; struct Tree* left ; struct Tree* right ; } ; struct Tree* tcons( int x, struct Tree*L, struct Tree*R ) { struct Tree* ans ; ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ; if ( ans != NULL ) { ans->data = x ; ans->left = L ; ans->right = R ; } return ans ; } void main() { struct Tree* top = tcons( 52 , tcons( 24 , tcons( 10 , NULL , NULL ) , tcons( 35 , NULL , NULL ) ) , tcons( 73 , tcons( 60 , NULL , NULL ) , tcons( 95 , NULL , NULL ) ) ) ; }
出来上がった木構造のイメージ
top \ 52 / \ / \ 24 73 / \ / \ 10 35 60 95
データに対する処理
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 ; // 見つからなかった } void print( struct Tree* p ) { // 全データの出力 if ( p != NULL ) { print( p->left ) ; printf( "%d¥n" , p->data ) ; print( p->right ) ; } } int count( struct Tree* p ) { // 全データの件数をカウント if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } int depth( struct Tree* p ) { // データの深さをカウント if ( p == NULL ) { return 0 ; } else { int dl = depth( p->left ) ; int dr = depth( p->right ) ; if ( dl > dr ) return 1 + dl ; else return 1 + dr ; } }