Click here to Skip to main content
15,860,972 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
/*           12
                  /\
                 9  15
                / \   \
               4  11   21
The node with data 15 is not being deleted in the above binary serach tree.*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef struct Node 
{
    int info;
    struct Node* left;
    struct Node* right;
}node;

void deleteItem(node*,node*,int);
void deleteNode(node *root,node* parent)
{
    node *temp;
    if(root->left==NULL)/*Only left child*/
    {
        if(parent->left==root)
        parent->left=root->right;
        else
        parent->right==root->right;
        free(root);
    }
    else if(root->right==NULL)/*Only right child*/
    {
        if(parent->left==root)
        parent->left=root->left;
        else
        parent->right=root->left;
        free(root);
    }
    else/*Both children exist*/
    {
        temp=root->left;
        while(temp->right!=NULL)
        temp=temp->right;
        root->info=temp->info;
        deleteItem(root->left,root,temp->info);
        free(root);
    }
}

void insert(node **root,int item)
{
    node *parent,*cur;
    parent=NULL;
    cur=*root;
    while(cur!=NULL)
    {
        parent=cur;
        if(item<=cur->info)
        cur=cur->left;
        else
        cur=cur->right;
    }
    if(*root==NULL)
    {
        *root=(node*)malloc(sizeof(node));
        (*root)->info=item;
        (*root)->left=NULL;
        (*root)->right=NULL;
    }
    else
    {
        node *newNode=(node*)malloc(sizeof(node));
        newNode->info=item;
        newNode->left=NULL;
        newNode->right=NULL;
        if(item<parent->info)
        parent->left=newNode;
        else
        parent->right=newNode;
    }
}

void deleteItem(node *root,node *parent,int item)
{
    if(root==NULL)
    return;
    node *cur=root;
    if(item<cur->info)
    deleteItem(cur->left,cur,item);
    else if(item>cur->info)
    deleteItem(cur->right,cur,item);
    else
    deleteNode(cur,parent);
}
    
int main()
{
    int a[]={12,9,4,11,15,21};
    int i;
    node *root,*ptr;
    root=NULL;
    for(i=0;i<6;i++)
    insert(&root,a[i]);
    ptr=root;
    while(ptr!=NULL)
    {
        printf("%d\n",ptr->info);
        ptr=ptr->right;
    }
    deleteItem(root,NULL,15);
    ptr=root;
    printf("\n\n\n\n");
    while(ptr!=NULL)
    {
        printf("%d\n",ptr->info);
        ptr=ptr->right;
    }
    getch();
}
Posted
Updated 17-Aug-13 20:11pm
v2

Look at your code:
C#
void deleteNode(node *root,node* parent)
{
    node *temp;
    if(root->left==NULL)/*Only left child*/
    {
        if(parent->left==root)
        parent->left=root->right;
        else
        parent->right==root->right;
        free(root);
    }
    else if(root->right==NULL)/*Only right child*/
    {
        if(parent->left==root)
        parent->left=root->left;
        else
        parent->right=root->left;
        free(root);
    }
    else/*Both children exist*/
    {
        temp=root->left;
        while(temp->right!=NULL)
        temp=temp->right;
        root->info=temp->info;
        deleteItem(root->left,root,temp->info);
        free(root);
    }
}
Do you really want "==" in there? :laugh:
C++
parent->right==root->right;



We've all done it! :O
 
Share this answer
 
Comments
Brady Bar 18-Aug-13 2:58am    
Oh thanks Mr. Griff.I made a blunder.The code worked right away as I removed it
OriginalGriff 18-Aug-13 3:14am    
Too easy to do - and too easy to miss. I find I read the code I meant to write, rather than the code I *did* write... :laugh:
Let's do one step at a time. I'll tell you just the problems I can see immediately. Fix them first, and then see if you can solve the problem completely.

Both deleteNode and deleteItem have some wrong set of parameters. Your function deleteItem has a redundant parameter item. You don't really use it at all, you only pass it to recursive calls to the same function, and the value is actually ignored. Remove it. Now, the parameter root sounds like redundant, but perhaps it is only named in a misleading way. If you have a node parent, you don't really need a root. If you work with the tree, you have to remember the root anyway. But you still need two parameters: a node to be deleted and its parent node, because after deletion you will need to set left or right member to null after the corresponding sun-tree is deleted.

Now, deletion is complicated because you don't have a pointer the the parent node stored in each node. This is the redundancy, but it will improve performance dramatically. Right now, you try to perform the node deletion recursively (which is quite a decision). You can apply some deletion function. The tree is binary, so you get left and right sub-tree of the node, and for each of the non-null sub-tree call the same function recursively. Recursion is stopped on each of the terminal nodes — those which have both left == 0 and right == null; then and only then you can delete the node, otherwise you would have children nodes lost. But then, you will need to scan the sub-tree starting from the parent again, to delete the nodes which became terminal after previous set of deletion, until you have only the node to be deleted. So think about adding the parent member to the structure and leveraging it, in particular, during deletion.

—SA
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900