2分木の生成

先週に2分木に対する再帰などを交えたプログラムの説明をしたので、 今週は木の生成について、AVL木などを交えて説明。 後半は、情報処理センターで演習。

#include <stdio.h>
#include <stdlib.h>
// 2分木の宣言
struct Tree {
   int data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
// 木の根
struct Tree* top = NULL ;
// 木のノードを構築する補助関数
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 ;
}
// 木を表示する補助関数。枝の左右がわかる様に...
void print( struct Tree* p ) {
   if ( p == NULL ) {
      printf( "x" ) ;
   } else {
      printf( "(" ) ;
      print( p->left ) ;
      printf( " %d " , p->data ) ;
      print( p->right ) ;
   printf( ")" ) ;
   }
}
// 木に1件のデータを追加する補助関数
void entry( int x ) {
   struct Tree** ppt = &top ;

   while( (*ppt) != NULL ) {
      if ( (*ppt)->data == x )
         break ;
      else if ( (*ppt)->data > x )
         ppt = &( (*ppt)->left ) ;
      else
         ppt = &( (*ppt)->right ) ;
   }
   if ( *ppt == NULL )
      (*ppt) = tcons( x , NULL , NULL ) ;
   }
int main() {
   entry( 51 ) ;
   entry( 26 ) ;
   entry( 76 ) ;
   entry( 60 ) ;
   print( top ) ;
   // ((x 26 x) 51 ((x 60 x) 76 x))

   top = NULL ;
   entry( 26 ) ;
   entry( 51 ) ;
   entry( 60 ) ;
   entry( 76 ) ;
   print( top ) ;
   // (x 26 (x 51 (x 60 (x 76 x))))
}