2分探索木

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 ;
    }
}