binarytree.c

Binary Search Tree - with additional recursion functions (smallest, parent & successor) etc

// BinaryTree.c
// file is the implementation of a binary search tree.
#include <stdlib.h> // for malloc
#include "BinaryTree.h"

// Defines 
#define TRUE 1
#define FALSE 0

typedef struct Node
{
   Item item;

   Key key;
   struct Node *left;
   // if left == NULL , it means it has no left son
   struct Node *right;
   // if right == NULL , it means it has no right son
} *ptrNode;

struct tree
{
   ptrNode root;
};

int succ;
//helper functions
static BOOL delNode(Tree tree, Key key);
static ptrNode find_parent(ptrNode root, Key key);
static ptrNode find_succ(ptrNode root);
static ptrNode find_small(ptrNode root);
static void DestoryTree(Tree tree);
// ---------------------------------------------------------
static ptrNode search(ptrNode subtree, Key key);
static void traversePre(ptrNode subtree, PerItemFunc pFunc);
static void traverseIn(ptrNode subtree,  PerItemFunc pFunc);
static void traversePost(ptrNode subtree,PerItemFunc pFunc);

void deleteTree(Tree tree)
{
   DestoryTree(tree);
}

int deleteNode(Tree tree, Key key)
{
   succ=delNode(tree,key);
   return succ;
}

Tree CreateTree()
{
   return calloc(1,sizeof(struct tree));
}

Item *Find(Tree tree, Key key)
// searches a node, given its key, in the tree and
// returns the appropriate Item address.
// returns NULL if it's not found
{
   ptrNode pNode = search(tree->root,key);

   if (!pNode)
      return NULL;
   return &(pNode->item);
}

static ptrNode search(ptrNode root, Key key)
{
   if (root)
	 {
      if (!EQ(key,root->key))
         return root;												// we've found it
      if (EQ(key,root->key) < ZERO)
         return search(root->left, key);
      else if (EQ(key,root->key) > ZERO)
         return search(root->right, key);
   }
   return NULL;													// the sub-tree was empty
}

void traversePreOrder(Tree tree, PerItemFunc pFunc)
{
   traversePre(tree->root, pFunc);
}

void traverseInOrder(Tree tree, PerItemFunc pFunc)
{
   traverseIn(tree->root, pFunc);
}

void traversePostOrder(Tree tree, PerItemFunc pFunc)
{
   traversePost(tree->root, pFunc);
}
static void traversePre(ptrNode root,
                        PerItemFunc pFunc)
{
   if (root) // if ptr is not NULL (i.e., there is a node)
   {
      pFunc(&root->item);
      traversePre(root->left, pFunc);
      traversePre(root->right, pFunc);
   }
}
static void traverseIn(ptrNode root,
                       PerItemFunc pFunc)
{
   if (root) // if ptr is not NULL (i.e., there is a node)
   {
      traverseIn(root->left, pFunc);
      pFunc(&root->item);
      traverseIn(root->right, pFunc);
   }
}
static void traversePost(ptrNode root,
                         PerItemFunc pFunc)
{
   if (root) // if ptr is not NULL (i.e., there is a node)
   {
      traversePost(root->left, pFunc);
      traversePost(root->right, pFunc);
      pFunc(&root->item);
   }
}

void add(Tree tree, Key key, Item item)
{
   ptrNode subtree;
   //crate new node
   ptrNode newNode = malloc(sizeof(struct Node));
   if (!newNode)
   {
      ERROR();
      return;
   }
		//fill it with data
   newNode->key = key;
   newNode->item = item;
   newNode->left = newNode->right = NULL;

   subtree = tree->root; //start from beginning
   if (!tree->root) // Is it an empty tree?
   {
      tree->root = newNode;
      return;
   }
		while (1)
   {
      if (EQ(key, subtree->key) < ZERO) // add to left sub-tree
      {
        if ( subtree->left == NULL )
        {
            subtree->left = newNode;
            return;
        }
         subtree = subtree->left;
      }
     else //add to right sub-tree
      {
        if ( subtree->right == NULL )
        {
            subtree->right = newNode;
            return;
        }
        subtree = subtree->right;
      }
   }
}

