c - Cの二分探索木で削除

Question

C で BST を実装しました。挿入と検索は正常に機能します。ただし、ルート ノードを削除する場合、delete には問題があります。ルート ノードへのポインタを解放できません。二重ポインターとして渡せば可能ですが、二重ポインターを使用せずにコードをシンプルにしたかったのです。ここでは、ルート ノードを指すヘッド ポインターはありません。ルート ノードへのヘッド ポインタを使用する必要がありますか?

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
    struct node* node = malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return(node);
}

static int lookup(struct node* node,int target)
{
    if(node==NULL)
    {
        return(0);
    }
    else
    {
        if(target == node->data)
        {
            return(1);
        }
        else
        {
            if(target < node->data)
            {
                return(lookup(node->left,target));
            }
            else
            {
                return(lookup(node->right,target));
            }
        }
    }
}


struct node* insert(struct node* node, int data)
{
    if(node==NULL)
    {
        return(newNode(data));
    }   
    else
    {
        if(data < node->data)
        {
            node->left =insert(node->left,data);
        }
        else
        {
            node->right=insert(node->right,data);
        }
        return(node);
    }
}

struct node* delete(struct node* node, struct node* pnode, int target)
{
    struct node* rchild;
    struct node* rchildparent;
    if(node==NULL)
    {
        return(pnode);
    }
    else
    {
        if(target == node->data)
        {
            if(node->left == NULL && node->right == NULL) //leaf node
            {
                if(pnode == NULL) //special case deleting the root node
                {
                    free(node);
                    return(NULL);
                }
                if(pnode->left == node)
                {
                    pnode->left = NULL;
                }
                else
                {
                    pnode->right = NULL;
                }
                free(node);
                return(pnode);
            }
            if(node->left ==NULL ) //one child
            {
                if(pnode == NULL) //deleting root having no left child
                {
                    struct node* temp = node;
                    node = node->right;
                    free(temp);
                    return(node);
                }
                if(pnode->left == node)
                {
                    pnode->left = node->right;
                }
                else
                {
                    pnode->right = node->right;
                }   
                free(node);
                return(pnode);
            }
            if(node->right ==NULL ) //one child
            {
                if(pnode == NULL) //deleting root having no right child
                {
                    struct node* temp = node;
                    node = node->left;
                    free(temp);
                    return(node);
                }
                if(pnode->left == node)
                {
                    pnode->left = node->left;
                }
                else
                {
                    pnode->right = node->left;
                }   
                free(node);
                return(pnode);
            }

            //two children case
            rchild = node->right;
            rchildparent=node;
            while(rchild->left != NULL)
            {
                rchildparent=rchild;
                rchild = rchild->left;
            }
            node->data=rchild->data;
            if(rchildparent == node)
            {
                //rchildparent->right=rchild->right;
                node->right=rchild->right;
            }
            else
            {
                //rchildparent->left=NULL;
                rchildparent->left=rchild->right;
            }
            free(rchild);
            if(pnode ==NULL) //root node
            {
                return(node);
            }           
            return(pnode);
        }
        else
        {
            if(target < node->data)
            {
                delete(node->left,node,target);
                return(node);
            }
            else
            {
                delete(node->right,node,target);
                return(node);
            }
        }

    }

}
void printinorder(struct node* node)
{
    if(node == NULL)
    {
        return;
    }   
    printinorder(node->left);
    printf("%d\t",node->data);
    printinorder(node->right);
}
int main()
{
    clock_t start,end;
    struct node* root = newNode(3);
    insert(root,7);
    insert(root,7);
    insert(root,7);
    printinorder(root);
    printf("\n");
    root = delete(root,NULL,6);
    printinorder(root);
    printf("\n");
}

modifiable lvalue編集: @提案に従ってコードを修正しました。削除ロジックを改善する方法はありますか?

Answer 1

delete から head ノードを返し、 main 関数で head を次のように管理します: root = delete(root, NULL, 10);、 insert: についても同じことを行いroot = insert(root,/*...*/);ます。