C++实现树数据结构替换int为string时触发读取访问违例错误

问题根因 #

1. Tree类未初始化root指针
   你没有为Tree类编写构造函数，创建Tree实例后，root成员是野指针，并非NULL。之所以int类型时未触发崩溃，是因为int是POD类型，野指针访问int成员时可能刚好未触发内存访问违例；而string是类类型，访问node->data时需要调用string的成员函数，野指针会直接触发读取访问违例，你遇到的0x5D地址就是野指针偏移后访问string成员的非法地址。

2. search函数存在未定义行为
   当整个树中找不到目标数据时，search函数没有显式返回值，会返回随机地址，后续add、del、modify函数拿到这个随机地址访问成员时，直接触发内存访问错误。

3. 无空指针校验逻辑
   所有调用search的位置都没有校验返回值是否为NULL，即便search正常返回NULL，后续直接访问p->left、p->parent也会直接崩溃。同时删除根节点时，p->parent为NULL，直接访问q->right也会触发崩溃。

4. 头文件重复#endif
   头文件末尾多写了一个#endif，属于语法冗余。

修复方案 #

1. 新增Tree类构造函数，初始化root为NULL #

在Tree类的public部分添加构造函数：

Tree() : root(NULL) {}

2. 修复search函数的返回值 #

在search函数末尾添加返回NULL的逻辑：

Tre* search(Tre* node, string data)
{
    if (node == NULL)
        return NULL;

    if (node->data == data)
        return node;

    Tre* p = search(node->left, data);
    if (p != NULL) return p;

    Tre* q = search(node->right, data);
    if (q != NULL) return q;

    return NULL; // 新增这行
}

3. 为所有调用search的位置添加空校验 #

比如add函数修改为：

Tre* add(Tre* root, string find, string input)
{
    Tre* p = search(root, find);
    if (p == NULL) {
        cout << "未找到父节点" << endl;
        return root;
    }
    if (p->left == NULL) {
        p->left = new Tre(p, input);
    } else if (p->right == NULL) {
        p->right = new Tre(p, input);
    } else {
        cout << "父节点左右子节点已满，无法添加" << endl;
    }
    return root;
}

del、modify函数同理，先判断search返回的p是否为NULL，删除节点时还要判断p->parent是否为NULL（也就是要删的是根节点的情况），单独处理。

4. 删除头文件末尾多余的#endif #

把头文件最后重复的那个#endif删掉即可。

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