调试BST delete_node函数时触发Illegal instruction异常求助

以下是实现二叉搜索树（BST）的C++代码，Node类包含data、parent、left_child、right_child四个属性，实现了静态的insert和delete_node方法。调试时，执行delete_node(current_node->right_child, val)并返回nullptr后触发了"Illegal instruction"异常，需要排查原因并修复，使delete_node能通过递归删除值为val的后代节点。

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int data;
    Node *parent;
    Node *left_child;
    Node *right_child;
    Node()
    {
        data = 0;
        parent = NULL;
        left_child = NULL;
        right_child = NULL;
    }
    Node(int val)
    {
        data = val;
        parent = NULL;
        left_child = NULL;
        right_child = NULL;
    }

    static void *insert(Node *current_node, int val)
    {
        if (current_node->data == val)
        {
            cout << "Duplicate Value";
            return NULL;
        }
        if (current_node->left_child == NULL && val < current_node->data)
        {
            Node *temp_node = new Node(val);
            current_node->left_child = temp_node;
            temp_node->parent = current_node;
            return NULL;
        }
        if (current_node->right_child == NULL && val > current_node->data)
        {
            Node *temp_node = new Node(val);
            current_node->right_child = temp_node;
            temp_node->parent = current_node;
            return NULL;
        }
        if (current_node->left_child != NULL && val < current_node->data)
        {
            return insert(current_node->left_child, val);
        }
        if (current_node->right_child != NULL && val > current_node->data)
        {
            return insert(current_node->right_child, val);
        }
    };

    static void *delete_node(Node *current_node, int val)
    {
        if (current_node == NULL)
        {
            return nullptr;
        }
        else if (current_node->data == val)
        {
            if (current_node->left_child == NULL)
            {
                Node *parent_node = current_node->parent;
                if (parent_node->left_child == current_node)
                {
                    Node *right_child = current_node->right_child;
                    right_child->parent = parent_node;
                    parent_node->left_child = right_child;
                }
                else if (parent_node->right_child == current_node)
                {
                    Node *right_child = current_node->right_child;
                    right_child->parent = parent_node;
                    parent_node->right_child = right_child;
                }
            }
            else if (current_node->right_child == NULL)
            {
                Node *parent_node = current_node->parent;
                if (parent_node->left_child == current_node)
                {
                    Node *left_child = current_node->left_child;
                    left_child->parent = parent_node;
                    parent_node->left_child = left_child;
                }
                else if (parent_node->right_child == current_node)
                {
                    Node *left_child = current_node->left_child;
                    left_child->parent = parent_node;
                    parent_node->right_child = left_child;
                }
            }
        }
        else if (current_node->data > val)
        {
            delete_node(current_node->left_child, val);
        }
        else if (current_node->data < val)
        {
            delete_node(current_node->right_child, val);
        }
    };
};
int main()
{
    Node *root = new Node(4);
    Node::insert(root, 1);
    Node::insert(root, 2);
    Node::insert(root, 3);
    Node::insert(root, 5);
    Node::insert(root, 6);
    Node::delete_node(root, 10);
    Node::delete_node(root, 1);
    return 0;
}

异常原因分析 #

• 空指针访问：
  1. 当删除的节点没有对应子节点时（比如删除节点1时，它的right_child是NULL），代码直接执行right_child->parent = parent_node，此时right_child为空，访问其成员会触发未定义行为，导致崩溃。
  2. 如果删除的是根节点，current_node->parent为NULL，此时访问parent_node->left_child或parent_node->right_child会直接访问空指针，引发异常。
• 函数返回值不规范：
  delete_node声明返回void*，但多个分支（比如递归调用后、处理完节点删除后）没有return语句，这会导致函数返回不确定的值，触发栈帧错误，进而引发"Illegal instruction"异常。
• 递归调用未返回：
  在递归调用delete_node(current_node->left_child, val)和delete_node(current_node->right_child, val)时，没有返回值，不符合函数的返回类型要求，加剧了未定义行为。
• 逻辑缺失：
  未处理节点同时存在左右子节点的情况，这不仅是功能缺陷，也可能导致后续逻辑异常。

修复方案与代码 #

针对上述问题，我们对代码进行如下修改：

