C++实现二叉搜索树(BST)删除全节点时内存未释放问题排查

问题1：重复值节点直接泄漏 #

插入逻辑中，每次循环都会先调用new BSTNode生成新节点，再通过findNode判断是否存在重复值。如果检测到重复值，已分配的新节点不会被插入树中，也不会被手动释放，直接造成内存泄漏，该问题和后续的销毁逻辑无关。

修复方案：将节点创建逻辑移到重复值判断之后，仅确认需要插入时再分配内存：

for (int i = 0; i < nodesAmount; i++) {
    value = rand() % INT_MAX + 1;
    if (!findNode(root, value)) {
        BSTNode* n = new BSTNode(value, "");
        root = (BSTNode*)insertNode(root, n, BST);
    }
}

问题2：递归销毁方法存在未定义行为 #

BSTNode::destroy方法的空指针校验逻辑无效。C++中使用空指针调用非静态成员函数本身属于未定义行为，当节点的左/右子节点为空时，直接调用left->destroy()或right->destroy()会触发未定义行为，递归逻辑无法正常执行完成，导致大量节点未被释放。

修复方案：调整递归逻辑，先判断子节点非空再调用销毁方法：

void BSTNode::destroy(){
    if (left != nullptr) {
        left->destroy();
    }
    if (right != nullptr) {
        right->destroy();
    }
    delete this;
}

同时调用销毁方法前先校验根节点非空：

if (root != nullptr) {
    root->destroy();
    root = nullptr;
}

补充说明 #

第二种基于栈实现的迭代式销毁逻辑本身没有错误，修复上述重复值泄漏的问题后，该方案可以正常释放所有节点内存。

内容的提问来源于stack exchange，提问作者Simone B.