二叉搜索树插入节点触发未处理异常：m_father为空指针

从你提供的代码和调试信息来看，程序崩溃的核心原因是当树为空（root == NULL）时，代码后续仍然尝试访问m_father（此时为nullptr）的成员，同时插入逻辑还存在多处逻辑错误，具体问题和修复方案如下：

主要错误点分析 #

1. 空树场景下的非法访问 #

当root == NULL时，你执行了root = temp;，但代码没有终止后续逻辑，继续执行了else if判断和最后的m_father->m_left_child = temp;。此时m_father还是初始的NULL，直接访问m_father->m_left_child必然触发写入访问冲突，这就是调试器提示的核心问题。

2. 循环内的逻辑完全错误 #

• 条件判断毫无意义：if (m_father->m_key > x->m_key) 这里m_father刚被赋值为x，相当于比较节点自身的key，完全不符合二叉搜索树的遍历规则。正确逻辑应该是比较要插入的节点temp的key与当前节点x的key，来决定往左还是往右走。
• 分支缺失else：不管条件是否满足，你都直接执行x = x->m_left_child;，这会导致所有情况都往左子树遍历，彻底违背二叉搜索树的插入逻辑。

3. 插入位置判断的致命错误 #

else if (temp->m_right_child->m_key > m_father->m_key) 这行存在两个严重问题：

• 刚创建的temp节点，其m_right_child是nullptr，直接访问temp->m_right_child->m_key会触发空指针访问崩溃；
• 逻辑完全错误，应该比较temp自身的m_key和m_father的m_key，来决定插入到左还是右子节点。

4. 未处理分支覆盖问题 #

最后一行m_father->m_left_child = temp;没有被包裹在else中，导致无论是否进入else if分支，都会覆盖m_father的左子节点，破坏之前的正确赋值。

修复后的代码 #

NOD *INSERT(NOD k) {
    NOD *temp = new NOD(k);
    // 确保新节点的指针成员初始化（如果构造函数未处理）
    temp->m_father = nullptr;
    temp->m_left_child = nullptr;
    temp->m_right_child = nullptr;

    NOD *m_father = nullptr;
    NOD *x = root;

    // 遍历找到插入位置的父节点
    while (x != nullptr) {
        m_father = x;
        if (temp->m_key < x->m_key) {
            // 插入值更小，往左子树遍历
            x = x->m_left_child;
        } else {
            // 插入值更大或相等，往右子树遍历（可根据需求调整重复key的处理逻辑）
            x = x->m_right_child;
        }
    }

    temp->m_father = m_father;
    if (m_father == nullptr) {
        // 树为空，新节点作为根
        root = temp;
    } else if (temp->m_key < m_father->m_key) {
        // 插入到左子节点
        m_father->m_left_child = temp;
    } else {
        // 插入到右子节点
        m_father->m_right_child = temp;
    }

    return temp; // 返回插入的节点，而非0，更符合函数设计逻辑
}

额外调试与编码建议 #

• 确保NOD类的构造函数正确初始化m_father、m_left_child、m_right_child为nullptr，避免未初始化的野指针；
• 处理key相等的情况：如果不允许重复节点，可以在循环中判断并直接返回，或者根据业务需求决定插入位置；
• 调试时可以在循环、空树判断等关键位置添加断点，观察m_father、x、temp的指针值和key值，更直观地定位逻辑错误。

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