1. 将delete_node的返回类型改为void，因为该函数不需要返回值，避免返回值不规范带来的问题。
2. 操作子节点前先判断是否为空，避免空指针访问。
3. 处理根节点的删除情况。
4. 实现节点同时有左右子节点的删除逻辑（通过寻找后继节点替代）。
5. 确保递归调用逻辑正确。

修复后的完整代码：

#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
    int data;
    Node *parent;
    Node *left_child;
    Node *right_child;

    Node() : data(0), parent(nullptr), left_child(nullptr), right_child(nullptr) {}
    Node(int val) : data(val), parent(nullptr), left_child(nullptr), right_child(nullptr) {}

    // 辅助函数：找到子树中的最小节点（用于寻找后继）
    static Node* find_min(Node* node) {
        while (node->left_child != nullptr) {
            node = node->left_child;
        }
        return node;
    }

    static void insert(Node *current_node, int val)
    {
        if (current_node->data == val)
        {
            cout << "Duplicate Value" << endl;
            return;
        }
        if (val < current_node->data) {
            if (current_node->left_child == nullptr) {
                Node *temp_node = new Node(val);
                current_node->left_child = temp_node;
                temp_node->parent = current_node;
            } else {
                insert(current_node->left_child, val);
            }
        } else {
            if (current_node->right_child == nullptr) {
                Node *temp_node = new Node(val);
                current_node->right_child = temp_node;
                temp_node->parent = current_node;
            } else {
                insert(current_node->right_child, val);
            }
        }
    };

    static void delete_node(Node*& root, int val) {
        Node* current_node = root;
        // 先找到要删除的节点
        while (current_node != nullptr && current_node->data != val) {
            if (val < current_node->data) {
                current_node = current_node->left_child;
            } else {
                current_node = current_node->right_child;
            }
        }
        if (current_node == nullptr) {
            cout << "Value not found in tree" << endl;
            return;
        }

        // 情况1：节点没有子节点
        if (current_node->left_child == nullptr && current_node->right_child == nullptr) {
            if (current_node == root) {
                root = nullptr;
            } else {
                if (current_node->parent->left_child == current_node) {
                    current_node->parent->left_child = nullptr;
                } else {
                    current_node->parent->right_child = nullptr;
                }
            }
            delete current_node;
        }
        // 情况2：节点只有一个子节点
        else if (current_node->right_child == nullptr) {
            Node* child = current_node->left_child;
            if (current_node == root) {
                root = child;
                child->parent = nullptr;
            } else {
                child->parent = current_node->parent;
                if (current_node->parent->left_child == current_node) {
                    current_node->parent->left_child = child;
                } else {
                    current_node->parent->right_child = child;
                }
            }
            delete current_node;
        } else if (current_node->left_child == nullptr) {
            Node* child = current_node->right_child;
            if (current_node == root) {
                root = child;
                child->parent = nullptr;
            } else {
                child->parent = current_node->parent;
                if (current_node->parent->left_child == current_node) {
                    current_node->parent->left_child = child;
                } else {
                    current_node->parent->right_child = child;
                }
            }
            delete current_node;
        }
        // 情况3：节点有两个子节点，找后继节点替代
        else {
            Node* successor = find_min(current_node->right_child);
            current_node->data = successor->data;
            // 递归删除后继节点
            delete_node(root, successor->data);
        }
    };
};

int main()
{
    Node *root = new Node(4);
    Node::insert(root, 1);
    Node::insert(root, 2);
    Node::insert(root, 3);
    Node::insert(root, 5);
    Node::insert(root, 6);
    
    Node::delete_node(root, 10); // 不存在的节点，提示未找到
    Node::delete_node(root, 1); // 删除节点1
    
    // 可添加中序遍历等代码验证结果
    return 0;
}

修改说明 #

• 调整delete_node为接收根节点的引用，方便修改根节点的指向。
• 先遍历找到要删除的节点，再分三种情况处理：无子女、单子女、双子女。
• 操作子节点前先判断是否为空，避免空指针访问。
• 添加find_min辅助函数，用于寻找双子女节点的后继节点。
• 修复了返回值问题，将insert和delete_node的返回类型改为void，避免不必要的返回值错误。
• 添加了节点不存在的提示，提升调试友好性。

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