二叉搜索树内存泄漏及新树残留子节点问题排查

问题现象 #

• 内存泄漏：调用17次Insert函数后，Valgrind检测到1496字节内存泄漏，且泄漏均由Insert操作导致
• 节点残留：销毁原有树并重建新树后，根节点仍存在悬空子节点，且代码未处理子节点与根节点相同的情况

相关代码片段 #

Insert与Delete系列函数 #

template <typename SomeType>
void BSTree<SomeType>::Insert(BSTreeNode<SomeType>*& ptr, SomeType item) {
    if (rootPtr == NULL) {
        rootPtr = new BSTreeNode<SomeType>;
        rootPtr->data = item;
        return;
    }
    if (ptr->data < item) {
        if (ptr->rightPtr == NULL) {
            ptr->rightPtr = new BSTreeNode<SomeType>;
            ptr->rightPtr->data = item;
            return;
        } else {
            Insert(ptr->rightPtr, item);
        }
    } else if (ptr->data > item) {
        if (ptr->leftPtr == NULL) {
            ptr->leftPtr = new BSTreeNode<SomeType>;
            ptr->leftPtr->data = item;
            return;
        } else {
            Insert(ptr->leftPtr, item);
        }
    } else if (ptr->data == item) {
        throw FoundInBSTree();
    }
}

template <typename SomeType>
void BSTree<SomeType>::Delete(BSTreeNode<SomeType>*& treePtr, SomeType& item) {
    if (treePtr == NULL)
        throw NotFoundBSTree();
    else if (treePtr->data > item)
        Delete(treePtr->leftPtr, item);
    else if (treePtr->data < item)
        Delete(treePtr->rightPtr, item);
    else
        DeleteNode(treePtr);
}

template <typename SomeType>
void BSTree<SomeType>::DeleteNode(BSTreeNode<SomeType>*& treePtr) {
    if (treePtr == NULL) {
        delete treePtr;
        return;
    }
    if (treePtr->leftPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->rightPtr;
        delete tmp;
        return;
    } else if (treePtr->rightPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->leftPtr;
        delete tmp;
        return;
    } else {
        treePtr->data = GetPredecessor(treePtr->leftPtr);
        Delete(treePtr->leftPtr, treePtr->data);
    }
    if (treePtr == NULL) {
        delete treePtr;
        return;
    }
}

补充：Destroy函数与析构函数 #

template <typename SomeType>
void BSTree<SomeType>::Destroy(BSTreeNode<SomeType>*& ptr){
    if(ptr == NULL) return;
    Destroy(ptr->leftPtr);
    delete ptr->leftPtr;
    Destroy(ptr->rightPtr);
    delete ptr->rightPtr;
    ptr = NULL;
}

template <typename SomeType>
BSTree<SomeType>::~BSTree(){
    Destroy(rootPtr);
    delete rootPtr;
}

完整最小可复现示例（MRE） #

template <typename SomeType>
SomeType BSTree<SomeType>::GetPredecessor(BSTreeNode<SomeType>* treePtr) const{
    BSTreeNode<SomeType>* tmp = treePtr;
    while(tmp->rightPtr != NULL){
        tmp = tmp->rightPtr;
    }
    return tmp->data;
}

template <typename SomeType>
BSTree<SomeType>::BSTree(){
    rootPtr = NULL;
}

template <typename SomeType>
BSTree<SomeType>::~BSTree(){
    Destroy(rootPtr);
    delete rootPtr;
}
  
template <typename SomeType>
void BSTree<SomeType>::InsertItem(SomeType item){
    Insert(rootPtr, item);
}
  
template <typename SomeType>
SomeType BSTree<SomeType>::DeleteItem(SomeType item){
    Delete(rootPtr, item);
    return item;
}

// 以下代码不可修改
template <typename SomeType>
struct BSTreeNode{
    SomeType data;
    BSTreeNode<SomeType>* leftPtr;
    BSTreeNode<SomeType>* rightPtr;
};

