Witajcie. Krótko zwięźle i na temat. Mam drzewo BST usuwam z niego jakikolwiek element, w tym przypadku element 13 (największy). Wszystko działa poprawnie, ale gdy po usunięciu jakiejkolwiek wartości chcę wypisać elementy drzewa ponownie za pomocą funkcji wypisz wyskakuje błąd. Siedzę od kilku godzin i siwieje. Funkcje działają poprawnie, gdyż jeśli dam printa do tej wartości np.
printf("%d",root->right->right->key);
to element faktycznie jest usunięty (wyskakuje dowolna liczba z pamięci). Natomiast przy funkcji wypisującej wywala błąd, pomimo że mam w tej rekurencyjnej funkcji warunek, że jeżeli jest pusty, żeby nie wypisywało. Ktoś ma jakiś pomysł? Dla przejrzystości dodam zdjęcie rysunku drzewa, jeśli ktoś miałby ochotę sobie przeanalizować.
#include <stdio.h>
#include <stdlib.h>
struct drzewo{
int key;
struct drzewo *left, *right;
};
void dodaj(int el);
void wypisz(struct drzewo *glowa);
void znajdzIUsun(int el);
void znajdzIUsun(int el);
void usunPrzezScalanie(struct drzewo *node);
struct drzewo *root =NULL;
int main(void){
dodaj(5);
dodaj(7);
dodaj(1);
dodaj(3);
dodaj(2);
dodaj(13);
dodaj(6);
wypisz(root);
puts("");
znajdzIUsun(13);
//wypisz(root); // tutaj wystapi blad po usunieciu wartosci 13 z drzewa!
printf("%d",root->right->right->key);
return 0;
}
void dodaj(int el){
if (root==NULL){
root = (struct drzewo*) malloc(sizeof(struct drzewo));
root->key=el;
root->left=NULL;
root->right=NULL;
return;
}
struct drzewo *pom, *prev;
pom=root;
while(pom!=0){
prev = pom;
if(el < pom->key)
pom=pom->left;
else
pom=pom->right;
}
if(el < prev->key){
prev->left = (struct drzewo*) malloc(sizeof(struct drzewo));
prev->left->key = el;
prev->left->left=NULL;
prev->left->right=NULL;
}
else if(el > prev->key){
prev->right = (struct drzewo*) malloc(sizeof(struct drzewo));
prev->right->key = el;
prev->right->left=NULL;
prev->right->right=NULL;
}
}
void wypisz(struct drzewo *glowa){
if(glowa==NULL)
return;
wypisz(glowa->left);
printf("%d ",glowa->key);
wypisz(glowa->right);
}
void znajdzIUsun(int el){
struct drzewo *node = root;
struct drzewo *prev = 0;
while(node!=0){
if(node->key==el)
break;
prev=node;
if(el<node->key)
node=node->left;
else
node=node->right;
}
if(node!=0 && node->key==el)
if(node==root)
usunPrzezScalanie(root);
else if(prev->left == node)
usunPrzezScalanie(prev->left);
else
usunPrzezScalanie(prev->right);
else if(root!=0)
printf("%d nie ma w drzewie\n",el);
else
printf("Drzewo puste");
}
void usunPrzezScalanie(struct drzewo *node){
struct drzewo *tmp = node;
if(node!=0){
if(!node->right)
node=node->left;
else if(node->left ==0)
node=node->right;
else{
tmp = node->left;
while(tmp->right !=0)
tmp=tmp->right;
tmp->right = node->right;
tmp=node;
node = node->left;
}
free(tmp);
}
}