Napisałem algorytm który m. in. dodaje i usuwana elementy z drzewa BST.
Wszystko ładnie działa, tylko mam problem z zabezpieczeniem przed podawaniem złych danych wejściowych. Chodzi dokładnie o funkcję usuwania pojedynczego elementu. Jak podam do usunięcia element o kluczu którego nie ma w drzewie to wyskakuje segmentation fault, a chce żeby wyskoczył komunikat że podano złe dane. Najprawdopodobniej program wchodzi w nieskończoną pętlę while po wejściu w funkcję usuwanie(). Proszę o pomoc gdyż nie wiem już jak to zrobić bo moje próby okazały się nieskuteczne :(
#include <iostream>
#include <stdio.h>
using namespace std;
struct drzewo
{
int index;
int klucz;
drzewo *lewy,*prawy;
drzewo *rodzic;
};
drzewo *root;
int z,usuwana_wartosc;
//Dodawanie elementu do drzewa BST
void dodawanie(int x)
{
int i=1;
drzewo *nowy_element;
nowy_element = new drzewo;
nowy_element->klucz=x;
nowy_element->lewy=NULL;
nowy_element->prawy=NULL;
if(!root)
{
root=nowy_element;
nowy_element->index=1;
nowy_element->rodzic=NULL;
return;
}
drzewo *tym=root;
while ( ( (tym->klucz>x) && (tym->lewy) ) || ( (tym->klucz<x) && (tym->prawy) ) )
{
if (tym->klucz>x)
{
tym=tym->lewy;
i=2*i;
}
else
{
tym=tym->prawy;
i=2*i+1;
}
}
if (tym->klucz>x)
{
nowy_element->rodzic=tym;
tym->lewy=nowy_element;
i=2*i;
}
else
{
nowy_element->rodzic=tym;
tym->prawy=nowy_element;
i=2*i+1;
}
nowy_element->index=i;
}
//Usuwanie elementu o kluczu podanym jako parametr
void usuwanie(int x) //Do dopracowania index
{
int z=0;
drzewo *tym=root, *tym2;
while (tym->klucz!=x)
{
if (tym->klucz<x)
{
tym=tym->prawy;
z=1;
}
else
{
tym=tym->lewy;
z=2;
}
}
if ((!tym->lewy) && (!tym->prawy))
{
switch (z)
{
case 0:
delete tym;
tym=NULL;
root=NULL;
return;
case 1:
tym->rodzic->prawy=NULL;
delete tym;
tym=NULL;
return;
case 2:
tym->rodzic->lewy=NULL;
delete tym;
tym=NULL;
return;
}
}
else if ((tym->lewy) && (!tym->prawy))
{
switch (z)
{
case 0:
tym->lewy->rodzic=NULL;
root=tym->lewy;
delete tym;
tym=NULL;
return;
case 1:
tym->lewy->rodzic=tym->rodzic;
tym->rodzic->prawy=tym->lewy;
delete tym;
tym=NULL;
return;
case 2:
tym->lewy->rodzic=tym->rodzic;
tym->rodzic->lewy=tym->lewy;
delete tym;
tym=NULL;
return;
}
}
else if ((!tym->lewy) && (tym->prawy))
{
switch (z)
{
case 0:
tym->prawy->rodzic=NULL;
root=tym->prawy;
delete tym;
tym=NULL;
return;
case 1:
tym->prawy->rodzic=tym->rodzic;
tym->rodzic->prawy=tym->prawy;
delete tym;
tym=NULL;
return;
case 2:
tym->prawy->rodzic=tym->rodzic;
tym->rodzic->lewy=tym->prawy;
delete tym;
tym=NULL;
return;
}
}
else if ((tym->lewy) && (tym->prawy))
{
tym2=tym;
tym2=tym2->prawy;
while (tym2->lewy!=NULL)
{
tym2=tym2->lewy;
}
usuwana_wartosc=tym2->klucz;
usuwanie(tym2->klucz);
tym->klucz=usuwana_wartosc;
return;
}
}
int main()
{
int n=0,n2=0;
printf("Podaj ilość elementów które chcesz wprowadzić do drzewa: ");
scanf("%d",&n);
int *tab = new int[n];
for (int i=0;i<n;i++)
{
scanf("%d",&tab[i]);
dodawanie(tab[i]);
}
printf("Podaj ile elementów chcesz usunąć: ");
scanf("%d",&n2);
int *tab2 = new int[n2];
if (n2<=n)
{
for (int i=0;i<n2;i++)
{
scanf("%d",&tab2[i]); // TUTAJ TRZEBA ZABEZPIECZYĆ PRZED PODAWANIEM ELEMENTU KTÓREGO NIE MA W DRZZEWIE
usuwanie(tab2[i]);
}
}
else printf("Nie ma tylu elemenetów w drzewie\n");
delete [] tab;
delete [] tab2;
return 0;
}