GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 29-Apr-2009, 02:56
aijazbaig1's Avatar
aijazbaig1 aijazbaig1 is offline
Member
 
Join Date: May 2006
Location: India
Posts: 174
aijazbaig1 has a spectacular aura aboutaijazbaig1 has a spectacular aura about
Question

Binary tree deletion algorithm


Hello,
Ive been trying to write a program to delete a node from a binary tree. The algorithm is pretty simple for a node with no children (leaf) and a node with one child. However for a node with 2 children, heres what the problem is (what the text says so atleast):
When a node with 2 children is deleted, another node must take its place. However we cannot simply assign the parent of the node being deleted to one of the children of the deleted node as then the following characteristic of a binary tree doesn't hold: values in any left subtree are to be less than the value in the parent node and values in any right subtree are to be greater than the parent node.

I am having trouble understanding or rather visualizing this problem. So heres to give an example:

Shown in the picture attached is a sample binary tree in which I decide to delete node 97. If I replace it with 92 then as it shows there is no problem except that I would have to assign the right pointer of 92 to 99 and the rest takes care of itself. However when I replace 97 with 99, then in that case I have no where to shift 92 as it will be competing with 98 (since neither 92 nor 98 can be on the right side of 99). Is this the problem that the text talks about in the last paragraph?
Attached Images
File Type: jpg Binary_tree.jpg (12.3 KB, 482 views)
__________________
Hope to hear from you guys!

--------------------------------------------------

Best Regards,
Aijaz Baig.
  #2  
Old 27-Feb-2010, 01:13
murugaperumal murugaperumal is offline
New Member
 
Join Date: Feb 2010
Posts: 15
murugaperumal has a little shameless behaviour in the past

Re: Binary tree deletion algorithm


Dear Friend,

I have attached program to delete the element in the Binary Tree

CPP / C++ / C Code:
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct tree
{
        int node  ;
         struct tree *left ;
         struct tree *right;

} ;

struct tree *new1();
struct tree *delete(struct tree * ,int );

struct tree *addtree(struct tree *p,int w )
{
        int cond;
        if(p==NULL)
        {
                p=new1();
                p->node=w;
                p->left=p->right=NULL;
        }
        else
        {
                if(p->node >= w )
                p->left=addtree(p->left,w);
        else
                p->right=addtree(p->right,w);
        }
        return p;
}

void treeprint(struct tree *p)
{
        if(p!=NULL)
        {
                treeprint(p->left);
                printf("%d \n",p->node);
                treeprint(p->right);
        }
}

struct tree *new1 (void)
{
        return(struct tree *)malloc(sizeof(struct tree));
}

int W ;

        static int i;

int MIN;
main ( int argc, char *argv[] )
{
struct tree *root = NULL;

root=addtree(root,8);
root=addtree(root,2);
root=addtree(root,10);
root=addtree(root,1);
root=addtree(root,5);
root=addtree(root,4);
root=addtree(root,9);
root=addtree(root,15);
treeprint(root);
puts("-----------------------");
printf ("Tree After deleting :\n");
delete(root,2);
treeprint(root);
                return 0;
}           

struct tree * delete(struct tree *p, int w )
{
        struct tree *buf ;

        if (p==NULL)
                return NULL ;
        else if (w < p->node )
        {
                p->left =delete(p->left ,w );
        }
        else if (w > p->node )
        {
                p->right =delete(p->right ,w ) ;
        }
        else
        {
                if (p->left !=NULL && p->right !=NULL )
                {
                        buf=p->right ;
                        p->node=buf->node ;
                        p->right= delete(p->right,p->node);
                }

             else if ( p->left == NULL )
                {
                        buf=p;
                        p=p->right;
                }
                else if (p->right == NULL )
                {
                        buf=p ;
                        p=p->left ;
                }
        }
}
Last edited by LuciWiz : 27-Feb-2010 at 01:17. Reason: Please insert your C++ code between [cpp] & [/cpp] tags
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Link List In C Peter_APIIT C Programming Language 33 12-Jun-2008 13:33
Please Help. I have 3 Qns regarding AVL tree in data structure , Kindly give answer syamsankar C++ Forum 1 30-Mar-2007 08:29
can anyone help me with my tree :) bioeng_mtm C++ Forum 5 22-Apr-2006 12:50
printing binary search tree nkhambal C Programming Language 2 26-Mar-2005 03:01
Binary Tree Trouble neufunk C Programming Language 4 06-Dec-2004 09:52

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 22:27.


vBulletin, Copyright © 2000 - 2014, Jelsoft Enterprises Ltd.