POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZAP  zima 2013/14
Język programowania: C/C++
Środowisko programistyczne: Qt
Wykład 11 : Listy c.d. Drzewa binarne i drzewa BST.
2
Tworzenie listy prostej
Funkcja wczytuje liczby całkowite aż do
Telement *utworz_liste ( ) {
napotkania zera i tworzy z nich listę w
Telement *aktualny, *glowa, *ogon;
kolejności wczytywania. Adres początku
int liczba;
utworzonej listy zwraca przez nazwę funkcji,
aktualny = NULL;
która (dla odmiany) jest typu wskaz
nikowego
glowa = NULL;
cout << "Wprowadz dane calkowite, 0 konczy wpisywanie\n";
cin >> liczba; // wczytujemy 1-szą liczbę
while (liczba !=0) { // dopóki nie wczytano zera
ogon = aktualny; // zapamiętujemy dotychczasowy koniec listy
aktualny = new Telement; // tworzymy miejsce dla nowego elementu
aktualny->dane = liczba; // zapisujemy do niego odczytane dane
aktualny->next = NULL; // i wpisujemy NULL
// bo teraz jest to ostatni element listy
if (ogon == NULL) // jeśli nowy element to pierwszy element listy
glowa = aktualny; // to staje się on głową
else // a jeśli nie, to doczepiamy go do starego ogona:
ogon->next = aktualny;
cin >> liczba;
}
return glowa;
}
kierunek dodawania elementów
3
Szkielet programu - tworzenie i drukowanie listy
using namespace std;
struct Telement {
int dane;
Telement *next;
};
Telement *utworz_liste ( ) { // funkcja jest teraz typu wskaz
nikowego
Telement *aktualny, *glowa,...; // glowa jest zmienną lokalną typu wskaz
nikowego
... // treść funkcji
return glowa;
}
void drukuj_liste (Telement *adres) {
... // treść funkcji
}
int main( ) {
Telement *glowa; // deklaracja wskaz
nika glowa
glowa = utworz_liste ( ); // zapamiętujemy głowę zwróconą przez funkcję
drukuj_liste (glowa); // i od niej zaczynamy drukowanie
return 0;
}
4
Wstawianie elementu do listy
// funkcja wstawiająca do listy element o jakimś adresie nowy
// za elementem o jakimś adresie gdzie
void wstaw_element (Telement *gdzie, Telement *nowy) {
Telement *tmp; // wskaz
nik pomocniczy
if (gdzie!= NULL) {
// zapamiętujemy adres elementu za tym wskazywanym przez gdzie:
tmp = gdzie->next;
// za elementem o adresie gdzie wstawiamy dodatkowy element o adresie nowy:
gdzie->next = nowy;
// i na koniec dołączamy ten dodatkowy do dotychczasowego następnika:
nowy->next = tmp;
}
}
5
Usuwanie elementu z listy
// funkcja usuwająca z listy element za elementem o jakimś adresie za_ktorym
void usun_za (Telement *za_ktorym) {
Telement *tmp; // wskaz
nik pomocniczy
if (za_ktorym!= NULL) {
tmp = za_ktorym->next; // zapamiętujemy adres elementu do usunięcia
// tworzymy połączenie z ominięciem elementu usuwanego:
za_ktorym->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 *tmp; // wskaz
nik pomocniczy
if (glowa!= NULL) {
tmp = glowa; // zapamiętujemy adres elementu do usunięcia
glowa = glowa->next; // przesuwamy się do elementu następnego
delete tmp; // zwalniamy pamięć i kasujemy wskaz
nik tmp
}
}
6
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
7
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
8
Przykłady drzew binarnych
Autor: Krzysztof Trzciński, R59,
praca magisterska, styczeń 2007
Drzewo krążenia dużego
Drzewo krążenia płucnego
9
Binarne drzewa poszukiwań (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ć !
10
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
n=9 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
}
else 5
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 korzeń nie jest już NULL
1 7
...
};
11
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.
12
Binarne drzewo poszukiwań - aplet
Autor:Jakub Krzesłowski, gr. R41, listopad 2006
Przykład wyświetlania drzewa w kolejności inorder 
operacja  Odczytaj drzewo
Wyświetlanie drzewa BST - c.d.
13
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
14
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;
}
15
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ównaj z rekurencyjną
pom = wezel;
procedurą usuwania listy (s. 6)
wezel = NULL;
delete pom;
}
}
16
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
17
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