POLITECHNIKA WARSZAWSKA
POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZASADY PROGRAMOWANIA KOMPUTERÓW
Język programowania: C/C++
Język programowania: C/C++
Środowisko programistyczne: C++ Builder 6
Środowisko programistyczne: C++ Builder 6
Wykład 11 : Listy c.d, drzewa binarne i drzewa BST
Wykład 11 : Listy c.d, drzewa binarne i drzewa BST
Wstawianie elementu do listy
Wstawianie elementu do listy
// funkcja wstawiająca do listy element o jakimś adresie co
// za elementem o jakimś adresie gdzie
void wstaw_element (Telement *gdzie, Telement *co) {
Telement *tmp; // wskaz
nik pomocniczy
// zapamiętujemy adres elementu za tym wskazywanym przez gdzie:
tmp = gdzie->next;
// za elementem o adresie gdzie wstawiamy dodatkowy element o adresie co:
gdzie->next = co;
// i na koniec dołączamy ten dodatkowy do dotychczasowego następnika:
co->next = tmp;
}
Usuwanie elementu z listy
Usuwanie elementu z listy
// funkcja usuwająca z listy element za elementem o jakimś adresie za_czym
void usun_za (Telement * za_czym) {
Telement *tmp; // wskaz
nik pomocniczy
if (za_czym!= NULL) {
tmp = za_czym->next; // zapamiętujemy adres elementu do usunięcia
// tworzymy połączenie z ominięciem elementu usuwanego:
za_czym->next = tmp ->next;
delete tmp; // zwalniamy pamięć i kasujemy wskaz
nik tmp
}
}
// funkcja usuwająca z listy pierwszy
// element o jakimś adresie glowa
void usun_glowe (Telement *& glowa) {
Telement *pom; // wskaz
nik pomocniczy
if (glowa!= NULL) {
pom = glowa; // zapamiętujemy adres elementu do usunięcia
glowa = glowa ->next; // przesuwamy się do elementu następnego
delete pom; // zwalniamy pamięć i kasujemy wskaz
nik pom
}
}
Zwalnianie pamięci - usuwanie listy
Zwalnianie pamięci - usuwanie listy
// iteracyjna procedura usuwania listy z pamięci
// zaczynamy od głowy, kończymy na ogonie
void usun_liste (Telement *&glowa) {
Telement *pom;
while (glowa != NULL) {
pom=glowa;
glowa=glowa->next;
delete pom;
}
// rekurencyjna procedura usuwania listy z pamięci
// zaczynamy od ogona, kończymy na głowie
void usun_liste (Telement *&glowa) {
Telement *pom;
if (glowa!=NULL) {
usun_liste (glowa->next);
pom=glowa;
Dzięki temu w każdym kroku
glowa=NULL;
usuwania zachowana jest struktura
delete pom;
listy, bo ostatni element wskazuje na
}
NULL, więc glowa na koniec też jest
}
równa NULL, a nie nieokreślona
Drzewa binarne
Drzewa binarne
Drzewo
Regularna struktura pamięciowa, gdzie każdy element (węzeł)
zawiera dwa lub więcej wskaz
ników do takich samych elementów
Drzewo binarne
Każdy element (węzeł) zawiera dokładnie dwa wskaz
niki
korzeń węzły
struct Twezel {
int Dane;
Twezel *Lewy;
Twezel *Prawy;
};
Uwaga: wskaz
niki równe
NULL nie są
narysowane. Liście
drzewa to węzły mające
oba wskaz
niki równe
NULL.
liście
Binarne drzewa sortowane (BST)
Binarne drzewa sortowane (BST)
BST (Binary Search Tree) - drzewo binarnego wyszukiwania
wszystkie elementy < węzeł < wszystkie elementy
lewego poddrzewa prawego poddrzewa
UWAGA: wartości w węzłach nie mogą się powtarzać !
Tworzenie drzewa BST
Tworzenie drzewa BST
Przykład:
. . . .
void DodajWezel (Twezel *&wezel, int wartosc) {
Utworzyć drzewo BST z ciągu
if (wezel == NULL) { // tworzymy i dołączamy element
wczytanych liczb:
wezel = new Twezel;
wezel -> Dane = wartosc;
5, 3, 8, 2, 6, 4, 9, 1, 7
wezel -> Lewy = NULL;
wezel -> Prawy = NULL;
Dodanie węzła o wartości 1
}
5
else
if (wartosc < wezel -> Dane)
3 8
DodajWezel (wezel -> lewy, wartosc ); // rekurencja
else
2 4 6 9
if (wartosc > wezel -> Dane)
DodajWezel (wezel -> prawy, wartosc ); // rekurencja
// liczby powtarzające się nie są dodawane do drzewa !!!
1
}
int main( ) {// przykład wykorzystania funkcji DodajWezel
int n, liczba;
Dodanie węzła o wartości 7
Twezel korzen;
5
korzen=NULL;
cin >> n; // n liczb ma być wczytanych
3 8
for (int i=0; icin >> liczba;
2 4 6 9
DodajWezel (korzen, liczba);
// teraz korzen nie jest już NULL
1 7
...
};
Wyświetlanie drzewa BST
Wyświetlanie drzewa BST
" kolejność inorder: lewe poddrzewo, węzeł, prawe poddrzewo
" kolejność preorder: węzeł, lewe poddrzewo, prawe poddrzewo
" kolejność postorder: lewe poddrzewo, prawe poddrzewo, węzeł
void WyswietlDrzewo (Twezel *wezel) {
// porządek inorder
if (wezel != NULL) {
WyswietlDrzewo (wezel->Lewy); // lewe poddrzewo
cout << wezel->Dane << " "; // węzeł
WyswietlDrzewo (wezel->Prawy); // prawe poddrzewo
}
}
Wyświetlając drzewo w kolejności
inorder uzyskujemy ciąg wartości
posortowany rosnąco.
Zatem główny ciężar procesu
sortowania spoczywa na etapie
tworzenia drzewa BST,
Kolejność wyświetlania wartości w węzłach:
1, 2, 3, 4, 5, 6, 7, 8, 9
wyświetlanie jest już tylko finałem.
Wyświetlanie drzewa BST - c.d.
Wyświetlanie drzewa BST - c.d.
void WyswietlDrzewo (Twezel *wezel) {
// porządek preorder
if (wezel != NULL) {
cout << wezel->Dane << " ";
WyswietlDrzewo (wezel->Lewy);
WyswietlDrzewo (wezel->Prawy);
}
}
Kolejność wyświetlania wartości w węzłach:
5, 3, 2, 1, 4, 8, 6, 7, 9
void WyswietlDrzewo (Twezel *wezel) {
// porządek postorder
if (wezel != NULL) {
WyswietlDrzewo (wezel->Lewy);
WyswietlDrzewo (wezel->Prawy);
cout << wezel->Dane << " ";
}
Kolejność wyświetlania wartości w węzłach:
}
1, 2, 4, 3, 7, 6, 9, 8, 5
Drzewo binarne - aplet
Drzewo binarne - aplet
Autor:Jakub Krzesłowski, gr. R41, listopad 2006
Przykłady drzew binarnych
Przykłady drzew binarnych
Autor: Krzysztof Trzciński, R59,
praca magisterska, styczeń 2007
Drzewo krążenia dużego
Drzewo krążenia płucnego
Poszukiwanie węzła w drzewie BST
Poszukiwanie węzła w drzewie BST
bool ZnajdzWezel (Twezel* wezel, int wartosc) {
// Funkcja zwraca wartość true, jeżeli udało się jej znalez
ć
// wartość, w przeciwnym razie zwraca wartość false
if (wezel == NULL)
return false;
else
if (wartosc < wezel->Dane)
return ZnajdzWezel (wezel->Lewy, wartosc);
else
if (wartosc > wezel->Dane)
return ZnajdzWezel (wezel->Prawy, wartosc);
else
return true;
}
Poszukiwanie węzła c.d., usuwanie całego drzewa BST
Poszukiwanie węzła c.d., usuwanie całego drzewa BST
void UsunDrzewo (Twezel *&wezel) {
Twezel *pom;
if (wezel != NULL) {
UsunDrzewo (wezel -> Lewy);
UsunDrzewo (wezel -> Prawy);
por. z rekurencyjną procedurą
pom=wezel;
usuwania listy
wezel=NULL;
delete pom;
}
}
Algorytm usuwania węzła w drzewie BST
Algorytm usuwania węzła w drzewie BST
Należy usunąć węzeł o podanej wartości. Mogą wystąpić przypadki:
1. Brak takiego węzła
2. Węzeł usuwany ma co najwyżej jednego potomka ( może też być liściem drzewa )
Adres usuwanego węzła zastępuje się adresem jego potomka ( lub NULL )
3. Węzeł usuwany ma dwóch potomków
a) Usuwany węzeł zostaje zastąpiony przez skrajny prawy węzeł jego lewego
poddrzewa (czyli największy element lewego poddrzewa)
lub:
b) Usuwany węzeł zostaje zastąpiony przez skrajny lewy węzeł jego prawego
poddrzewa (czyli najmniejszy element prawego poddrzewa)
UWAGA 1: Zastąpienie takie zawsze jest możliwe, bo skoro węzeł jest skrajny, to ma
co najwyżej jednego potomka.
UWAGA 2: Każdą z operacji a) i b) da się więc wykonać, najlepiej je wykonywać
losowo (lub na przemian).
Przypadek 2. Przypadek 3.
5
5
3 8
3 8
2 4 6 9
2 4 6 9
1 7
1 7
Przykład - usuwanie węzłów
Przykład - usuwanie węzłów
węzeł usuwany węzeł  zajmujący miejsce węzła usuwanego
5 5
3 8 3 8
2 4 6 9 1 4 6 9
1 7 7
1 2
5 6
3 9 3 9
1 4 6 1 4 7
7
3 4