Witam,
Mam do napisania mały projekcik z obsługą drzewa przeszukiwań binarnych, funkcje dodawania, generowania, wyszukiwania i wyświetlania nie stanowiły zbyt dużego problemu. Nie wiem jednak zupełnie jak zabrać się za poniższy problem:
usunięcie z drzewa elementu o zadanej przez użytkownika wartości składowej kluczowej (wraz z obsługą przypadku, w którym brak w drzewie węzła o zadanej wartości składowej kluczowej; w przypadku usuwania węzła stopnia 2-go należy zaimplementować obie alternatywne wersje postępowania, odwołujące się do poprzednika albo następnika usuwanego węzła)
Poniżej zamieszczę swój kod, napisany w bardzo uproszczony sposób na funkcjach. Nazwy zmiennych troszku pomieszane pol-ang ze względu na to, że skrótowce, których używałem mogły być mało przejrzyste.
Bardziej od gotowego rozwiązania interesuje mnie np schemat rozwiązania problemu tj zasady które trzeba zaimplementować.
struct drzewo{
int key;
drzewo *left, *right;
};
void printinorder(drzewo *d)
{
drzewo *kopia = d;
if(!kopia) //gdy drzewo puste
{
cout<<"Nie ma nic!";
system("PAUSE");
return;
}
else
{
if(kopia->left) printinorder(kopia->left);
cout<<" "<<kopia->key<<" ";
if(kopia->right) printinorder(kopia->right);
//cout<<endl;
}
}
int wyszukiwanie(drzewo *d, int klucz)
{
drzewo *kopia = d;
while(kopia)
{
if(kopia->key == klucz) return 1;
if(klucz > kopia->key) kopia = kopia->right;
else kopia = kopia->left;
}
return NULL;
}
int dodaj (drzewo *d, int klucz)
{
if (wyszukiwanie(d,klucz)) return 0; //jezeli taki element jest juz w bazie
drzewo *aktualny = d, *poprzedni=NULL, *kopia =d;
drzewo *nowy= new drzewo;
nowy->left=NULL;
nowy->right=NULL;
nowy->key=klucz;
if (d->right==NULL && d->left==NULL && d->key==NULL) {d->key=klucz; return 1;}
while(aktualny!=NULL)
{
poprzedni = aktualny;
if(nowy->key > aktualny->key) aktualny = aktualny->right;
else aktualny = aktualny->left;
}
if(nowy->key > poprzedni->key) poprzedni->right = nowy;
else poprzedni->left = nowy;
/*while(obecny)
{
poprzedni=obecny;
if(obecny->key > klucz)
{
obecny=obecny->left;
}
else
{
obecny=obecny->right;
}
}
if(poprzedni->key > klucz)
{
poprzedni->left=nowy;
return 1;
}
else
{
poprzedni->right=nowy;
return 1;
}
*/
}
int _tmain(int argc, _TCHAR* argv[])
{
drzewo *root= new drzewo;
root->right=NULL;
root->left=NULL;
root->key=NULL;
int klucz, x=0, end=1, pierwszy = 0;
for (;end;)
{
cout<<"MENU - drzewo poszukiwan binarnych"<<endl<<endl<<"1. Dodanie nowego elementu z klawiatury"<<endl<<"2. Dodanie X nowych elementow (wylosowanych). "<<endl<<"3. Wyswietlanie elementow ''inorder''."<<endl<<"4. Wyszukanie zadanego elementu"<<endl<<"5. Usuniecie zadanego elementu (odwolanie do poprzednika)"<<endl<<"6. Usuniecie zadanego elementu (odwolanie do nastepnika)"<<endl<<endl<<"0. Zakonczenie pracy programu"<<endl;
cout<<endl<<"Decyzja: "; cin>>x;
if (x==1){
system("cls");
if (pierwszy == 0) {pierwszy=1; cout<<"Drzewo zostalo utworzone"<<endl; }
cout<<"Dodanie nowego elementu z klawiatury."<<endl;
cout<<endl<<endl<<"Podaj wartosc klucza elementu ktory chcesz dodac: "<<endl;
cin>>klucz;
int p =dodaj(root, klucz);
if(!p)
{
cout<<"Taki element juz istnieje!"<<endl;
}
else if(p) cout<<"Dodano! "<<endl;
system("PAUSE");
}
else if (x==2){
system("cls");
if (pierwszy == 0) {pierwszy=1; cout<<"Drzewo zostalo utworzone"<<endl; }
cout<<"Dodanie X nowych elementow (wylosowanych). "<<endl;
cout<<"Podaj liczbe wezlow do wylosowania: ";
int ilosc=0;
cin>>ilosc;
srand (time(NULL));
for (int i=0 ; i<ilosc ; )
{
int w=1+rand()%200;
int p =dodaj(root, w);
if(p) {
cout<<"Dodano! "<<endl;
i++;
}
}
system("PAUSE");
}
else if (x==3){
system("cls");
printinorder(root);
cout<<endl;
system("PAUSE");
}
else if (x==4){
system("cls");
cout<<"Wyszukanie zadanego elementu"<<endl<<"Podaj klucz wezla ktorego szukasz: "<<endl;
int klucz, znaleziono=0;
cin>>klucz;
znaleziono=wyszukiwanie(root, klucz);
if(znaleziono==1) cout<<endl<<"Wezel o wskazanym kluczu istnieje"<<endl;
else cout<<"WEZEL NIE ISTNIEJE"<<endl;
system("PAUSE");
}
else if (x==5){
system("cls");
system("PAUSE");
}
else if (x==6){
system("cls");
system("PAUSE");
}
else if (x == 0){
system("cls");
cout<<"KONIEC"<<endl;
end=0;
}
system ("cls");
}
system("PAUSE");
//generowanie(d);
return 0;
}
Z góry dziękuję za wszelką pomoc i sugestie.
Pozdrawiam,
Michał