// 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 0typedef 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 functionsstatic 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);}