c - 不递归地从二叉搜索树中删除一个节点

Question

我有一个二叉搜索树。我想从中删除一个节点:

void deleteANode(struct node *head, int value) {
    //let us find the node
    struct node *temp = head;
    struct node *parent = NULL;

    //let us find the node
    while (temp != NULL) {
        if (value > temp->data) {
            parent = temp;
            temp = temp->right;
        } else
        if (value < temp->data) {
            parent = temp;
            temp = temp->left;
        } else {
            //let us check for child nodes
            //
            if (temp->left == NULL && temp->right == NULL) {
                printf("Deleting a leaf.\n");

                temp = NULL;
                printf("Set temp null.\n");
                free(temp);
                break;
            } else
            if (temp->left == NULL || temp->right == NULL) {
                printf("Deleting a one child.\n");
                //one of the child is null
                if (temp->left != NULL) {
                    parent->left = temp->left;
                } else {
                    parent->right = temp->right;
                }
                free(temp);
            } else {
                printf("Deleting two child parent.\n");
                //both of them are not NULL
                //need to find the pre-order successor
                struct node *temp2 = temp->right;

                while (temp2->left != NULL) {
                    temp2 = temp2->left;
                }
                //found the successor.
                temp->data = temp2->data;
                free(temp);
            }
            break;
        }
    }
}

我正在尝试删除此 block 中的叶节点:

if (temp->left == NULL && temp->right == NULL) {
    printf("Deleting a leaf.\n");

    temp->data = NULL;
    printf("Set temp null.\n");
    free(temp);
    break;
}

但是上面的代码不起作用。

我正在调用上面的方法:

deleteANode(head, 3);

前序遍历前后相同:

5 4 3 10 7 20 Deleting a leaf. Set temp null. =============== 5 4 3 10 7 20

我做错了什么。

根据@pstrjds 评论更新:

if (temp->left == NULL && temp->right == NULL ) {
    printf("Deleting a leaf.\n");
    parent->left = NULL;
    parent->right = NULL;
    free(temp);
    temp = NULL;
    printf("Set temp null.\n");
    break;
}

叶节点工作正常。需要为有两个 child 的节点工作。

Answer 1

在删除叶子的代码块中，您实际上并没有释放节点，也没有更新父节点以不再指向它。

if ( temp -> left == NULL && temp -> right == NULL )
{
    printf("Deleting a leaf.\n");
    if (parent->left == temp)
    {
        parent->left = NULL;
    }
    else
    {
        parent->right = NULL;
    }

    free(temp);
    temp = NULL;
    printf("Set temp null.\n");
    break;
 }

您实际上可以删除行 temp = NULL 并将 break; 更改为 return 语句。