witam,mam za zadanie stworzenie slownika polsko-angielskiego i angielsko-polskiego wykorzystując drzewo avl,.Pierwszy etap jaki zaczołem to stworzenie drzewa avl na którym umieszczoną są liczby i sprawdzenie działania .Dodawanie i wypisywanie działa poprawnie,natomiast napotkałem problem w usuwaniu ,nie mogę znależć błedu który popełniłem,ktoś ma pomysł?
#include <iostream>
#include <fstream>
using namespace std;
typedef struct wierzcholek
{
int x;
int wysokosc;
wierzcholek *lewy;
wierzcholek *prawy;
} wierzcholek;
int maks(int a, int b)
{
if(a>b)
return a;
return b;
}
int wysokosc(wierzcholek *N)
{
if(N==NULL)
return 0;
return N->wysokosc;
}
wierzcholek *nowy(int liczba)
{
wierzcholek *w = new wierzcholek();
w->x = liczba;
w->lewy = NULL;
w->prawy = NULL;
w->wysokosc = 1;
return (w);
}
//ROTACJE
wierzcholek *Rotacja_w_prawo(wierzcholek *y)
{
wierzcholek *x = y->lewy;
wierzcholek *temp = x->prawy;
//rotacja
x->prawy = y;
y->lewy = temp;
//wysokosci
y->wysokosc = maks(wysokosc(y->lewy), wysokosc(y->prawy))+1;
x->wysokosc = maks(wysokosc(x->lewy),wysokosc(x->prawy))+1;
return x;
}
wierzcholek *Rotacja_w_lewo(wierzcholek *x)
{
wierzcholek *y = x->prawy;
wierzcholek *temp = y->lewy;
//rotacja
y->lewy = x;
x->prawy = temp;
//wysokosci
x->wysokosc = maks(wysokosc(x->lewy), wysokosc(x->prawy))+1;
y->wysokosc = maks(wysokosc(y->lewy), wysokosc(y->prawy))+1;
return y;
}
int jaki_Balans(wierzcholek *N)
{
if(N==NULL)
return 0;
return wysokosc(N->lewy) - wysokosc(N->prawy);
}
wierzcholek *INSERT(wierzcholek *w, int liczba)
{
//Normalna rotacja BST
if(w==NULL)
return(nowy(liczba));
if(liczba < w->x)
w->lewy = INSERT(w->lewy,liczba);
else
w->prawy = INSERT(w->prawy,liczba);
//aktualizacja wysokosci na poziomie tego wierzcholka
w->wysokosc = maks(wysokosc(w->lewy), wysokosc(w->prawy))+1;
//pobranie balansu w wysokosci
int balans = jaki_Balans(w);
//gdy nie ma zachowanego odpowiedniego balansu
//mamy 4 mozliwosci
//Rotacja lewa
if(balans > 1 && liczba < w->lewy->x)
return Rotacja_w_prawo(w);
//Rotacja prawa
if(balans < -1 && liczba > w->prawy->x)
return Rotacja_w_lewo(w);
//Rotacja lewa prawa
if(balans > 1 && liczba > w->lewy->x)
{
w->lewy = Rotacja_w_lewo(w->lewy);
return Rotacja_w_prawo(w);
}
//Rotacja prawa lewa
if(balans < -1 && liczba < w->prawy->x)
{
w->prawy = Rotacja_w_prawo(w->prawy);
return Rotacja_w_lewo(w);
}
return w;
}
//zwroc minimalna wartosc w drzewie AVL. trzeba przejrzec cale drzewo
wierzcholek *najmniejszy(wierzcholek *w)
{
wierzcholek *obecny = w;
while(obecny->lewy != NULL)
obecny = obecny->lewy;
return obecny;
}
wierzcholek *usun (wierzcholek *przetwarzany,int _dane)
{
if(przetwarzany==NULL)
{
return przetwarzany;
}
else if(przetwarzany->x>_dane)
{
przetwarzany->lewy =usun(przetwarzany->lewy,_dane);
}
else if(przetwarzany->x<_dane)
{
przetwarzany->prawy =usun(przetwarzany->prawy,_dane);
}
else if(przetwarzany->x==_dane)
{
wierzcholek *temp =NULL;
if((przetwarzany->lewy == NULL )&&(przetwarzany->prawy==NULL))
{
delete przetwarzany;
return NULL;
}
else if(przetwarzany->lewy == NULL )
{
temp = przetwarzany->prawy;
delete przetwarzany;
return temp;
}
else if(przetwarzany->prawy == NULL )
{
delete przetwarzany;
return temp;
}
else
{
temp=przetwarzany;
temp= temp->prawy;
wierzcholek *pom=przetwarzany;
while (temp->lewy!= NULL)
{
pom = temp;
temp=temp->lewy;
}
if(temp==przetwarzany->prawy)
{
temp->lewy=przetwarzany->lewy;
delete przetwarzany;
return temp;
}
else
{
pom->lewy=temp->prawy;
temp->prawy=przetwarzany->prawy;
temp->lewy=przetwarzany->lewy;
delete przetwarzany;
return temp;
}
}
}
przetwarzany->wysokosc=max(wysokosc(przetwarzany->prawy),wysokosc(przetwarzany->lewy))+1;
int bf=jaki_Balans(przetwarzany);
if(bf > 1 && jaki_Balans(przetwarzany->lewy)>=0)
return Rotacja_w_prawo(przetwarzany);
if(bf < -1 && jaki_Balans(przetwarzany->prawy)<=-1)
return Rotacja_w_lewo(przetwarzany);
if(bf < -1 && jaki_Balans(przetwarzany->lewy)<=0)
{
przetwarzany->prawy = Rotacja_w_prawo(przetwarzany->prawy);
return Rotacja_w_lewo(przetwarzany);
}
if(bf > 1 &&jaki_Balans(przetwarzany->prawy)>=-1)
{
przetwarzany->lewy = Rotacja_w_lewo(przetwarzany->lewy);
return Rotacja_w_prawo(przetwarzany);
}
return przetwarzany;
}
//wyswietlanie
void przegladanie_KLP(wierzcholek *korzen)
{
if(korzen != NULL)
{
cout<<korzen->x<<" ";
przegladanie_KLP(korzen->lewy);
przegladanie_KLP(korzen->prawy);
}
}
int main()
{
wierzcholek *korzen = NULL;
ifstream we("in.txt");
int i;
while(we>>i)
{
korzen = INSERT(korzen, i);
}
przegladanie_KLP(korzen);
return 0;
}
plik in.txt zawiera przypadkowe liczby
np.in.txt zawiera:9 4 10 3 7 11 6 8 5
przegladam drzewo 9 6 4 3 5 7 8 10 11
usuwam(6)
przegladane drzewo powinno wygladać: 9 5 4 3 7 8 10 11
a u mnie jest: 9 7 4 3 5 8 10 11
usuwam(5)
powinno być: 9 4 3 7 8 10 11
a u mnie jest: 9 7 4 3 8 10 11