Wysłano: Środa, 09 Czerwca 2004, 19:46 |
|
|
|
heyka!
znow potrzbuje pomocy!
procedura usuwania wezla z drzewa usuwanie(T,q)
(to najwazniejsze..)
oraz
tym razem
implementacje takich algorytmow9ale to chyba jakos dam rade zrobic;)
wyszukiwanie (a,b)
if (( a = NULL) lub ( c= klucz [a] ))
return a
else
if (c < klucz [a]_
return wyszukiwanie (lewy[a], c)
else
return wyszukiwanie (prawy [a], c)
end if
end if
___________________
i drugi:
wstawianie (T,q)
p=NULL
a = ro [T]
while (x !=NULL)
y = x
if ( key [q] , key[a] )
a = lewy [a]
else
a = prawy [a]
end while
d[q] = p
if ( p !=NULL )
ro [T] = q
else
if (key[q] < key[p])
left [p] = q
else
right[p] = q
z gory dzieki za pomoc!!!! |
|
|
|
|
|
|
|
Wysłano: Czwartek, 10 Czerwca 2004, 21:39 |
|
|
|
czesc
a co to za jezyk, ktory pokazalas?
Moge ci dac kod do usuwania w C, z krotkim opisem.
Gdy usuwamy X sa trzy mozliwosci:
1. X nie ma potomkow - usuwamy a rodzicowi zmieniamy lewego albo prawego potomka na NULL.
2. X ma jednego potomka - usuwamy X, jego potomkowi zmieniamy rodzica na rodzica Xa, a rodzicowi Xa zmieniamy potomka na potomka Xa.
3. X ma 2 potomkow - idziemy najpierw na lewo od Xa, potem na prawo tak dlugo az napotkamy NULL. ostatni element oznaczmy przez Y. Klucz Xa := Klucz Y-ka, potem z Y-kiem robimy to co w przypadku 1 lub 2 z Xem. Wlasnosc drzewa zostaje zachowana.
Ten kod realizuje te trzy przypadki w dosc zagmatwany, bo optymalny sposob
Kod: |
int del(int k){ //parametrem jest klucz
EL *x,*y,*z;
if(!(x=szukaj(root,k))) //szukaj zwraca 0 gdy takiego klucza nie ma i wskaznik jesli jest
return 0;
if(!x->l || !x->r) y=x;
else{
y=x->l;
while(y->r)
y=y->r;
}
if(y->l) z=y->l;
else z=y->r;
if(z) z->p=y->p;
if(!y->p) root=z; //root jest zdefiniowany globalnie
else{
if(y==y->p->l) y->p->l=z;
else y->p->r=z;
update(y->p);
}
if(y!=x) x->k=y->k;
free(y);
return 1;
} |
|
|
|
|
|
|
|
|
Wysłano: Sobota, 12 Czerwca 2004, 21:42 |
|
|
|
dzieki!
fakt zapomnialam napisac w jakim jeyzku,ale chodizlo mi o c/cpp;)
pozdrawiam!!!!!! |
|
|
|
|
noclegi w ciechocinku
Kopiowanie i rozpowszechnianie materiałów w całości lub części jest niedozwolone. Wszelkie informacje zawarte w tym miejscu są chronione prawem autorskim.
|