csort

/*sort routine:explain:create binary tree,simple linked list,recursive,traverse binary tree*/
#include <stdio.h>
#define MAXLINE 132
#define RECORD_SIZE sizeof(struct rec)

struct rec
{
       char *string;
       struct rec *left, *right;
};
/*
**csort: a utility that sorts named file
**and sends results to standard output.
**Syntax: csort filename
*/
main(argc,argv)
int argc;
char *argv[];
{
     FILE *file;
     char line[MAXLINE];       /*input line*/
     struct rec *add();
     struct rec *root=NULL;
     void print_tree();
    
     if(file=fopen(argv[1],"r"))  /*open input file*/
     {
         while(fgets(line,MAXLINE,file))  /*line byb line*/
             root=add(root,line);       /*addm,lines to tree*/
         print_tree(root);             /*print sorted lines*/
     }
     else
         printf("csort:can't open %s\n",argv[1]);
}

/*
**Add a record containing the indicated text to the binary tree
**pointed to by the argument named root.
**If this is the first rocord(i.e.,if root is NULL),
**return address of new record for use as root.
**Otherwise return root's current value.
*/
struct rec *add(ptr,line)
struct rec *ptr;
char *line;
{
     struct rec *install();
    
     if(ptr)                       /*we're not yet at an empty node*/
         if((strcmp(line,ptr->string))<=0)
             ptr->left=add(ptr->left,line);           /*go left*/
         else
             ptr->right=add(ptr->right,line);         /*go right*/
     else
         ptr=install(line);                /*we're at an empty node*/
     return(ptr);                        /*return for use in main()*/
}

/*
**Create a new record.Store a line of text in memory and
**insert a pointer to it in the new record.
**Return the addr of the new record.
**If no more space available,halt.
*/
struct rec *install(line)
char *line;
{
    // char *malloc();
     struct rec *ptr;
    
     if((ptr=(struct rec*)malloc(RECORD_SIZE))&&
         (ptr->string=malloc(strlen(line)+1)))
         /*ptr is the address of a new record;
           ptr->string points to reserved memory
           large enough to hold the input line.
         */
         {
             strcpy(ptr->string,line);  /*copy line into memory*/
             ptr->left=ptr->right=NULL; /*initialize l. and r.ptrs*/
             return(ptr);
         }
     /*malloc() returned NULL;out of memory*/
     printf("csort: out of memory\n");
     exit(0);
}

/*
**Walking the binary tree.
**When we traverse the tree,
**printing each node's text as we visit it,
**we're listing the lines of text in alphabetical order.
*/
void print_tree(ptr)
struct rec *ptr;
{
       if(ptr)           /*we're not yet at an empty node*/
       {
           print_tree(ptr->left);  /*traverse the left subtree*/
           printf("%s",ptr->string); /*print current node*/
           print_tree(ptr->right);      /*traverse the right subtree*/
       }
}