Example Binary Tree.

btree.c

//simple btree done as an exmaple
//not all null pointers checked, incomplete EXAMPLE

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define myassert(x, y) printf(y); assert(x);

//btree consists of a search, insert and delete. 
//btree consists of nodes, left = small, right = big, value = data

char *a = "This will be the value for keys smaller than 5";
char *b = "This will be the value for keys larger than 5";

struct node
{
	struct node *left;
	struct node *right;
	int key;
	char *value;
};

//this is our insert function, we recursively call insert depending on 
//value of key
struct node * insert(struct node **node, int key, char *value)
{
	printf("Attempting to insert node @%p, key=%d, value=%s\r\n",
		*node, key, value);
	if(!*node)
	{
		printf("Node @%p does not exist, creating node.\r\n",
			*node);
		//we must create a node if no node exists
		*node = malloc(sizeof(**node));
		//if memory fails to allocate, we assert() and exit
		if(!node) myassert(node, "Out of memory!");
		
		printf("Created node @%p, assigning key=%d, value=%s\r\n",
			*node, key, value);
		
		//assign our key, value pair
		(*node)->key   = key;
		(*node)->value = value;
		
		printf("Assigned key=%d, value=%s to node @%p\r\n",
			key, value, *node);
			
		printf("Returning node @%p from insert()\r\n",
			*node);
		
		return *node;
	}
	
	printf("Node exists @%p, recursively inserting key=%d, value=%s\r\n",
		*node, key, value);
	
	if((*node)->key > key)
	{
		printf("Node @%p key=%d is greater than insert key=%d\r\n",
			*node, (*node)->key, key);
		insert(&(*node)->left, key, value);
	}
	else
	{
		printf("Node @%p key=%d is less than insert key=%d\r\n",
			*node, (*node)->key, key);
		insert(&(*node)->right, key, value);
	}	
}


char * search(struct node *node, int key)
{

	printf("Attempting to locate key=%d, searching through node @%p\r\n",
		key, node);
		
	if(!node) myassert(node, "Invalid node passed to search()");
	
	if(node->key == key) 
	{
		printf("Found key=%d at node @%p, %d=%d\r\n",
			key, node, node->key, key);
		return node->value;
	}
	
	if(node->key > key)
	{
		printf("Node @%p key=%d is greater than search key=%d\r\n",
			node, node->key, key);
		search(node->left, key);
	}
	else
	{
		printf("Node @%p key=%d is less than search key=%d\r\n",
			node, node->key, key);
		search(node->right, key);
	}
}

void delete(struct node *node, int key)
{
	printf("Attempting to remove key=%d at node @%p\r\n",
		key, node);
		
	if(!node) myassert(node, "Invalid node passed to delete()");
	
	if(node->key == key) {
	//temporary fix here, but more problems will arise if you think
	// about the underlying logic.. 
	//delete a node in the middle, what happens to the edges?
		printf("Found key=%d at node @%p, %d=%d\r\n",
			key, node, node->key, key);
		free(node);
		return;
	}
	
	if(node->key > key)
	{
		printf("Node @%p key=%d is greater than delete key=%d\r\n",
			node, node->key, key);
		delete(node->left, key);
	}
	else
	{
		printf("Node @%p key=%d is less than delete key=%d\r\n",
			node, node->key, key);
		delete(node->right, key);
	}
}

int main(void)
{
	//preliminary testing.. checking for seg faults
	struct node *node;
	node = insert(&node, 5, a);
	insert(&node, 9, "My key is 9");
	search(node, 5);
	delete(node, 5);
	return 0;
}