销毁二叉搜索树(BST)时未初始化值错误排查

我在编写二叉搜索树（BST）的销毁函数以自动释放内存，最初尝试多种销毁逻辑时，用Valgrind检测始终存在内存泄漏。添加delete tree->value语句后，内存泄漏问题解决，但出现了条件跳转或移动依赖于未初始化值的错误。

原代码 #

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

// 用户结构体
struct User
{
    string firstname;
    string lastname;
};

// BST结构体，存储User类型数据
struct BST
{
    User* value;
    int key=0;
    BST* leftTree;
    BST* rightTree;
};

// 创建BST（预留后续扩展大小跟踪字段）
BST* createBST(){
    BST* n = nullptr;
    return n;
}

// 判断BST是否为空
bool isEmpty(BST* tree){
    if(tree == nullptr){
        return true;
    }
    return false;
}

// 销毁整个BST
void destroy(BST* tree){
    if (tree != nullptr){
        delete tree->value;
        destroy(tree->leftTree);
        destroy(tree->rightTree);
        delete tree;
    }
}

测试主函数 #

// 测试代码
int main() {
    BST* bst = createBST();
    // 暂未实现插入函数，手动创建节点
    bst = new BST;
    bst->key = 15;
    bst->value = new User{"John","15"};
    bst->leftTree = new BST;
    bst->leftTree->key = 5;
    bst->leftTree->value = new User{"John","15"};
    destroy(bst);
    return 0;
}

Valgrind报错信息 #

==34== Memcheck, a memory error detector
==34== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==34== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==34== Command: student/labo12
==34==
==34== Conditional jump or move depends on uninitialised value(s)
==34==    at 0x400923: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400950: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400950: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400ABD: main (in /task/student/labo12)
==34==
==34== Conditional jump or move depends on uninitialised value(s)
==34==    at 0x400923: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400960: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400950: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400ABD: main (in /task/student/labo12)
==34==
==34== Conditional jump or move depends on uninitialised value(s)
==34==    at 0x400923: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400960: destroy(BST*) (in /task/student/labo12)
==34==    by 0x400ABD: main (in /task/student/labo12)
==34==
==34==
==34== HEAP SUMMARY:
==34==     in use at exit: 0 bytes in 0 blocks
==34==   total heap usage: 8 allocs, 8 frees, 208 bytes allocated
==34==
==34== All heap blocks were freed -- no leaks are possible
==34==
==34== For counts of detected and suppressed errors, rerun with: -v
==34== Use --track-origins=yes to see where uninitialised values come from
==34== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

问题分析与修复 #

问题根源 #

手动创建BST节点时，leftTree和rightTree指针未被初始化，其值为内存中的随机垃圾值。销毁函数递归调用时，会检查这些未初始化的指针是否为nullptr，导致Valgrind检测到“依赖未初始化值”的错误。

修复方案 #

方案1：给BST结构体添加默认初始化

修改BST结构体，让指针成员默认初始化为nullptr，避免手动创建节点时遗漏初始化：

struct BST
{
    User* value = nullptr;
    int key = 0;
    BST* leftTree = nullptr;
    BST* rightTree = nullptr;
};

或者使用显式构造函数：

struct BST
{
    User* value;
    int key;
    BST* leftTree;
    BST* rightTree;

    BST() : value(nullptr), key(0), leftTree(nullptr), rightTree(nullptr) {}
};

方案2：手动创建节点时显式初始化指针

如果不想修改结构体定义，在手动创建节点时，必须显式将所有未使用的指针设为nullptr：

int main() {
    BST* bst = createBST();
    bst = new BST;
    bst->key = 15;
    bst->value = new User{"John","15"};
    bst->leftTree = new BST;
    bst->leftTree->key = 5;
    bst->leftTree->value = new User{"John","15"};
    // 显式初始化未使用的指针
    bst->rightTree = nullptr;
    bst->leftTree->leftTree = nullptr;
    bst->leftTree->rightTree = nullptr;
    destroy(bst);
    return 0;
}

方案3：优化createBST函数

让createBST返回一个已初始化好的节点，避免后续手动初始化的繁琐：

BST* createBST(){
    BST* n = new BST;
    n->value = nullptr;
    n->key = 0;
    n->leftTree = nullptr;
    n->rightTree = nullptr;
    return n;
}

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