删除一个二叉搜索树节点

删除一个二叉搜索树节点到底哪里出问题了

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

struct Node {
    int data;
    Node* left;
    Node* right;
};

struct Node* FindMin(Node* root)
{
    if (root->left != NULL)
        FindMin(root->left);
    else
        return root;
}

struct Node* Delete(Node* root, int data)
{
    if (root == NULL)
        return root;
    else if (data < root->data)
        root->left = Delete(root->left, data);
    else if (data > root->data)
        root->right = Delete(root->right, data);
    else
    {
        //Case 1: No child
        if (root->left == NULL && root->right == NULL)
        {
            struct Node* temp = root;
            root = NULL;
            free(temp);
            return root;
        }
        //Case 2: One child
        else if (root->left == NULL)
        {
            struct Node* temp = root;
            root = root->right;
            free(temp);
            return root;
        }
        else if (root->right == NULL)
        {
            struct Node* temp = root;
            root = root->left;
            free(temp);
            return root;
        }
        //Case 3: Two child
        else
        {
            struct Node* temp = FindMin(root->right);
            root->data = temp->data;
            root->right = Delete(root->right,temp->data);
            return root;
        }
    }
}

【以下回答由 GPT 生成】

问题分析：根据提供的代码，有几个潜在的问题： 1. 在FindMin函数中没有返回值，需要在递归调用中添加return关键字，修复这个问题。 2. 在Delete函数中，没有处理root为null的情况，需要在函数的开始加入if (root == NULL) return root;的判断。

解决方案：

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

struct Node {
    int data;
    Node* left;
    Node* right;
};

struct Node* FindMin(Node* root)
{
    if (root->left != NULL)
        return FindMin(root->left);
    else
        return root;
}

struct Node* Delete(Node* root, int data)
{
    if (root == NULL)
        return root;

    if (data < root->data)
        root->left = Delete(root->left, data);
    else if (data > root->data)
        root->right = Delete(root->right, data);
    else
    {
        if (root->left == NULL && root->right == NULL)
        {
            struct Node* temp = root;
            root = NULL;
            free(temp);
        }
        else if (root->left == NULL)
        {
            struct Node* temp = root;
            root = root->right;
            free(temp);
        }
        else if (root->right == NULL)
        {
            struct Node* temp = root;
            root = root->left;
            free(temp);
        }
        else
        {
            struct Node* temp = FindMin(root->right);
            root->data = temp->data;
            root->right = Delete(root->right, temp->data);
        }
    }
    return root;
}

这样修改后的代码将能正常删除二叉搜索树中的节点。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/229795
• 你也可以参考下这篇文章：【二叉树】将二叉搜索树转换成一个排序的双向链表
• 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 二维数组的初始化和遍历小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 精讲了33道二叉树经典题目之后，我总结了这些，帮你一举搞定二叉树中的 求二叉搜索树的属性 部分也许能够解决你的问题。