关于二叉搜索树(BST)deleteNode中指针操作与后继节点删除的疑问

问题1：处理单孩子/叶子节点时，为何能对*tree赋值？修改nodeToDelete为何会出错？ #

你代码里的*tree并不是固定的根指针——递归调用delete时，每次传入的是当前子树根节点指针的地址（比如父节点的左/右指针的地址）。对*tree赋值，本质是修改父节点中指向当前节点的指针，让它直接指向删除节点的子节点，这样就能正确断开原节点的链接，避免野指针问题。

你尝试的修改代码有两个致命问题：

1. nodeToDelete是局部变量，修改它的指针值不会影响父节点中存储的指针，父节点仍然指向已经被free的内存，后续访问必然触发内存错误。
2. 直接free(temp)后，原节点的子节点没有被接到树的正确位置，相当于丢失了这部分子树，同时父节点的指针变成野指针，后续操作极大概率引发malloc错误或程序崩溃。

错误代码片段：

// If the node to delete has only one child or is a leaf
if (nodeToDelete->left == NULL) {
    treeNode* temp = nodeToDelete;
    nodeToDelete = nodeToDelete->right;
    free(temp);
} else if (nodeToDelete->right == NULL) {
    treeNode* temp = nodeToDelete;
    nodeToDelete = nodeToDelete->left;
    free(temp);
}

问题2：是否必须递归删除中序后继？能否直接free(successor)？ #

不能直接free(successor)，因为中序后继节点（右子树的最左节点）可能存在右子节点（它的左子一定为空，但右子可能非空）。如果直接free，会丢失这部分右子树，破坏BST的结构完整性。

递归调用delete(&(nodeToDelete->right), successor->data)的作用，就是让delete函数自动处理后继节点的子节点：如果后继是叶子节点，直接删除；如果有右子节点，就把右子节点接到后继父节点的左指针上，保证树的链接逻辑完整。

原完整代码 #

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

// Define the structure for a tree node
typedef struct treeNode 
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
} treeNode;

treeNode* createNode(int data)
{
    treeNode* newNode = (treeNode*)malloc(sizeof(treeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

treeNode* search(treeNode** tree, int data)
{
    if((*tree) == NULL) return NULL;
    else if((*tree)->data == data) return *tree;
    else if(data <= (*tree)->data) return search(&((*tree)->left),data);
    else if(data > (*tree)->data) return search(&((*tree)->right),data);
    else return NULL;
}

void insert(treeNode** tree, int data)
{
    if(*tree == NULL) *tree = createNode(data);
    else if(data <= (*tree)->data) insert(&((*tree)->left), data);
    else if(data > (*tree)->data) insert(&((*tree)->right), data);
}

void delete(treeNode** tree, int data)
{
    // If tree is empty
    if (*tree == NULL) {
        printf("Not Found");
        return;
    }

    treeNode* nodeToDelete = search(tree, data);

    // If data doesn't exist in tree
    if (nodeToDelete == NULL) {
        printf("Not Found");
        return;
    }

    // If the node to delete has only one child or is a leaf
    if (nodeToDelete->left == NULL) {
        treeNode* temp = nodeToDelete;
        *tree = nodeToDelete->right;
        free(temp);
    } else if (nodeToDelete->right == NULL) {
        treeNode* temp = nodeToDelete;
        *tree = nodeToDelete->left;
        free(temp);
    }
    // If the node to delete has two children
    else {
        // Find the in-order successor
        treeNode* successor = nodeToDelete->right;
        while (successor->left != NULL) {
            successor = successor->left;
        }

        // Copy the data of the in-order successor to the node to be deleted
        nodeToDelete->data = successor->data;

        // Delete the in-order successor recursively
        delete(&(nodeToDelete->right), successor->data);
    }
}

int main()
{
    int c = -1, i, d, s;
    treeNode* tree = NULL;
     
    while (c != 0)
    {
        printf("Please input your choice(1/2/3/0): ");
        scanf("%d", &c);

        switch(c)
        {
            case 1: //insert

                printf("Enter a number to insert: ");
                scanf("%d", &i);
                insert(&tree, i);
                break;

            case 2: //delete

                printf("Enter a number to delete: ");
                scanf("%d", &d);
                delete(&tree, d);
                break;

            case 3: // search

                printf("Enter a number to search: ");
                scanf("%d", &s);
                if(search(&tree, s) != NULL) printf("Found.\n");
                else printf("Not Found.\n");
                break;
        }
    }
}

内容的提问来源于stack exchange，提问作者neil dund