-1
我在從BST中刪除節點時遇到問題,我似乎無法找到導致seg故障的罪魁禍首。我測試過的BST的其他部分都能順利運行。我也嘗試刪除具有不同條件的節點,但它們都是相同的結果。刪除二進制搜索樹(BST)中的節點正在導致seg故障
template <typename object>
bool BST<object>::remove(object& data)
{
if (nodes == 0)
{
return false;
}
else
{
return remove(root_, data);
}
}
template <typename object>
bool BST<object>::remove(node<object>* current_node_, object& data)
{
if (current_node_ == NULL)
{
return false;
}
int relation = compare(data, current_node_->get_data());
//if you need to keep searching right
if (relation > 0)
{
remove(current_node_->get_right(), data);
}
else if (relation < 0)
{
remove(current_node_->get_left(), data);
}
else
{
//LEAF CASE
if (current_node_->is_leaf())
{
//root case
if (compare(root_->get_data(), data) == 0)
{
root_ = NULL;
}
else
{
if (current_node_->is_right_child())
{
current_node_->get_parent()->set_right(NULL);
}
else
{
current_node_->get_parent()->set_left(NULL);
}
}
//release from memory
delete current_node_;
nodes--;
}
//ONE CHILD CASE
else if (current_node_->has_one_child())
{
//root node
if (compare(root_->get_data(), data) == 0)
{
if (current_node_->get_right() != NULL)
{
current_node_->get_right()->set_parent(NULL);
root_ = current_node_->get_right();
}
else
{
current_node_->get_left()->set_parent(NULL);
root_ = current_node_->get_left();
}
}
//node with right child
else if(current_node_->get_right() != NULL)
{
current_node_->get_right()->set_parent(current_node_->get_parent());
if (current_node_->is_right_child())
{
current_node_->get_parent()->set_right(current_node_->get_right());
}
else
{
current_node_->get_parent()->set_left(current_node_->get_right());
}
}
//node with left child
else
{
current_node_->get_left()->set_parent(current_node_->get_parent());
if (current_node_->is_right_child())
{
current_node_->get_parent()->set_right(current_node_->get_left());
}
else
{
current_node_->get_parent()->set_left(current_node_->get_left());
}
}
//release from memory
delete current_node_;
nodes--;
}
//TWO CHILDREN CASE
else
{
node<object>* temp_node_ = find_min(current_node_->get_right());
object* temp_object_ = new object(temp_node_->get_data());
remove(temp_node_, temp_node_->get_data());
current_node_->set_data(*temp_object_);
}
return true;
}
return false;
}
template <typename object>
node<object>* BST<object>::find_min(node<object>* current_node_)
{
if(current_node_->get_left() != NULL)
{
find_min(current_node_->get_left());
}
else
{
return current_node_;
}
}
解決此類問題的正確工具是您的調試器。在*堆棧溢出問題之前,您應該逐行執行您的代碼。如需更多幫助,請閱讀[如何調試小程序(由Eric Lippert撰寫)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/)。至少,您應該\編輯您的問題,以包含一個[最小,完整和可驗證](http://stackoverflow.com/help/mcve)示例,該示例再現了您的問題,以及您在調試器。 –
遞歸調用'remove'函數,但不返回遞歸調用返回的內容。 –