Thread: Problem with BST deletion

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    2

    Problem with BST deletion

    I've got problem when i'm using inorder fuction after delete a data from BST

    usually if i don't use delete function i can print data by use inorder fuction normally.

    and the second problem is when i want to delete node that doesn't have a children the problem will show because the node that i would delete is nothing happening example

    9
    5 10



    DATA >>

    11
    / \
    5 18
    / \
    16 24
    / \
    15 17

    <<<


    Code:
    #include<stdio.h>
    #include<conio.h>
    typedef struct treetype
    {
    	int num;
    	struct treetype *left;
    	struct treetype *right;
    }T;
    
    void insertnode(T **bst,T *p)
    {
    	T *prev,*start;
    	start=*bst;
    	int flag=-1;
    	if(*bst==NULL)
    	{
    		(*bst)=p;
    		printf("\nCreate parent node >> %d",(**bst).num);
    	}
    	else
    	{       while(start!=NULL)
    		{
    			prev=start;
    			if((*p).num>(*start).num)
    			{
    				start=(*start).right;
    				flag=0;
    			}
    			else
    			{
    				start=(*start).left;
    				flag=1;
    			}
    		}
    		if(flag==0)
    		{
    			(*prev).right=p;
    			printf("\nAdd %d to right of %d",(*p).num,(*prev).num);
    		}
    		else if(flag==1)
    		{
    			(*prev).left=p;
    			printf("\nAdd %d to left of %d",(*p).num,(*prev).num);
    		}
    		else
    		printf("\nCannot insert node");
    	}
    }
    
    void deletebst(T **bst,int target)
    {
    	T *start,*prev;
    	start=*bst;
    	while(start!=NULL)
    	{
    		prev=start;
    		if(target<(*start).num)
    		start=(*start).left;
    		else if(target>(*start).num)
    		start=(*start).right;
    		else
    		{
    			if((*start).right==NULL)
    			{
    				start=(*start).left;
    				delete prev;
    			}
    			else if((*start).left==NULL)
    			{
    				start=(*start).right;
    				delete prev;
    			}
    			else
    			{
    			       prev=(*start).left;
    			       while((*prev).right!=NULL)
    			       prev=(*prev).right;
    			       (*start).num=(*prev).num;
    			       delete prev;
    			}
    		}
    	}
    }
    
    void getdata(T **bst)
    {
    	FILE *inf;
    	T *p;
    	inf=fopen("data.txt","r");
    	*bst=NULL;
    	while(!feof(inf))
    	{
    		p=new T;
    		fscanf(inf,"%d",&(*p).num);
    		(*p).right=(*p).left=NULL;
    		insertnode(bst,p);
    	}
    	printf("\nFinishing");
    }
    
    void inorder(T *bst)
    {
    	if(bst!=NULL)
    	{
    		inorder((*bst).left);
    		printf("%d ",(*bst).num);
    		inorder((*bst).right);
    	}
    }
    
    void main()
    {
    	T *bst,*prev;
    	int ans;
    	clrscr();
    	getdata(&bst);
    	printf("\n");
    	inorder(bst);
    	deletebst(&bst,11);
    	printf("\n");
            inorder(bst);
    	getch();
    
    }

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    1. do not use foef to control loop - read FAQ
    2. Why you do not use ->
    It is stamdard syntax and therefore - more readable
    Code:
    p->right=p->left=NULL;
    3. Your have some indentation problems
    Code:
    prev=(*start).left;
    			       while((*prev).right!=NULL)
    			       prev=(*prev).right;
    			       (*start).num=(*prev).num;
    			       delete prev;
    Don't you loose the ordering of your tree in this code-snipplet?
    4. conio.h is not standard - better get rid of it and its functions
    5. main should be declared as
    Code:
    int main(void)
    read FAQ
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    2
    thanks i will try ur sugges

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. File deletion problem...
    By Junior89 in forum C++ Programming
    Replies: 5
    Last Post: 07-13-2007, 02:01 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM