Thread: program terminates abruptly

  1. #1
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305

    program terminates abruptly

    I have this program of a binary search tree which works fine but now what is happening is that i am trying to delete an element 8 which i dont input into the tree. But i have a condition where in if the element is not present it should simply return and tell the user and continue with its execution. But as soon as the delete statement is executed the program terminates saying that trees.exe has encountered some problem and do you want to tell microsoft about this problem. What can be the other error i cant seem to understand?

    [insert]
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define FALSE 0
    #define TRUE 1
    
    void insert(struct node **root, int data);
    void searchdata(struct node	**root, int data);
    void delete(struct node **root, int data);
    void search(struct node **root, int data, struct node **par, struct node **delnode, int *found);
    void inorder(struct node **root);
    
    struct node 
    {
    	struct node *lchild;
    	int data;
    	struct node *rchild;
    };
    
    int main(void)
    {
    
    	struct node *root = NULL;
    	int data;
    	char ch;
    
    	do
    	{
    		printf("\n Enter the data\n");
    		scanf("%d", &data);
    		fflush(stdin);
    		insert(&root, data);
    		printf("\n Do you want to add more elements\n");
    		scanf("\n%c", &ch);
    		fflush(stdin);
    	}while(ch == 'y' || ch == 'Y');
    
    	printf("\n Before deletion: Inorder\n");
    	inorder(&root);
    
    	delete(&root, 8);
    
    	printf("\n After deletion of 8: Inorder\n");
    	inorder(&root);
    
    	return 0;
    }
    
    void inorder(struct node **root)
    {
    	if(*root == NULL)
    		return;
    	else if(*root != NULL)
    	{
    		inorder(&(*root)->lchild);
    		printf("\n %d", (*root)->data);
    		inorder(&(*root)->rchild);
    	}
    }
    
    // delete the node in the bst where the data occurs
    void delete(struct node **root, int data)
    {
    	struct node *parent, *delnode, *delsuc, *x;
    	int found;
    
    	if(*root == NULL)
    	{
    		printf("\n BST is empty you funky crazy fellow");
    		return;
    	}
    
    	parent = NULL;
    	// BST is not empty so search the parent, delnode 
    	search(root, data, &parent, &delnode, &found);
    	if(found == 0)
    	{
    		printf("\n Data was not found in the tree");
    		return;
    	}
    	
    	if(delnode->lchild != NULL && delnode->rchild != NULL)
    	{
    		// find the inorder successor of the node
    		x = delnode;
    		delsuc = delnode->rchild;
    		parent = delnode;
    
    		while(delsuc->lchild != NULL)
    		{
    			parent = delsuc;
    			delsuc = delsuc->lchild;
    		}
    
    		x->data = delsuc->data;
    		delnode = delsuc;
    	}
    
    	// node to be deleted has no child
    	if(delnode->lchild == NULL && delnode ->rchild == NULL)
    	{
    		if(parent->lchild == delnode)
    			parent->lchild = NULL;
    		else if(parent->rchild == delnode)
    			parent->rchild = NULL;
    		// free the memory
    		free(delnode);
    	}
    
    	// node to be deleted has only one child - left child
    	if(delnode->lchild != NULL && delnode->rchild == NULL)
    	{
    		// set the parent to point to the left child of the node to be deleted
    		if(parent->lchild == delnode)
    			parent->lchild = delnode->lchild;
    		else if(parent->rchild == delnode)
    			parent->rchild = delnode->lchild;
    
    		// free the memory
    		free(delnode);
    	}
    
    	// node to be deleted has only one child - right child
    	if(delnode->lchild == NULL && delnode->rchild != NULL)
    	{
    		// set the parent to point to the right child of the node to be deleted
    		if(parent->lchild == delnode)
    			parent->lchild = delnode->rchild;
    		else if(parent->rchild == delnode)
    			parent->rchild = delnode->rchild;
    
    		// free the memory
    		free(delnode);
    	}
    }
    
    void search(struct node **root, int data, struct node **par, struct node **delnode, int *found)
    {
    	// check if the data is available at the root
    	if((*root)->data == data)
    	{
    		*delnode = *root;
    		*found = TRUE;
    	}
    	else if ((*root)->data > data)
    	{
    		*par = *root;
    		// go to the left of the root
    		search(&(*root)->lchild, data, par, delnode, found);
    	}
    	else if((*root)->data < data)
    	{
    		*par = *root;
    		// go to the right of the root
    		search(&(*root)->rchild, data, par, delnode, found);
    	}
    }
    
    // search the data in the bst
    void searchdata(struct node** root, int data)
    {
    	if((*root)->data == data)
    	{
    		printf("\n Data Found in the tree");
    		return;
    	}
    	// search in the right of the root
    	else if((*root)->data < data)
    	{
    		if((*root)->rchild != NULL)
    		{
    			searchdata(&(*root)->rchild, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return;
    		}
    	}
    	// search in the left of the root
    	else if((*root)->data > data)
    	{
    		if((*root)->lchild != NULL)
    		{
    		searchdata(&(*root)->lchild, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return;
    		}
    	}
    	else
    	{
    		printf("\n Data does not exist in the tree");
    		return;
    	} 
    }
    
    
    void insert(struct node **root, int data)
    {
    	
    	struct node *temp;
    
    	// check if its the first element that i am going to add
    	if(*root == NULL)
    	{
    		*root = (struct node *) malloc(sizeof(struct node));
    		(*root)->lchild = NULL;
    		(*root)->rchild = NULL;
    		(*root)->data = data;
    		return;
    	}
    	// this is not the first element
    	// find its correct place in the tree
    	// data is larger than root so put in the right
    	else
    	{
    		if((*root)->data < data)
    		{
    			insert(&((*root)->rchild), data);
    		}
    	
    		else if((*root)->data > data)
    		{
    			insert(&((*root)->lchild), data);
    		}
    	}
    }

  2. #2
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    I would suggest you initialize found to false before calling search. If search fails, found will have a garbage value, and very probably will not be false.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Location
    Greece,Athens
    Posts
    17
    yes that's the problem.check what the search function returns when it finds nothing.a quick solution is to initialize variable found in delete function as int found=0; or int found =FALSE; .

  4. #4
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    Oh thanks, i did it and it seems to work fine. Also one other problem i figured out was in the search function when i reach a node and its left child is null i was still calling the search function with null as the parameter which is wrong. So i put that check there as well before calling search function with the leftchild or the right child of a node.

    [insert]
    Code:
    void search(struct node **root, int data, struct node **par, struct node **delnode, int *found)
    {
    	// check if the data is available at the root
    	if((*root)->data == data)
    	{
    		*delnode = *root;
    		*found = TRUE;
    	}
    	else if ((*root)->data > data)
    	{
    		*par = *root;
    		// go to the left of the root
    		if((*root)->lchild == NULL)
    			return;
    		search(&(*root)->lchild, data, par, delnode, found);
    	}
    	else if((*root)->data < data)
    	{
    		*par = *root;
    		// go to the right of the root
    		if((*root)->rchild == NULL)
    			return;
    		search(&(*root)->rchild, data, par, delnode, found);
    	}
    }
    
    Anyways thanks for the inputs.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  3. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM