Deleting from Binary search trees

This is a discussion on Deleting from Binary search trees within the C Programming forums, part of the General Programming Boards category; Hey there... can anyone suggest code for deleting a term from a tree.. I have a base code for searching ...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    4

    Unhappy 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...

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    If what you are going to delete has no children, then the pointer to the node you are deleting should be set to NULL. If the node you are deleting has one child node/subtree, then the pointer to the node you are deleting should be set to the node/subtree. If the what you are deleting has two child nodes/subtrees, then the pointer to the node you are deleting can be set to one of the subtrees, left or right it doesn't matter, and you can then reinsert the remaining node/subtree back into the root of the tree using whatever add/insert function you have created to insert a new node into the tree.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    4

    Question

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

  4. #4
    Registered User
    Join Date
    Dec 2001
    Posts
    21
    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

  5. #5
    Registered User
    Join Date
    Feb 2002
    Posts
    9

    same problem

    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.

  6. #6
    Registered User
    Join Date
    Feb 2002
    Posts
    9

    code

    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?

  7. #7
    Unregistered
    Guest
    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.
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 11:57 AM
  2. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  3. problem with binary search trees
    By Daniel in forum C++ Programming
    Replies: 1
    Last Post: 03-11-2003, 03:59 PM
  4. Ornery binary search algorithm
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 02:32 PM
  5. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 06:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21