尝试解除分配二进制搜索树时出错(仅适用于基元数据类型)

Question

我正在尝试编写一个BST，它执行常见的操作，插入、删除、搜索和遍历。

我发现的问题是，当创建的树被分配使用非基元数据类型时，它可以完美地工作。例如：用户定义的结构、类和C++stl类(如std::string(

但是当我使用int、double_t、int64_t等等时，它会抛出一个异常。

~BinaryNode()
{
if (left_ != NULL)
Deleting(left_);
if (right_ != NULL)
Deleting(right_);
//The exception occurs here when the primitive data type
//is attempted to be deallocated
}
//Using preorder to delete this tree recursively
void Deleting(BinaryNode<T> *node)
{
if (node == NULL) return;
if (node->left_ != NULL)
delete node->left_;
if (node->right_ != NULL)
delete node->right_;
node->left_ = node->right_ = NULL;
delete node;
}

我做了很多测试，检查节点之间的完整性，这不是问题所在。因为，正如我所说，问题是当析构函数到达它的末端时。

当我使用调试器时，我看到std::string调用了它的析构函数，并且被正确地释放了。但对于原始类型，它抛出了一个类型的异常：

Exception has occurred.
Trace/breakpoint trap

谢谢你。

编辑：

我将其测试为：

int main()
{
BinarySearchTree<uint64_t> bst(
[](const uint64_t &t1, const uint64_t &t2) -> int8_t {
if (t1 == t2) return 0;
if (t1 > t2) return 1;
else return -1;
});
//performance slow down because there are (20000^2)/2 operations
//to do. This is not a Self Balanced tree, so it is expected
//it ends having worst performance than a singly linked list
for (size_t i = 0; i <= 200; i++)
// i <= 20000 causes error
// i <= 200 or i <= 2000 works perfect
{
bst.Insert(i);
std::cout << "i:" << i << std::endl;
}
std::cout << bst.Size() << std::endl;
bst.Clear();//this generates the error. [When i <= 20000]
}

插入的定义

virtual bool Insert(const T &t)
{
if (this->root_ == NULL)
{
this->root_ = new BinaryNode<T>(t);
return true;
}
return Insert(t, this->root_);
}
virtual bool Insert(const T& t, BinaryNode<T> *node)
{
if (this->comparing_(t, node->t_) > 0)
if (node->left_ == NULL)
{
node->left_ = new BinaryNode<T>(t);
this->size_++;
}
else Insert(t, node->left_);
else if (this->comparing_(t, node->t_) < 0)
if (node->right_ == NULL)
{
node->right_ = new BinaryNode<T>(t);
this->size_++;
}
else Insert(t, node->right_);
else return false; //if there is such element
return true; //if it was successfully inserted
}

这是Clear 的定义

virtual void Clear()
{
delete root_;
root_ = NULL;
}

注：comparing_是lambda。

我认为这是一个递归错误

Answer 1

我发现该错误是由于堆栈溢出错误而产生的。为什么？因为调用堆栈添加的调用数量与树不平衡一侧的节点数量一样多。

由于不平衡二进制搜索树的性质，这种情况发生时，递归是有限制的。我尝试在AVLTree中添加20.000和200000个元素，由于采用了自平衡程序，它运行良好，因为它确保了树的高度为O(ln(n((

Answer 2

由于我看不到节点类，因此根据我的理解：不能为int等数据类型指定NULL。