delete node for a binary tree

This is a discussion on delete node for a binary tree within the C Programming forums, part of the General Programming Boards category; I am having serious problems implementing a delete_node function for a binary tree it works fine unless the target to ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    88

    delete node for a binary tree

    I am having serious problems implementing a delete_node function for a binary tree
    it works fine unless the target to be deleted has 2 children. Then the children are lost
    Any help would be much appreciated

    Code:
    int Delete_Node(SSummary *data, Tree_Header *psTree, Tree_node *treecurrent, Tree_node *treeparent, Tree_node *temp)
    {
    	char zip_answer[8];
    	int children_count = 0, confirmation;
    	int comparison_count = 0, y = 0;
    	printf("What zipcode would you like to delete from the tree: ");
    	scanf("%s",&zip_answer);
    	treecurrent = psTree->pRoot; 
    	
    	while(treecurrent != NULL)
    	{
    		
    		comparison_count++;
    		if(strcmp(treecurrent->zipcode, zip_answer) == 0)
    		{
    			//match
    			printf("\nThe record was found with %d comparison(s)",comparison_count);
    			printf("\n---------------Record---------------");
    			printf("\nZipcode: %s",treecurrent->zipcode);
    			printf("\nCity, State: %s, %s",treecurrent->city, treecurrent->state);
    			printf("\nPopulation: %d",treecurrent->population);
    			printf("\nLatitude, Longitude: %-.2f, %-.2f\n\n", treecurrent->latitude, treecurrent->longitude);
    			printf("\n\nAre you sure you want to delete this node?");
    			printf("\n1. Yes");
    			printf("\n2. No\n");
    			scanf("%d",&confirmation);
    			if(confirmation == 2)
    			{
    				break;
    			}
    			//counting the number of children
    			if (treecurrent->left == NULL && treecurrent->right == NULL)
    			{
    				children_count = 0;
    			}
    			else
    			{
    				if(treecurrent->left != NULL)
    				{
    					children_count = 1;
    				}
    				if(treecurrent->right != NULL)
    				{
    					children_count = 1;
    				}
    				else
    				{
    					children_count = 2;
    				}
    			}
    			
    			//proceeding on basis of number of children
    			if(children_count == 0)
    			{
    				//Leaf node//
    				treeparent = treecurrent->parent;
    				treeparent->left = NULL;
    				free(treecurrent);
    			
    			}
    			if(children_count == 1)
    			{
    				//if statement to find if right or left
    				if(treecurrent->right == NULL)
    				{
    					//Single left child
    					treeparent = treecurrent->parent;
    					if(treeparent->right == treecurrent)
    					{
    						//treecurrent is referenced by the right parent pointer
    						treeparent->right = treecurrent->left;
    						treecurrent->left->parent = treeparent;
    						free(treecurrent);
    						
    					}
    					if(treeparent->left == treecurrent)
    					{
    						//treecurrent is referenced by the left parent pointer
    						treeparent->left = treecurrent->left;
    						treecurrent->left->parent = treeparent;
    						free(treecurrent);
    						
    					}
    				}
    				else
    				{
    					//Single Right child
    					treeparent = treecurrent->parent;
    					if(treeparent->right == treecurrent)
    					{
    						//treecurrent is referenced by the right parent pointer
    						treeparent->right = treecurrent->right;
    						treecurrent->right->parent = treeparent;
    						free(treecurrent);
    					
    					}
    					if(treeparent->left == treecurrent)
    					{
    						//treecurrent is referenced by the left parent pointer
    						treeparent->left = treecurrent->right;
    						treecurrent->right->parent = treeparent;
    						free(treecurrent);
    						
    					}
    				}
    			}
    			if(children_count == 2)//got serious problems here//
    			{
    				printf("we are here");//print test
    				//Two Children				
    				treeparent = treecurrent->parent;
    				if (treeparent->left == treecurrent)
    				{
    					treeparent->left = treecurrent->right;
    					temp = treecurrent->right;
    					temp->left = treecurrent->left;
    				}
    				else
    				{
    					temp = treecurrent;
    					temp = temp->left;	 
    					treeparent->right = treecurrent->left;
    					treecurrent->left->right = treecurrent->right;
    					
    				}
    				
    				free(treecurrent);
    				
    				
    			}
    			
    			printf("\nThe record was found and deleted\n");
    			break;
    			}
    
    			else
    			{
    				if(strcmp(treecurrent->zipcode, zip_answer) < 0)
    				{
    					//go right
    					treecurrent = treecurrent->right;
    				}
    				else
    				{
    					//go left
    					treecurrent = treecurrent->left;
    				}
    				
    				
    			}
    			if(treecurrent == NULL)
    			{
    				printf("\nNo record was found\n");
    			}
    			}//end while
    			
    			return 0;
    }

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,647
    Your "children_count" is wrong when both "->left" and "->right" do not equal NULL.
    Haven't looked at the rest of it.

    gg

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    ok changed that part to this
    Code:
    //counting the number of children
    			if (treecurrent->left == NULL && treecurrent->right == NULL)
    			{
    				children_count = 0;
    			}
    			else
    			{
    				if(treecurrent->left != NULL && treecurrent->right != NULL)
    				{
    					children_count = 2;
    				}
    				else
    				{
    					children_count = 1;
    				}
    			
    			}

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    still doesn't work though

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,647

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  3. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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