bintree/bintree.c

// ------------------------------------------------------------
// bintree.c
// Implementation of a binary tree
//
// 27.02.2005, J.Ahrensfeld
// ------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bintree.h"

// ------------------------------------------------------------
node_t* GetParent(node_t *pObj)
{
	if (!pObj)
		return pObj;

	if (!pObj->pParent)
		return pObj;

	return GetParent(pObj->pParent);
}

node_t* node_init(node_t *pObj, double value, void *pData, int size)
{
	node_t *pNode;
	pNode = (node_t*)malloc(sizeof(node_t));

	pNode->pData = NULL;
	if (size)
		pNode->pData = malloc(size);
	if (pData)
		memcpy(pNode->pData, pData, size);
	pNode->pParent = pObj;
	pNode->pLeft = NULL;
	pNode->pRight = NULL;
	pNode->value = value;

	return pNode;
}

node_t* node_insert(node_t *pObj, double value, void *pData, int size)
{
	if(pObj == NULL)
	{
		return node_init(pObj, value, pData, size);
	}
	else
	{
		if(value <= pObj->value)
		{
			if (pObj->pLeft)
				node_insert(pObj->pLeft, value, pData, size);
			else
				pObj->pLeft = node_init(pObj, value, pData, size);

		}
		else
		{
			if (pObj->pRight)
				node_insert(pObj->pRight, value, pData, size);
			else
				pObj->pRight = node_init(pObj, value, pData, size);

		}
	}

	return pObj;
}

node_t*  node_lookup(node_t *pObj, double value)
{
	return pObj;
}

node_t* node_remove(node_t *pNode)
{
	node_t *pMin_leaf;
	node_t *pParent;
	void *pData;
	double value;

	if(pNode == NULL)
	{
		return pNode;
	}
	pParent = pNode->pParent;

	if(!pNode->pLeft && !pNode->pRight)
	{
		if (pParent)
		{
			if(pParent->pLeft == pNode)
			{
				pParent->pLeft = NULL;
			}

			if(pParent->pRight == pNode)
			{
				pParent->pRight = NULL;
			}

		}
	}
	else
	{
		if(pNode->pLeft && !pNode->pRight)
		{
			pNode->pLeft->pParent = pParent;
			if (pParent)
			{
				if(pParent->pLeft == pNode)
					pParent->pLeft = pNode->pLeft;

				if(pParent->pRight == pNode)
					pParent->pRight = pNode->pLeft;


			}
			else
				pParent = pNode->pLeft;

		}
		else
		{
			if(!pNode->pLeft && pNode->pRight)
			{
				pNode->pRight->pParent = pParent;
				if (pParent)
				{
					if(pParent->pLeft == pNode)
						pParent->pLeft = pNode->pRight;

					if(pParent->pRight == pNode)
						pParent->pRight = pNode->pRight;

				}
				else
					pParent = pNode->pRight;

			}
			else
			{
				if(pNode->pLeft && pNode->pRight)
				{
					pMin_leaf = bintree_GetLeafMin(pNode);
					value = pMin_leaf->value;
					pData = pMin_leaf->pData;
					pParent = node_remove(pMin_leaf);
					pNode->pData = pData;
					pNode->value = value;
				}
			}
		}
	}
	if (pNode->pData)
		free(pNode->pData);
	free(pNode);
	pNode = NULL;

	return GetParent(pParent);
}

// ------------------------------------------------------------
void bintree_print(node_t *pObj)
{
	if (pObj == NULL)
		return;

	bintree_print(pObj->pLeft);
	printf("%g ", pObj->value);
	bintree_print(pObj->pRight);

}

int bintree_size(node_t *pObj)
{
	if (pObj==NULL)
	{
		return 0;
	}
	else
	{
		return(bintree_size(pObj->pLeft) + 1 + bintree_size(pObj->pRight));
	}
}

int bintree_maxdepth(node_t *pObj)
{
	int lDepth;
	int rDepth;

	if (pObj==NULL)
	{
		return(0);
	}
	else
	{
		// compute the depth of each subtree
		lDepth = bintree_maxdepth(pObj->pLeft);
		rDepth = bintree_maxdepth(pObj->pRight);

		// use the larger one
		if (lDepth > rDepth)
			return(lDepth+1);
		else
			return(rDepth+1);
	}
}

double bintree_minvalue(node_t *pObj)
{
	node_t *current = pObj;

	// loop down to find the leftmost leaf
	while (current->pLeft != NULL)
	{
		current = current->pLeft;
	}

	return(current->value);
}

double bintree_maxvalue(node_t *pObj)
{
	node_t *current = pObj;

	// loop down to find the leftmost leaf
	while (current->pRight != NULL)
	{
		current = current->pRight;
	}

	return(current->value);
}

// ------------------------------------------------------------
node_t *bintree_GetNodeMax(node_t *pObj)
{

	node_t *pNode = pObj;
	node_t *current = pNode;

	if (!pNode)
		return pNode;

	// loop down to find the leftmost leaf
	while (current->pRight != NULL)
	{
		current = current->pRight;
	}

	return current;
}

// ------------------------------------------------------------
node_t *bintree_GetNodeMin(node_t *pObj)
{

	node_t *pNode = pObj;
	node_t *current = pNode;

	if (!pNode)
		return pNode;

	// loop down to find the leftmost leaf
	while (current->pLeft != NULL)
	{
		current = current->pLeft;
	}

	return current;
}

// ------------------------------------------------------------
node_t *bintree_GetLeafMax(node_t *pObj)
{

	node_t *current = pObj;

	if(current->pRight != NULL)
		current = bintree_GetLeafMax(current->pRight);
	else
		if(current->pLeft != NULL)
			current = bintree_GetLeafMax(current->pLeft);

	return current;
}

node_t *bintree_GetLeafMin(node_t *pObj)
{

	node_t *current = pObj;

	if(current->pLeft != NULL)
		current = bintree_GetLeafMin(current->pLeft);
	else
		if(current->pRight != NULL)
			current = bintree_GetLeafMin(current->pRight);

	return current;
}

int bintree_isBST(node_t *pObj)
{
	if (pObj==NULL)
		return(1);

	// false if the max of the left is > than us

	// (bug -- an earlier version had min/max backwards here)
	if (pObj->pLeft != NULL && bintree_maxvalue(pObj->pLeft) > pObj->value)
		return(0);

	// false if the min of the right is <= than us
	if (pObj->pRight !=NULL && bintree_minvalue(pObj->pRight) <= pObj->value)
		return(0);

	// false if, recursively, the left or right is not a BST
	if (!bintree_isBST(pObj->pLeft) || !bintree_isBST(pObj->pRight))
		return(0);

	// passing all that, it's a BST
	return(1);
}

int bintree_isBSTUtil(node_t *pObj, double min, double max)
{
	if (pObj==NULL)
		return(1);

	// false if this node violates the min/max constraint
	if (pObj->value<min || pObj->value>max)
		return(0);

	// otherwise check the subtrees recursively,
	// tightening the min or max constraint
	return
	(
		bintree_isBSTUtil(pObj->pLeft, min, pObj->value) &&
		bintree_isBSTUtil(pObj->pRight, pObj->value+1, max)
	);
}

int bintree_destroy(node_t *pObj)
{
	int size;
	node_t *pRoot, *pMaxLeaf;
	pRoot = pObj;

	size = 1;
	while(pRoot)
	{
		size = bintree_size(pRoot);
		pMaxLeaf = bintree_GetLeafMax(pRoot);
		pRoot = node_remove(pMaxLeaf);

	};

	if (size != 1)
		return -1;

	return 0;

}

// ------------------------------------------------------------