C++结构体指针初始化NULL内存读取异常，BST递归插入问题求助

我来帮你梳理下你遇到的问题，你的BST插入逻辑存在几个关键错误，导致程序无法正常进入左递归分支，还出现了指针相关的内存问题。咱们一步步拆解：

问题分析 #

1. 插入逻辑错误：覆盖当前节点而非创建新节点
   看你代码里的这段：

   else {
       ptr->data = word;
       ptr->left = NULL;
       ptr->right = NULL;
       cout << "Inserted!";
   }
   

   当ptr->left为NULL时，你没有创建新的左子节点，反而把当前节点的data给覆盖了！这就导致：

   • 原有节点的数据被丢失
   • 左子节点永远不会被创建，ptr->left始终是NULL（调试器显示的""其实是未初始化内存的垃圾值，不是真正的字符串）

2. 未处理右子树插入逻辑
   你的代码只处理了word < ptr->data的情况，完全没写word > ptr->data的分支，这会导致所有大于当前节点的元素无法插入右子树。

3. 根节点初始化方式错误
   你用了一个带有空字符串的node实例作为根节点，而不是初始化为NULL。这会让第一个插入逻辑进入if (ptr->data == "")分支，虽然能覆盖数据，但后续插入时容易引发指针混乱。另外，如果直接对NULL指针解引用（比如原函数没有检查ptr是否为NULL），就会出现无法读取内存的崩溃。

修正后的代码 #

我给你调整了递归插入函数，修复了这些问题：

#include <iostream>
#include <string>
using namespace std;

struct node {
    string data;
    node *left = NULL;
    node *right = NULL;
};

// 修正后的递归插入函数，返回新的节点指针，支持根节点为NULL的情况
node* Insert_Rec(string word, node* ptr) {
    // 如果当前节点为空，创建新节点作为当前位置的节点
    if (ptr == NULL) {
        node* newNode = new node();
        newNode->data = word;
        cout << "Inserted: " << word << endl;
        return newNode;
    }

    // 插入左子树
    if (word < ptr->data) {
        cout << "Recursing left from " << ptr->data << endl;
        ptr->left = Insert_Rec(word, ptr->left);
    }
    // 插入右子树
    else if (word > ptr->data) {
        cout << "Recursing right from " << ptr->data << endl;
        ptr->right = Insert_Rec(word, ptr->right);
    }
    // 处理重复元素（可选：覆盖或提示）
    else {
        cout << "Overwritten " << ptr->data << " with " << word << endl;
        ptr->data = word;
    }

    return ptr;
}

// 使用示例
int main() {
    node* root = NULL; // 根节点初始化为NULL，这是BST的正确初始状态
    root = Insert_Rec("orange", root);
    root = Insert_Rec("apple", root);
    root = Insert_Rec("pear", root);
    root = Insert_Rec("apricot", root);
    root = Insert_Rec("orange", root); // 测试重复元素

    // 记得后续要释放内存，避免内存泄漏（这里省略了释放逻辑）
    return 0;
}

关键修正点说明 #

• 创建新节点：当需要插入子节点时，用new node()创建新的节点对象，而不是修改当前节点的数据。
• 处理空指针：先检查ptr == NULL，避免解引用空指针导致的内存错误。
• 完整的BST逻辑：补充了右子树插入的分支，符合二叉搜索树的规则。
• 正确的根节点初始化：根节点初始为NULL，插入第一个元素时自动创建根节点。

这样修改后，程序就能正常进入左递归分支，调试器里的ptr->left也会正确显示为NULL或者指向有效的子节点，不会再出现奇怪的""值。

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