У меня трудности с удалением элемента из BST. Этот код основан на алгоритме из книги Кормена. Вот две функции, необходимые для удаления элемента:
el *TreeSuccessor(el *x)
{
el *y;
if (x->right != NULL){
return TreeMinimum(x->right);
}
y= x->p;
while (y != NULL && x == y->right){
x = y;
y = y->p;
}
return y;
}void TreeDelete (el* &root, el *z, el* &y)
{
el *x;
if (z->left == NULL || z->right == NULL){
y=z;
}
else{
y=TreeSuccessor(z);
}
if(y->left != NULL){
x = y->left;
}
else{
x = y->right;
}
if (x!=NULL){
x->p = y->p;
}
if (y->p == NULL){
root=x;
}
else if (y == y->p->left){
y->p->left = x;
}
else{
y->p->right = x;
}if (y!=z){
z->indeks = y->indeks;
strcpy(z->name,y->name);
strcpy(z->surname,y->surname);
}
}
А вот код, отвечающий за вызов функции в int main()
:
for (int i=0; i<n; i++)
{
File>>keyToSearch;
searchedLeave=TreeSearch(root,keyToSearch);
TreeDelete(root,searchedLeave,leaveToDelete);
delete leaveToDelete;
}
Вот полная программа http://pastebin.com/FgvWPzm9
Программа вылетает при удалении.
Задача ещё не решена.
Других решений пока нет …