Drzewo BST - błąd przy wypisywaniu pustego wskaźnika? (funkcja delete)

0

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);
	}
}
1

Chyba jakoś tak:

struct drzewo* usunPrzezScalanie(struct drzewo* node)
{
	struct drzewo* tmp = 0;

	if (!node) return 0;
	
	if (node->right && node->left) { 
		tmp = node->left;
		while (tmp->right != 0) { tmp = tmp->right; }

		tmp->right = node->right;
		if (node->left != tmp) tmp->left = node->left;
	}
	else {
		if (!node->left && node->right) { tmp = node->right; }
		else if (node->left && !node->right) { tmp = node->left; }
	}

	free(node);
	return tmp;
}

i usuwanie:

prev->left = usunPrzezScalanie(prev->left);

1 użytkowników online, w tym zalogowanych: 0, gości: 1