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,788
    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