递归如何使用 Void 而不是函数的逻辑

Question

这是一个简单的二叉树节点删除函数，现在我想将 removeElement 函数改为 void。至少从我收集到的信息来看，大多数教程都没有涵盖如何做到这一点。

基本代码：

struct treeNode* removeElement(struct treeNode *root, int data)
{
    if(root==NULL)
        return NULL;
    if (data>root->data)
        root->right = removeElement(root->right, data);
    else if(data<root->data)
        root->left = removeElement(root->left, data);
    else
    {
        
        if(root->left==NULL && root->right==NULL)
        {
            free(root);
            return NULL;
        }

        else if(root->left==NULL || root->right==NULL)
        {
            struct treeNode *temp;
            if(root->left==NULL)
                temp = root->right;
            else
                temp = root->left;
            free(root);
            return temp;
        }

        else
        {
            struct treeNode *temp = find_minimum(root->right);
            root->data = temp->data;
            root->right = removeElement(root->right, temp->data);
        }
    }
    return root;
}

我试过的

void removeElement(struct treeNode **root, int data)
{
    if(*root==NULL)
        return;//dont know if this is correct
    if (data>(*root)->data)
         removeElement(&(*root)->right, data);
    else if(data<(*root)->data)
        removeElement(&(*root)->left, data);
    else
    {
        //dont know how to continue 
        if((*root)->left==NULL && (*root)->right==NULL)
        {
        }
         else if(*root)->left==NULL || *root)->right==NULL)
          {}

我的主要问题是我不知道代码应该是什么样子，因为我不能在 void 中 return，所以递归对我来说变得很棘手。如果有人愿意帮助我 else if(*root)->left==NULL || *root)->right==NULL) 我相信我可以处理剩下的事情。

我不知道这是否有效 question/answered 之前。如果不是，请告诉我。如果需要，我会尝试改进它或删除问题。感谢您提供的任何帮助。

Answer 1

您发送了指向 'left' 或 'right' 的指针，它们是此叶的 parent 节点的成员。所以，你只需要释放它并进行 NULLify，如下所示：

       if((*root)->left==NULL && (*root)->right==NULL)
        {
            free(*root);
            *root = NULL;
            return;
        }

在第二部分，如果节点只有一个 child，根据你的算法，这个 child 被重新分配给 parent 的相应分支。我认为，以下是正确的：

else if((*root)->left==NULL || (*root)->right==NULL)
        {            
            struct treeNode *temp;
            if(root->left==NULL)
                temp = (*root)->right;
            else
                temp = (*root)->left;
            free(*root);
            *root = temp; // << assign temp to the parents left or right
            return ;
        }

递归如何使用 Void 而不是函数的逻辑

The Logic on How Rekursion Functions with Void instead of Functions

c

recursion

linked-list

binary-tree

binary-search-tree