Drzewa. Przykład.
Drzewo ukorzenione o wysokości = 4.
Drzewo to spójny graf bez cykli. Drzewo ukorzenione, to
7
drzewo, w którym jeden z wierzchołków jest wyróżniony -
wierzchołek ten nazywamy korzeniem. Wierzchołki drzew
2 11 5
nazywamy też węzłami.
10 8 3 9
Rozważmy dowolny węzeł x drzewa ukorzenionego T o korzeniu r.
Ponieważ T jest spójne, to istnieje ścieżka łącząca x z r w T , a
4 6 15
ponieważ T nie zawiera cykli, taka ścieżka jest jedyna. Jej długość
1
(ilość krawędzi) nazywamy głębokością węzła x. Największa
głębokość węzła to wysokość drzewa.
Głębokość 0 (korzeń): 7;
Każdy węzeł y na ścieżce z r do x nazywamy przodkiem węzła x. Głębokość 1: 2, 11, 5;
Jeśli y jest przodkiem x, to x jest potomkiem węzła y. Zbiór Głębokość 2: 10, 8, 3, 9;
wszystkich potomków x wraz z łączącymi je krawędziami tworzy Głębokość 3: 4, 6, 15;
poddrzewo o korzeniu x. Głębokość 4: 1.
Poddrzewo o korzeniu w węz
le 8 zawiera węzły 8, 6, 15 i 1.
Drzewa binarne.
Jeżeli węzeł y jest bezpośrednim poprzednikiem węzła x na ścieżce
Drzewo binarne to drzewo ukorzenione, w którym każdy węzeł na
od korzenia, to mówimy, że y jest ojcem x, a x jest synem y.
co najwyżej dwóch synów: lewego i prawego.
Poddrzewo, którego korzeń jest lewym (prawym) synem węzła x
Korzeń jest jedynym węzłem drzewa, który nie ma ojca.
nazywamy lewym (prawym) poddrzewem x.
Jeśli dwa węzły mają tego samego ojca, to nazywamy je braćmi.
7
Węzeł, który nie ma syna, nazywamy liściem.
2 5
Węzeł, który nie jest liściem, jest węzłem wewnętrznym.
10 8 3 9
4 6 15 11
Liczba synów węzła x nazywa się stopniem x.
1
Pełne drzewo binarne to drzewo binarne, w którym wszystkie
liście mają tą samą głębokość, a wszystkie węzły wewnętrzne mają
Lemat 2.2
stopień dwa.
Drzewo binarne o n węzłach ma wysokość co najmniej log n .
Uwaga
Na tym wykładzie log oznacza logarytm przy podstawie 2.
Dowód. Oznaczmy wysokość drzewa przez h. Zauważmy, że ilość
węzłów w naszym drzewie jest nie większa niż ilość węzłów w
drzewie pełnym, o tej samej wysokości. Stąd i z Lematu 2.1 mamy:
Lemat 2.1 2h+1 - 1 e" n,
Pełne drzewo binarne o wysokości h ma 2h+1 - 1 węzłów.
h e" log(n + 1) - 1.
Dowód. Korzeń ma dwóch synów o głębokości 1, z których każdy
ma dwóch synów o głębokości 2, itd. Liczba węzłów o głębokości i
Pozostaje zauważyć, że log(n + 1) - 1 e" log n , bo
wynosi zatem 2i, a liczba wszystkich węzłów
log(n + 1) e" log(n + 1) > log n e" log n , a dwie liczby
h całkowite różnią się o co najmniej 1.

2i = 2h+1 - 1.
i=0
Reprezentowanie drzew ukorzenionych. Przeglądanie drzewa binarnego.
Załóżmy, że mamy dane drzewo binarne T i chcemy wypisać
wszystkie jego klucze. Procedura TREE-PRINT(x) wypisuje
Do reprezentowania drzew w pamięci komputera możemy użyć wszystkie klucze z poddrzewa o korzeniu x.
struktur wskaz
nikowych, podobnie jak dla list.
TREE-PRINT(x)
Węzły drzewa reprezentujemy w postaci rekordów. Zakładamy, że 1. begin

każdy rekord ma pole key, tj. klucz. Pozostałe pola służą do 2. if x = NIL then
przechowywania wskaz
ników do innych węzłów. 3. begin
4. wypisz key[x];
W każdym węz
le drzewa binarnego przechowujemy wskaz
niki do
5. TREE-PRINT(left[x]);
ojca oraz lewego i prawego syna, odpowiednio w polach p, left i
6. TREE-PRINT(right[x]);
right. Jeśli p[x] = NIL, to x jest korzeniem drzewa. Jeśli węzeł x
7. end
nie ma lewego (prawego) syna to left[x] = NIL (right[x] = NIL).
8. end.
W dodatkowej zmiennej root pamiętamy wskaz
nik do korzenia
drzewa. Jeżeli root = NIL to drzewo jest puste. TREE-PRINT jest procedurą rekurencyjną (wywołuje samą siebie).
Najpierw wypisywany jest klucz korzenia x, potem klucze z lewego
poddrzewa, a następnie z prawego. Żeby wypisać wszystkie klucze
T , należy wykonać TREE-PRINT(root).
Przykład. Drzewa o dowolnym stopniu węzła.
Metodę reprezentowania drzew binarnych można uogólnić na
Procedura TREE-PRINT wypisze klucze drzewa
drzewa, w których stopień (liczba synów) każdego węzła jest nie
większa niż pewna stała k; pola left i right należy wtedy zastąpić
7
polami child1, . . . , childk. Metody tej nie da się zastosować, gdy
stopień węzła nie jest ograniczony. Co gorsza, jeżeli stała k jest
2 5
duża, a większość węzłów ma mały stopień, to przy takiej
10 8 3 9
reprezentacji marnuje się dużo pamięci.
4 6 15 11
Rozwiązaniem tego problemu jest reprezentacja  na lewo syn, na
prawo brat , która umożliwia przedstawienie drzewa o dowolnym
1
stopniu węzła w postaci drzewa binarnego.
Zamiast wskaz
ników do wszystkich synów, każdy węzeł ma tylko
w następującej kolejności: 7, 2, 10, 4, 8, 6, 15, 1, 5, 3, 11, 9
dwa wskaz
niki:
Ćwiczenie.
left-child[x] wskazuje na pierwszego syna x,
W jakiej kolejności będą wypisane klucze, jeżeli w procedurze
TREE-PRINT zamienimy miejscami wiersze (a) 4. i 5.? (b) 4. i 6.? right-sibling[x] wskazuje na następnego, znajdującego się na
prawo brata x.
Drzewo o węzłach stopnia d" 3:
Reprezentacja pełnego drzewa binarnego.
7
Pełne drzewo binarne o n węzłach wygodnie jest reprezentować w
postaci tablicy A[1 . . . n] w następujący sposób. Pole A[1] jest
2 11 5
korzeniem drzewa, A[2] i A[3] są węzłami o głębokości 1, itd.
10 8 3 1 9
A[1]
4 6 15
A[2] A[3]
A[4] A[5] A[6] A[7]
To samo drzewo w reprezentacji  na lewo syn, na prawo brat :
A[8] A[9] A[10] A[11] A[12] A[13] A[14] A[15]
7
Mając dany indeks i węzła, łatwo obliczyć indeksy jego ojca p(i) i
2 11 5
synów left(i), right(i):
10 8 3 1 9
p(i) = i/2 , left(i) = 2i, right(i) = 2i + 1.
4 6 15