#include <stdio.h>
#include <sys/file.h>

typedef struct node { 
	int data;
	struct node  *left;
	struct node  *right;
} 
NODE ;

typedef NODE * BTREE;

char * build_tree_aux( BTREE b, char * s ) 
/* recursive function to search a nonexistent tree, depth first,
   building as we go, as long as the next char in some buffer is
   not '.'.  In this case, copy char, into built node. */
{
	/* recursion invariant: s points to next char to process,
	    return pointer to next unprocessed character */

	/* b is a non-empty tree,
	   s is a string, next char to process is at the front of s */

	if (*s!='.') {
		(*b).left = (BTREE) malloc(sizeof(NODE)) ;
		b->left->left = NULL ;
		b->left->right = NULL ;
		b->left->data = (int) *s ;
		s = build_tree_aux( b->left, (s+1) ) ;
	}
	else s++ ;
	if (*s!='.') {
		(*b).right = (BTREE) malloc(sizeof(NODE)) ;
		b->right->left = NULL ;
		b->right->right = NULL ;
		b->right->data = (int) *s ;
		s = build_tree_aux( b->right, (s+1) ) ;
	}
	else s++ ;
	return s ;
}

BTREE build_morse_tree( void )
{
	char * s ;
	BTREE root ;

	s = "@eish..v..uf...arl...wp..j..tndb..x..kc..y..mgz..q..o.." ;
	root = (BTREE) malloc(sizeof(NODE)) ;
	root->left = NULL ;
	root->right = NULL ;
	root->data = s[0] ;
	s = build_tree_aux( root, s+1 ) ;

	/* ASSERT: *s=='\0' */
	if (*s!='\0') printf("build_morse_tree: Oops!\n") ;

	return root ;

}

void  dump_tree_aux( int fd, BTREE b )
{
   int i ;
   if (b==NULL) i = write( fd, "!", 1 ) ;
   else {
      write( fd, " ", 1 ) ;
      write( fd, b, sizeof(NODE) ) ;
      dump_tree_aux( fd, b->left ) ;
      dump_tree_aux( fd, b->right ) ;
   }
}
 
void dump_tree( BTREE b ) 
{
   int fd ;
   fd = open("./treetmp",O_WRONLY|O_CREAT,0660) ;
   if (fd==-1) {
      perror("dump_tree") ;
      exit(1) ;
   }

   dump_tree_aux( fd, b ) ;
   close(fd) ;
}
void  print_tree_aux( BTREE b, int indent ) 
{
	int i ;
	for (i=0;i<indent;i++) printf(" ") ;
	if (b==NULL) printf("-\n") ;
	else {
		printf("%c\n",b->data) ;
		print_tree_aux(b->left, indent+5 ) ;
		print_tree_aux(b->right, indent+5 ) ;
	}
}

void print_tree( BTREE b ) 
{
	print_tree_aux( b, 0 ) ;
}

main (int argc, char *argv[])
{
	BTREE mo_tr ;

	printf("main: building morse tree\n") ;
	mo_tr = build_morse_tree() ;
	dump_tree(mo_tr) ;

}