Advanced Programming Course - Exercise 5

http://www.oocities.org/SiliconValley/Peaks/8778/TAU_advprog.html

To write an implementation of binary tree of strings that are stored by a string length. So the tree may contain more than 1 element with the same length. Use for the program the following struct (assuming that the strings will be not more than 256 characters):

typedef struct string_tree_node
{
	int len;
	char string[256];
	struct string_tree_node* ge;	/* greater or equal lengths */
	struct string_tree_node* lt;	/* less lengths */
} STNODE;

You have to write the functions:

STNODE* st_insert( STNODE* tree, char* str);
	/* inserts to the tree new element based on string "str" */
	/* (Use strlen() to get the string length and strcpy() to */
	/* store the string itself.) */
int st_lookup_len( STNODE* tree, int length);
	/* returns 1 if there is an element with length "length", */
	/* 0 - otherwise */
int st_lookup_string( STNODE* tree, char* str);
	/* returns 1 if there is an element with string "str", */
	/* 0 - otherwise. (Use strcmp() for strings comparison) */
STNODE* st_remove_len( STNODE* tree, int len);
	/* removes from the tree ALL elements with length "len". */
	/* (So after a deletion of an node you must continue to its */
	/* "ge" subtree to delete also all other nodes with the same */
	/* length.) */
STNODE* st_remove_string( STNODE*, char* str);
	/* removes from the tree ALL nodes with string "str". */
	/* (Due to the same string have the same length, so after a */
	/* deletion you have to go to "eq" subtree to find and delete */
	/* all other such nodes.) */

To print the tree use function:

void st_print( STNODE* tree)
{
	if( tree == NULL)
		return;
	st_print( tree->lt);
	printf( "[%d] - [%s]\n", tree->len, tree->string);
	st_print( tree->ge);
}

The main() function may look so:

int main()
{
	static char* strings[] =
	{
		"etc. etc. etc.",
		"bbbb",
		"ccc",
		"I love long strings",
		"I hate short strings",
		"aaa",
		"whatever you want",
		"123456789012345678901234567",
		"string with the same length",
		"etc. etc. etc.",
		/* ... add your own strings ... */
		NULL;
	};
	STNODE* tree = NULL;
	int i, n;

	for( i = 0; strings[i] != NULL; i ++)
		tree = st_insert( tree, strings[i]);
	st_print( tree);
	printf( "[%d]\n", st_lookup_len( tree, 3));
	printf( "[%d]\n", st_lookup_len( tree, 4));
	printf( "[%d]\n", st_lookup_len( tree, 5));
	printf( "[%d]\n", st_lookup_string( tree, strings[5]);
	printf( "[%d]\n", st_lookup_string( tree, "no such");

	tree = st_remove_len( tree, 3);
	st_print( tree);
	tree = st_remove_len( tree, strlen( 0));
	st_print( tree);
	tree = st_remove_string( tree, strings[7]);
	st_print( tree);
}