//===========================================================================
// is a child of the recursion function find_succ() to find the
// succsessor.
//===========================================================================
static ptrNode find_small(ptrNode root)
{
	if(root)
	{
		if(root->left == NULL)
		{
			return root;
		}
		else
		{
			return find_small(root->left);
		}
	}
	return NULL;
}
//===========================================================================
// find succ of Item that we want delete
//===========================================================================
static ptrNode find_succ(ptrNode root)
{
	return (root->right ? find_small(root->right) : NULL);
}
//===========================================================================
// this function find in a recursion way the father
// of the actually Item
//===========================================================================
static ptrNode find_parent(ptrNode root, Key key)
{
	if(root)
	{
		if( (root->left != NULL && EQ(root->left->key, key) == ZERO ) ||
				(root->right != NULL && EQ(root->right->key, key) == ZERO))
		{
			return root;
		}
		if(EQ(root->key, key) > ZERO)
		{
			return find_parent(root->left, key);
		}
		else if (EQ(root->key, key) < ZERO)
		{
			return find_parent(root->right, key);
		}
	}
	return NULL;
}

//===========================================================================
// is the main function to set all variables for the delete procedure.
//===========================================================================
static BOOL delNode(Tree tree, Key key)
{
	ptrNode root = tree->root;

	ptrNode pDel = NULL;
	ptrNode father = NULL;
	ptrNode succ = NULL;
	ptrNode fsucc = NULL;

	ptrNode tmp = NULL;

	if (!tree->root)
	{
		return FALSE;
	}
	// find the spec. Item
	pDel = search(root, key);
	if (pDel == NULL)
	{
		return FALSE;
	}
	father = find_parent(root, key);

	// if all our Nodes smaller then root
	if ( root->right == NULL )
	{
		tree->root = pDel->left;
		free(pDel);
		return TRUE;
	} // ups they are all greater!
	else if ( root->left  == NULL )
	{
		tree->root = pDel->right;
		free(pDel);
		return TRUE;
	}

	if (pDel->left == NULL && pDel->right == NULL)
	{
		if (EQ(key,father->key) == ZERO_GREATER) //if the son is on the right of the father
		{
			father->right = NULL;
		}
		else //if it's on the left
		{
			father->left = NULL;
		}
	}
	else if (pDel->left != NULL && pDel->right == NULL)
	{
		if (EQ(key,father->key) == ZERO_GREATER) //if the son is on the right of the father
		{
			father->right = pDel->left;
		}
		else //if it's on the left
		{
			father->left = pDel->left;
		}
	}
	else //if pDel has two sons, or son on the right only
	{
		succ = find_succ(pDel);
		fsucc = find_parent(root, succ->key);

		if (EQ(root->key,key) == ZERO) //  the node to delete is the root of the tree
		{
			father = pDel;
			succ = find_succ(pDel);
			fsucc = find_parent(pDel,succ->key);

			if (succ == pDel->right)
			{
				succ->right = succ->right;
			}
			else
			{
				succ->right = pDel->right;
				fsucc->left = NULL;
			}

			succ->left  = pDel->left;

			tree->root = succ;
			free(pDel);
			return TRUE;
		}
		else if (EQ(key,father->key) == 1)//if the son is on the right of the father
		{
			father->right = succ;
		}
		else //if it's on the left
		{
			father->left = succ;
		}

		tmp = pDel->left;

		if(EQ(fsucc->key,pDel->key) == ZERO)
		{

			fsucc->left = NULL;
			fsucc->right = NULL;
		}
		else
		{
			fsucc->left = succ->right;
		}

		//if the succesor is not the son of pDel
		succ->left = tmp;
		succ->right = pDel->right;

	}
	tmp = NULL;
	free(pDel);
	return TRUE;
}


static void DestoryTree(Tree tree)
{
	while (find_small(tree->root))
	{
		delNode(tree,find_small(tree->root)->key);
	}
	free(tree);
}