Thread: Deleting from Binary search trees

Hey there... can anyone suggest code for deleting a term from a tree.. I have a base code for searching the tree... we have to take into account whether or not the term to be deleted has children or not...

Any suggested code for that? just not sure how to do it code wise... thanks for replying!

Try This one:

Code:

tree dtree(tree root,int key)
{
	tree p,p2;
		if(!root) return root;

		if((root->e.id)==key) /* delete root */
		{
			if(root->lift == root->right)
			{
				free(root);
				return NULL;
			}
		/* or if one subtree is null */
			else if(root->lift ==NULL)
			{
				p=root->right;
				free(root);
				return p;
			}
			else if(root->right ==NULL)
			{
				p= root->lift;
				free(root);
				return p;
			}
		/* or if both subtree are ther */
			else
			{
				p2=root->right;
				p=root->right;
				while(p->lift) p=p->lift;
				p->lift = root->lift;
				free(root);
				return p2;
			}
		}

		if(root->e.id < key) root->right = dtree(root->right,key);
		else root->lift= dtree(root->lift,key);
		return root;
}

see you

how would you write it if you were using strings and files in the tree?
i.e. if the actual nodes of the tree contains a string of words
if you know what i mean.

here's a program i wrote but i need help correcting it

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 40



typedef struct treenode
        {
	char word[SIZE];
	int count;

	struct treenode *left;
	struct treenode *right;
        } treenode;  //structure

treenode* insert(treenode*, char*);
void inorder(treenode*);
void preorder(treenode*, FILE*);
void menu();
void check_choice(treenode* tree, char);
void freetree(treenode*);
int deletenode(treenode*, char);


//begin main function
int main()
   {
   char	str[30];
   FILE* fptr;
   int check =0;
   char ch;

   treenode* root =NULL;
	

   if ( (fptr = fopen("btree.txt","r")) == NULL)
       {
       fprintf(stderr, "Error in opening file test.txt");
       return(0);
       }
	
   while(fscanf(fptr, "%s", str) != EOF)
        root = insert(root, str);

   menu();
   scanf(" %c", &ch);

 
   while ((ch != 'e') && (ch != 'E'))
	{
	check_choice(root, ch);	
	menu();
        scanf(" %c", &ch);
        }



   fclose(fptr);

   if ( (fptr = fopen("btree.txt","w")) == NULL)
       {
       fprintf(stderr, "Error in opening file test.txt for writing");
       return(0);
       }
   preorder(root, fptr);

   return(1);
   }


treenode* insert(treenode* root, char word[30])
     {
     if(root == NULL)
	{
	root = (treenode *) malloc(sizeof(treenode));
	strcpy(root->word, word);		
	root->left = NULL;
	root->right = NULL;
	root->count = 1;
	}
	
	else
	   {
	   if((strcmp(word,root->word))==0)
		{
                root->count++;
		}
		else if((strcmp(word,root->word)) < 0)
		    {
		    root->left = insert(root->left, word);
		    }
		else if((strcmp(word,root->word)) > 0)
		    {
		    root->right = insert(root->right, word);
		    }
	    }
       return(root);
     }

void search(treenode *root, char *term)
	{
	int l;
    
	if (root == NULL)
		{
		printf("Term not found\n");	
		return;
		}
	else if ((l = strcmp (root->word, term)) == 0)
		{
		printf("Term found in tree\n");
		return;
		}
	else if	(l > 0)
		search(root->left, term);
	else 
		search(root->right, term);
	}

void inorder(treenode* root)
    {
	if(root != NULL)
	{
		inorder(root->left);
		printf("\n %s %d",root->word, root->count);
		inorder(root->right);
	}
    }

void  preorder(treenode *root, FILE *fptr)
	{
	if (root != NULL)
		{
		preorder(root->left, fptr);
		fprintf(fptr, "%s ",root->word);
		preorder(root->right, fptr);
		}
	}


void menu()
	{
	
	printf("\n\tExit program (e)\n");
	printf("\tDisplay tree (d)\n");
	printf("\tSearch tree for string (s)\n");
	printf("\tAdd new string to tree (a)\n");
	return;
	}

void check_choice(treenode *tree, char choice)
	{
	char term[WORD_SIZE];

	switch(choice)
		{
		case 'e' : printf("Exiting ...\n");
		      break;
		case 'd' : inorder(tree);
			   break;
                case 's' : printf("Please enter search term\n");
			   scanf ("%s", term);
			   search(tree, term);
			   break;
                case 'a' : printf("Please enter term to be added\n");
			   scanf ("%s", term);
			   tree = insert(tree, term);
			   break;
				case 'b' : printf("please enter a term to be deleted\n");
					scanf("%s" , term);
					del(tree, term);
			   break;
		}
	}


//begin function to delete a value from the tree


treenode* del(treenode* tree, char tofind)
{
	char term=0;
	treenode* parent=NULL, *deleted=NULL, *suc, *word;

	if (tree=NULL)
		printf("tree empty\n");
	term= search(tree, term);

	if(!term)
		printf("string %s is not in tree\n", term);

	else
	{
		if(root->leftptr==NULL && root->rightptr==NULL)
		{
			if(parent==NULL)
				tree=parent;
			else if(parent->leftptr==deleted)
				parent->leftptr=NULL;
			else
				parent->rightptr=NULL;
			free(deleted);
		}

		else if (deleted->leftptr==NULL && deleted->rightptr!=NULL)
		{
			if(parent==NULL)
				tree=deleted->rightptr;
			else if (parent->leftptr==deleted)
				parent->leftptr=deleted->rightptr;
			else
				parent->rightptr=deleted->leftptr;

			free(deleted);
		}

		else if(deleted->leftptr!=NULL && deleted-.rightptr==NULL)
		{
			if (parent==NULL)
				tree=deleted->leftptr;

			else if(parent->leftptr==deleted->leftptr)
				parent->leftptr=deleted->leftptr;
			else
				parent->rightptr=deleted->leftptr;
			free(deleted);

	}


		else
		{
			parent=deleted;
			suc=deleted->rightptr;
			while(suc->leftptr!=NULL)
			{
				parent=suc;
				suc=suc->leftptr;
			}

			strcpy(deleted->word,suc->word);
			deleted=suc;
			parent->rightptr=suc->rightptr;
			parent->leftptr=suc->leftptr;
			free(suc);
		}

	}
	return(tree);
}

the program is right without the delete function,so can anyone correct it for me?

Code:

char term=0;
treenode* parent=NULL, *deleted=NULL, *suc, *word;

if (tree=NULL)
   printf("tree empty\n");
term= search(tree, term);

I'm not sure why but you end up searching for term=0 here and
I don't understand why toFind is a charecter and not a c style string when your tree holds strings.

The easiest way to delete from a tree is to do it recursivly.
So you have have a prototype for your function like

treenode* del(treenode** tree, char* toFind);

And then you will probably have a line such as

Code:

int t = strcmp(toFind, (*tree)->word);
if (t < 0)
      *tree = del((*tree)->left, toFind);
else if (t > 0)
      *tree = del((*tree)->right, toFind);
else {
      /* handle the three cases */
      Probably the easiest way is to draw a picture of each one
      the only real tough one is when (*tree)->left != NULL and
      (*tree)->right != NULL and for that one you want to change
      *tree to the least valued node from the right tree 
      (the successor) and  then  delete successor of the
       right  tree.
}