#include <locale.h> 
#include <stdio.h> 
#include <string.h>

/*
  Compile and execute program. Enter in strings with a carriage return after
  each. When done, <Cntrl-D> and the list will be sorted
*/

struct tnode { 					/* node of binary tree */
char *line; 
int count; 
struct tnode *left, *right; };

main() 			 /* collate : sort a list of lines using strcoll() */ 
{
	struct tnode *root, *tree();
	char line[BUFSIZ];
	root = NULL;
	setlocale (LC_ALL, "");
	printf("Please enter strings to be sorted. \n");
	while (fgets(line,BUFSIZ,stdin))
		root = tree(root,line);
	printf("--------Sorted List---------\n");
	treeprint(root); 
}


struct tnode* tree( p, line) /* install line at or beloxemacsw tree pointer */ 
struct tnode *p; 
char *line; 
{
	char *cp, *malloc(), *strcpy();   
	int cond;
	if (p==NULL) {
		p = (struct tnode *) malloc (sizeof(struct tnode));
		if ((cp = malloc( strlen(line) +1 )) != NULL)
			strcpy (cp, line);
		p->line = cp; 
		p->count = 1; 
		p->left = p->right = NULL;
	} 
	else if ((cond = strcoll (line, p->line )) == 0)     
		p->count++;
	else if (cond < 0) 
		p->left = tree (p->left, line);    
	else  /* cond > 0 */
		p->right = tree(p->right, line);
	return (p);
}
treeprint(p) /* print the tree recursively starting at p */
struct tnode *p;
{
	if (p != NULL) {
		treeprint (p->left);
		while (p->count--)
			printf("%s", p->line);
	treeprint( p->right);
	}
}
