#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);
}