template <typename SomeType>
class BSTree{
    private:
        BSTreeNode<SomeType> rootPtr;
        void Delete(BSTreeNode<SomeType>*& treePtr, SomeType& item);
        void DeleteNode(BSTreeNode<SomeType>*& treePtr);
        void Insert(BSTreeNode<SomeType>*& ptr, SomeType item);
        void Destroy(BSTreeNode<SomeType>*& ptr);
        SomeType GetPredecessor(BSTreeNode<SomeType>* treePtr) const;
    public:
        BSTree();
        ~BSTree();
        void InsertItem(SomeType item);     
        SomeType DeleteItem(SomeType item);
};

int main(){
    BSTree<int>* TestModule = new BSTree<int>;
    TestModule->InsertItem(1);
    TestModule->InsertItem(2);
    TestModule->InsertItem(4);
    TestModule->InsertItem(3);
    TestModule->DeleteItem(2);
    delete TestModule;
    TestModule = NULL;
    TestModule = new BSTree<int>;
    TestModule->InsertItem(1); // 此处根节点左指针残留值4
}

问题根源分析 #

1. 致命类型错误：BST类的rootPtr被定义为BSTreeNode<SomeType>对象，但所有代码逻辑都将其当作指针使用（如构造函数赋值NULL、Insert中rootPtr = new BSTreeNode<SomeType>），这会导致未定义行为，直接引发内存泄漏和节点残留。
2. Destroy函数逻辑错误：
   • 递归销毁左右子节点后，未删除当前节点ptr，导致根节点及中间节点内存未释放
   • 在Destroy(ptr->leftPtr)后执行delete ptr->leftPtr，此时ptr->leftPtr已被递归调用置为NULL，属于无效操作
3. 析构函数冗余操作：Destroy已负责处理节点销毁，额外执行delete rootPtr（且rootPtr是对象不是指针）会导致错误或内存释放混乱
4. Insert函数逻辑缺陷：初始判断直接操作rootPtr而非传入的ptr参数，导致递归逻辑不一致，且新创建的节点未初始化leftPtr和rightPtr，可能产生野指针

修复方案 #

1. 修正rootPtr类型（核心修复） #

将BST类中private成员的BSTreeNode<SomeType> rootPtr;修改为：

BSTreeNode<SomeType>* rootPtr;

2. 修复Destroy函数 #

改为正确的后序遍历销毁逻辑：

template <typename SomeType>
void BSTree<SomeType>::Destroy(BSTreeNode<SomeType>*& ptr){
    if(ptr == NULL) return;
    // 先递归销毁左右子树
    Destroy(ptr->leftPtr);
    Destroy(ptr->rightPtr);
    // 删除当前节点并置空指针
    delete ptr;
    ptr = NULL;
}

3. 修复析构函数 #

移除冗余的delete rootPtr：

template <typename SomeType>
BSTree<SomeType>::~BSTree(){
    Destroy(rootPtr);
}

4. 修复Insert函数 #

调整初始判断逻辑，统一使用传入的ptr参数，并初始化新节点的左右指针：

template <typename SomeType>
void BSTree<SomeType>::Insert(BSTreeNode<SomeType>*& ptr, SomeType item) {
    if (ptr == NULL) {
        ptr = new BSTreeNode<SomeType>;
        ptr->data = item;
        ptr->leftPtr = NULL;
        ptr->rightPtr = NULL;
        return;
    }
    if (ptr->data < item) {
        Insert(ptr->rightPtr, item);
    } else if (ptr->data > item) {
        Insert(ptr->leftPtr, item);
    } else {
        throw FoundInBSTree();
    }
}

5. 简化DeleteNode函数 #

移除冗余的空指针判断：

template <typename SomeType>
void BSTree<SomeType>::DeleteNode(BSTreeNode<SomeType>*& treePtr) {
    if (treePtr->leftPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->rightPtr;
        delete tmp;
    } else if (treePtr->rightPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->leftPtr;
        delete tmp;
    } else {
        treePtr->data = GetPredecessor(treePtr->leftPtr);
        Delete(treePtr->leftPtr, treePtr->data);
    }
}

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