开发者

Deleting nodes in BST using free(N)

I'm coding a binary search tree and I'm having a little trouble finding a way to delete node effectively.

I have this code :

struct node* deleteNode(int i, struct node *N)

{
    if (N==NULL)
    {
        return NULL;
    }
    else if (i<N->value)
 开发者_StackOverflow   {
        N->size--;
        N->lChild=deleteNode(i,N->lChild);
    }
    else if (i>N->value)
    {
        N->size--;
        N->rChild=deleteNode(i,N->rChild);
    }
    else if (N->lChild==NULL)
    {
        return N->rChild;
    }
    else if (N->rChild==NULL)
    {
        return N->lChild;
    }
    else
    {
        N->size--;
        N->value=findMin(N->rChild);
        N->rChild=deleteNode(N->value,N->rChild);
    }
    return N;
}

And N is a node structure which have 5 fields : value, lChild, rChild, size, height. In fact what I'm doing here is to make the tree not to point toward the node that I want to delete but when I'm trying to put something like :

    else if (N->rChild==NULL)
    {
        free(N);
        N=NULL;
        return N->lChild;
    }

Or every similar looking code, it doesn't work. Can someone point me in the right direction please? Thank you.


First of all you're saying N=NULL and then calling N->lchild N is null and pointing to nothing so how do you expect to get the lchild value?

Since this is homework I won't give a direct answer but hints.

To delete the node, check if it has children, if it doesnt free it and remove references to it such as the parents child ptr. If it has 1 child swap the ptr that points to the node you want to delete with the child and free the node. The same applies if you also have 2 children.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