Ошибка памяти C ++ BST — что не так с моим удалением?

Проблема, с которой я столкнулся, состоит в том, что мое дерево может только успешно удалить узел ОДИН раз. Когда я попытаюсь удалить его больше, произойдет сбой с ошибкой сегментации (ошибка дампа). Я не могу точно указать точное место, где это происходит, но это ДОЛЖНО быть что-то, что я делаю неправильно с распределением и освобождением памяти, я просто не вижу этого.

Вот моя вставка, удаление, удаление помощника и листа (потому что это называется внутри удаления):

вставить:

/*********************************************************
Function: insert
Arguments: const T &x (a T variable)
Returns: void
Notes: If the tree is empty, the function will set the node
as the root. Otherwise, it will look for the appropiate
place (in terms of a BST) to place it as long as its data
is not already existent inside the tree.
*********************************************************/
template<class T> void binSTree<T>::insert(const T &x)
{
BinTreeNode *newnode, *current, *parentOfCurrent; /* newnode will be the inserted node, current and parentOfCurrent will be traversing the while loop to find an appropiate space to insert */
newnode = new BinTreeNode; /* allocates storage space */
newnode->info = x; /* sets newnode's data equal to x */
newnode->left = newnode->right = NULL; /* sets newnode's left and right children equal to NULL */

if (root == NULL)   { /* if the tree is empty, it will place newnode on the root */
root = newnode;
cout << "added to root\n";
return;         }
current = root; /* sets current at the root */
while(current != NULL)  { /* while current is not NULL, it will search for a place to insert the new node */
parentOfCurrent = current; /* sets the parent equal to current */
if(current->info == x) /* if the variable is found inside the tree, then it will error and exit */
{
cout << x << " already exists in tree. Duplicates not allowed!\n";
return;
}
else if(current->info > x) /* otherwise, if the variable is less than the data on the tree currently, it will move left */
current = current->left;
else                       /* otherwise, if the variable is greater than the data on the tree currently, it will move right */          current = current->right;
}
/* the new node is placed where current would be in */
if (parentOfCurrent->info > x)
parentOfCurrent->left = newnode;
else
parentOfCurrent->right = newnode;
}

удалить и PrivRemove:

template <class T> bool binSTree<T>::remove(const T &x)
{
BinTreeNode *current, *parentOfCurrent; /* current for tranversing the tree in the while loop and parentofCurrent to help */
bool found = false; /* the booleans that is to be returned */
if (root == NULL)   { /* Checks if the tree is empty, if it is, it returns found (false) and exits */
return found;
}
current = root; /* sets current equal to root */
while(current != NULL) /* loops repeats until current is equal to NULL */
{
if(current->info == x)  { /* if the current data from the tree is equal tox, then it breaks the loop and sets found equal to true */
found = true;
break;
}
else    { /* otherwise, it will search for the next place to go in the tree */
parentOfCurrent = current; /* parentOfCurrent is set to current before current is set to one of its children */
if(current->info > x) /* if x is less than the data on current, then it will move left */
current = current->left;
else   /* if x is greater than the data on current, then it will move right */
current = current->right;
}
}
if(found == true) { /* if it was found, it will pass current via the parent to the private remove function */
if (current == root)
privRemove(root);
else if (parentOfCurrent->info > x) {  /* if current is to the left of the parent */
found = leaf( parentOfCurrent->left );
if(found == true)
privRemove(parentOfCurrent->left);
}
else {  /* if current is to the right of the parent */
found = leaf( parentOfCurrent->left );
if(found == true)
privRemove(parentOfCurrent->right);
}
}
return found;
}
/*********************************************************
Function: privRemove
Arguments: BinTreeNode* &node (the node that is to be deleted)
Returns: void
Notes: This private remove function will take in the node that
is provided by the public remove function, and, after ensuring
that the node passed is not NULL, then it will delete it.
*********************************************************/
template <class T> void binSTree<T>::privRemove(BinTreeNode* &node)
{
BinTreeNode *temp; /* initializes temp in order to hold the information of node */
if(root != NULL )  /* if the node is not NULL */
{
temp = node;
delete node;
node = temp;
}
}

лист:

/*********************************************************
Function: leaf
Arguments: BinTreeNode* node
Returns: boolean
Notes: This function will check if the node in the argument
is a leaf by checking if both of its children are NULL. If
they are, it returns true. Otherwise, it returns false.
*********************************************************/
template <class T> bool binSTree<T>::leaf(BinTreeNode* node) const
{
bool isLEaf = false; /* the boolean variable it is to return */
if(node->left == NULL && node->right == NULL) /* checks if the node has no children */
isLEaf = true;  /* if it does, it sets isLEaf equal to true */
return isLEaf;  /* after going through the if statement, it returns the variable isLeaf */
}

Следует отметить, что мои узлы являются структурами, объявленными в заголовке класса, и что переменная root объявлена ​​как защищенная переменная в форме BinTreeNode * root; он инициализируется как NULL внутри конструктора binSTree. Кроме того, мне разрешено удалять только листья.

0

Решение

то, что мне кажется, что вы делаете неправильно, находится внутри метода privRemove …
Представьте, что вы пытались удалить узел, и на этом узле вызывается privRemove.

с:

delete node;

Вы освобождаете узел памяти, на который указывает.

затем вы переназначаете узел на значение, которое он имел ранее с:

node=temp;

так что теперь он указывает на то же место, что и раньше (внутри и снаружи вашей функции, потому что вы передали ее по ссылке).

Теперь при следующем удалении вы в конечном итоге встретите тот же самый узел и проверите, является ли он NULL, но это не так, поскольку вы дали ему значение, поэтому он указывает на память, которая была до него (node ​​= temp), поэтому узел указывает на где-то в памяти не NULL, так что вы будете думать, что это законный узел, но это не так, это указывает на то, что память уже освобождена. И когда вы вызываете метод для этого … bhumm!

1

Другие решения

Других решений пока нет …