AVL树_clear方法无法删除元素及遗留空链接节点问题排查

核心问题分析 #

• 传值参数导致指针未置空：你的_clear函数中，vertex是按值传递的指针。最后一行vertex = nullptr只是修改了函数内部的局部指针副本，完全不会改变原树中父节点的_left/_right指针，或是AVL树类中根节点指针的指向。这些原指针会变成野指针，看起来像是“未被删除的空链接节点”，但实际上对应的内存已经被delete释放了，只是指针本身没被置空。
• 析构函数未触发清理逻辑：如果AVL_Tree类的析构函数没有主动调用_clear来清理根节点，那么整个树的节点都不会被触发释放，自然会残留未删除的节点。
• 清理范围不全：检查你调用_clear时传入的节点是否是树的根节点。如果只清理了子树而没处理根节点，根节点及其关联的部分节点会残留。

修正方案 #

1. 修改_clear为引用传递指针
   把参数改成指针引用，这样修改vertex时会同步更新原树中的指针，避免野指针问题：

   void AVL_Tree<T>::_clear(Node<T>*& vertex) {
       if(vertex != nullptr) {
           _clear(vertex->_left);
           _clear(vertex->_right);
           delete vertex;
           vertex = nullptr; // 现在会同步置空原树中的对应指针
       }
   }
   

2. 实现AVL树的析构函数
   在AVL_Tree类中添加析构函数，主动调用_clear清理根节点：

   class AVL_Tree {
       // ... 其他成员 ...
       Node<T>* root; // 假设类中有根节点指针成员
   public:
       ~AVL_Tree() {
           _clear(root);
       }
   };
   

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