[ create a new paste ] login | about

Link: http://codepad.org/jnMTN32g    [ raw code | fork ]

C, pasted on Apr 27:
#include <string.h>
#include <stdlib.h>

static struct tsnode* BinarySearchTreeString_addtreeImp(struct tsnode *p, const char *w)
{
	if(p == NULL)
	{
		struct tsnode *newNode;
		if((newNode = (struct tsnode*)malloc(sizeof(struct tsnode))) == NULL)
			return NULL;

		newNode->word = strdup(w);
		newNode->left = NULL;
		newNode->right = NULL;
		return newNode;
	}
	else if(strcmp(w, p->word) < 0)
		p->left = BinarySearchTreeString_addtree(p->left, w);
	else
		p->right = BinarySearchTreeString_addtree(p->right, w);

	return p;
}

struct tsnode* BinarySearchTreeString_addtree(struct tsnode *p, const char *w)
{
	struct tsnode *ptr;
	if((ptr = BinarySearchTreeString_lookup(p, w)) == NULL)
		return BinarySearchTreeString_addtreeImp(p, w);

	return ptr;
}

struct tsnode* BinarySearchTreeString_deletetree(struct tsnode *p, const char *w)
{
	int cond;
	struct tsnode *currentp, *prevp;

	currentp = prevp = p;

	/* find the node to be deleted. prevp points to the parent of the node to be deleted
		and currentp points to the node to be deleted */
	while(1)
	{
		if(currentp == NULL)			/* cannot find the node to be deleted */
			return p;

		if((cond = strcmp(w, currentp->word)) == 0)		/* node found, break out of the loop */
		{
			break;
		}
		else if(cond < 0)
		{
			prevp = currentp;
			currentp = currentp->left;
		}
		else
		{
			prevp = currentp;
			currentp = currentp->right;
		}
	}

	/* the right node is NULL */
	if(currentp->right == NULL)
	{
		/* root node */
		if(currentp == p)
		{
			p = currentp->left;
		}
		else if(prevp->right == currentp)
		{
			prevp->right = currentp->left;
		}
		else
		{
			prevp->left = currentp->left;
		}
	}
	else if(currentp->left == NULL)
	{
		/* root node */
		if(currentp == p)
		{
			p = currentp->right;
		}
		else if(prevp->right == currentp)
		{
			prevp->right = currentp->right;
		}
		else
		{
			prevp->left = currentp->right;
		}
	}
	else
	{
		struct tsnode *ptr;
		ptr = currentp->right;

		if(ptr->left == NULL)
		{
			ptr->left = currentp->left;
			/* root node */
			if(currentp == p)
			{
				p = ptr;
			}
			else if(prevp->right == currentp)
			{
				prevp->right = ptr;
			}
			else
			{
				prevp->left = ptr;
			}
		}
		else
		{
			struct tsnode *prevptr;

			for(prevptr = ptr;
				ptr->left;
				prevptr = ptr, ptr = ptr->left);

			prevptr->left = ptr->right;
			
			ptr->right = currentp->right;
			ptr->left = currentp->left;

			/* root node */
			if(currentp == p)
			{
				p = ptr;
			}
			else if(prevp->right == currentp)
			{
				prevp->right = ptr;
			}
			else
			{
				prevp->left = ptr;
			}
		}
	}
	free(currentp->word);
	free(currentp);

	return p;
}

struct tsnode* BinarySearchTreeString_lookup(struct tsnode *p, const char *w)
{
	int cond;

LOOP:
	if(p == NULL)
		return NULL;

	if((cond = strcmp(w, p->word)) == 0)
		return p;
	else if(cond < 0)
		p = p->left;
	else
		p = p->right;

	goto LOOP;
}

void BinarySearchTreeString_free(struct tsnode *p)
{
	if(p == NULL)
		return;

	BinarySearchTreeString_free(p->left);
	BinarySearchTreeString_free(p->right);
	free(p->word);
	free(p);
}


Create a new paste based on this one


Comments: