Informatyka dla klas II

Drzewa binarne

Drzewo (ang. tree) jest strukturą danych zbudowaną z elementów, które nazywamy węzłami (ang. node). Dane przechowuje się w węzłach drzewa. Węzły są ze sobą powiązane w sposób hierarchiczny za pomocą krawędzi (ang. edge), które zwykle przedstawia się za pomocą strzałki określającej hierarchię. Pierwszy węzeł drzewa nazywa się korzeniem (ang. root node). Od niego "wyrastają" pozostałe węzły, które będziemy nazywać synami (ang. child node). Synowie są węzłami podrzędnymi w strukturze hierarchicznej. Synowie tego samego ojca są nazywani braćmi (ang. sibling node). Węzeł nadrzędny w stosunku do syna nazwiemy ojcem (ang. parent node). Ojcowie są węzłami nadrzędnymi w strukturze hierarchicznej. Jeśli węzeł nie posiada synów, to nazywa się liściem (ang. leaf node), w przeciwnym razie nazywa się węzłem wewnętrznym (ang. internal node, inner node, branch node).


Struktura drzewa    
obrazek   A...H – węzły drzewa

strzałki – krawędzie. Zwrot określa kierunek hierarchii rodzić → dziecko.

A – korzeń drzewa
B,C,D  – bracia, synowie węzła A, który jest dla nich ojcem
E,F,G  – bracia, synowie węzła B, który jest dla nich ojcem
H – syn węzła D, który jest dla niego ojcem
A,B,D – węzły wewnętrzne
C,E,F,G,H – liście

 

Za wyjątkiem korzenia wszystkie pozostałe węzły w drzewie posiadają swojego ojca. W normalnym drzewie liczba synów dla dowolnego węzła nie jest ograniczona. Istnieje jednakże bardzo ważna klasa drzew, w których dany węzeł może posiadać co najwyżej dwóch synów. Noszą one nazwę drzew binarnych (ang. binary tree).

Ciąg węzłów połączonych krawędziami nazwiemy ścieżką (ang. path). Od korzenia do określonego węzła w drzewie wiedzie zawsze dokładnie jedna ścieżka prosta, tzn. taka, iż zawarte w niej węzły pojawiają się tylko jeden raz. Długością ścieżki (ang. path length) nazwiemy liczbę krawędzi łączących węzły w ścieżce. Dla naszego drzewa mamy następujące ścieżki proste od korzenia do kolejnych węzłów:


Struktura drzewa   Ścieżki
obrazek   ścieżka od A do A: długość 0: A
ścieżka od A do B: długość 1: A→B
ścieżka od A do C: długość 1: A→C
ścieżka od A do D: długość 1: A→D
ścieżka od A do E: długość 2: A→B→E
ścieżka od A do F: długość 2: A→B→F
ścieżka od A do G: długość 2: A→B→G
ścieżka od A do H: długość 2: A→D→H

 

Długość ścieżki prostej od korzenia do danego węzła nazywa się poziomem węzła (ang. node level). Korzeń drzewa ma zawsze poziom 0. W naszym drzewie węzły B, C i D mają poziom 1, a E, F, G i H mają poziom 2. Wysokość drzewa (ang. tree height) jest równa największemu poziomowi węzłów (lub najdłuższej ścieżce rozpoczynającej się w korzeniu). Dla naszego drzewa wysokość jest równa 2. Wysokość węzła (ang. node height), to długość najdłuższej ścieżki od tego węzła do liścia. Dla korzenia wysokość węzła jest równa wysokości drzewa:


Struktura drzewa   Wysokości węzłów
obrazek   węzeł A: wysokość = 2
węzeł B: wysokość = 1
węzeł C: wysokość = 0
węzeł D: wysokość = 1
węzeł E: wysokość = 0
węzeł F: wysokość = 0
węzeł G: wysokość = 0
węzeł H: wysokość = 0

 

Poziom drzewa (ang. tree level, the level of a tree) dla danego węzła to długość ścieżki prostej od korzenia do danego węzła.


Struktura drzewa   Poziomy
obrazek   Poziom 0: A
Poziom 1: B,C,D
Poziom 2: E,F,G,H

 

Liczba krawędzi powiązanych z danym węzłem nosi nazwę stopnia węzła (ang. node degree). Krawędzie drzewa są krawędziami skierowanymi (ang. directed edge) i oznaczamy je za pomocą strzałek. Kierunek strzałki jednoznacznie określa pozycję w hierarchii – strzałka wychodzi od ojca i kończy się na synu. Z tego powodu stopień węzła rozbija się na dwa stopnie:


stopień wejściowy (ang. node in-degree) – liczba krawędzi wchodzących do węzła, dla drzewa nigdy nie przekracza 1, a jest równy 0 tylko dla korzenia,

stopień wyjściowy (ang. node out-degree) – liczba krawędzi wychodzących z węzła, określa liczbę synów.

 

Stopień węzła jest sumą stopnia wejściowego i wyjściowego.

Struktura drzewa    
obrazek   węzeł A: we=0, wy=3, stopień węzła = 3
węzeł B: we=1, wy=3, stopień węzła = 4
węzeł C: we=1, wy=0, stopień węzła = 1
węzeł D: we=1, wy=1, stopień węzła = 2
węzeł E: we=1, wy=0, stopień węzła = 1
węzeł F: we=1, wy=0, stopień węzła = 1
węzeł G: we=1, wy=0, stopień węzła = 1
węzeł H: we=1, wy=0, stopień węzła = 1

 

Zwróć uwagę, że liście nie będące korzeniem (jeśli korzeń jest liściem, to jego stopień wynosi 0) mają zawsze stopień równy 1.

Drzewo binarne

Drzewo, w którym węzły mogą posiadać co najwyżej dwóch synów, nazywa się drzewem binarnym (ang. binary tree, B-tree). Węzły potomne nazywamy odpowiednio synem lewym (ang. left child node) i synem prawym (ang. right child node). Drzewa binarne mają ogromne znaczenie w informatyce, ponieważ za ich pomocą można odwzorować również drzewa, których węzły posiadają dowolną liczbę synów – sposób takiego odwzorowania podamy w dalszej części rozdziału.


Drzewo binarne    
obrazek   A – korzeń, ojciec B i C
B,C – synowie A, B – lewy syn A, C – prawy syn A
D,E – liście, synowie B
F,G – liście, synowie C

 

W drzewie binarnym stopień każdego węzła nie przekracza 3. Stopień korzenia nie przekracza 2.

Regularne drzewo binarne (ang. regular binary tree, proper binary tree) zawiera wyłącznie węzły, których stopień wyjściowy jest albo równy 2 (węzeł posiada dwóch synów – jest węzłem wewnętrznym), albo 0 (węzeł nie posiada synów – jest liściem).


Regularne drzewo binarne   Stopnie wyjściowe
obrazek   A – stopień wyjściowy 2, węzeł wewnętrzny
B – stopień wyjściowy 2, węzeł wewnętrzny
C – stopień wyjściowy 2, węzeł wewnętrzny
D – stopień wyjściowy 0, liść
E – stopień wyjściowy 0, liść
F – stopień wyjściowy 0, liść
G – stopień wyjściowy 0, liść

 

Dla regularnego drzewa binarnego liczba węzłów na poziomie k-tym jest zawsze równa 2k.  Liczba wszystkich węzłów, czyli rozmiar drzewa (ang. binary tree size) jest równa 2p - 1, gdzie p oznacza liczbę poziomów.


obrazek

 

Dla n  węzłów liczba poziomów jest równa log2(n+1).

Ponumerujmy poziomami kolejne węzły, idąc od strony lewej do prawej:


obrazek

 

Otrzymane numery węzłów są powiązane ze strukturą hierarchii drzewa prostymi zależnościami:


obrazek      Jeśli węzeł o numerze k  posiada synów, to:

lewy syn ma numer 2k+1
prawy syn ma numer 2k+2

obrazek   Jeśli węzeł o numerze k posiada ojca, to:

ojciec ma numer [(k-1) / 2]

[...] oznacza część całkowitą.

 

Węzeł o numerze k  znajduje się na poziomie o numerze [log2(k+1)].

Węzeł o numerze k  jest wewnętrzny, jeśli 2k+2 < n. W przeciwnym razie węzeł jest liściem.

Własności te pozwalają odwzorowywać regularne drzewo binarne w ciąg elementów i na odwrót

 

obrazek

 

Kompletne drzewo binarne (ang. complete binary tree) posiada zapełnione węzłami wszystkie poziomy z wyjątkiem ostatniego, jednakże na ostatnim poziomie węzły są zapełnione począwszy od lewej strony.

 

Kompletne drzewo binarne   Niekompletne drzewo binarne
obrazek          obrazek

 

Kompletne drzewo binarne również da się odwzorować w ciąg węzłów. W takim drzewie liczba elementów n może być mniejsza od maksymalnej liczby węzłów, ponieważ ostatni poziom nie musi posiadać kompletu węzłów. Jednakże w przeciwieństwie do drzewa regularnego węzeł wewnętrzny może posiadać tylko jednego, lewego syna (u nas węzłem takim jest węzeł 4). Dlatego w kompletnym drzewie binarnym o rozmiarze n  dla węzła o numerze k  zachodzi:

 

2k  + 2 > n  – węzeł jest liściem

2k  + 2 = n  – węzeł jest ostatnim węzłem wewnętrznym i posiada tylko lewego syna

2k  + 2 < n  – węzeł jest węzłem wewnętrznym i posiada obu synów.

 

Poddrzewo (ang. subtree) jest drzewem zawartym w drzewie, gdy jako korzeń przyjmiemy jeden z węzłów. Dla danego węzła drzewa binarnego mogą istnieć dwa poddrzewa: lewe poddrzewo (ang. left subtree) – korzeniem jest lewy syn i analogicznie prawe poddrzewo (ang. right subtree) – korzeniem jest prawy syn:

 

obrazek

Reprezentacja drzew binarnych w programie

Istnieje wiele różnych rozwiązań dla reprezentacji drzew binarnych w pamięci komputera. Tutaj podamy te najprostsze.

Kompletne drzewo binarne

W tym przypadku drzewo możemy odwzorować w tablicy n-elementowej. Każdy element tablicy jest węzłem. Hierarchię drzewa przedstawiamy przy pomocy indeksów i ich własności dla kompletnych drzew binarnych. Korzeniem drzewa jest element o indeksie 0. Jego dwoma synami są kolejno elementy o indeksach 1 (lewy syn) i 2 (prawy syn). Postępując podobnie z pozostałymi węzłami otrzymamy całe drzewo binarne:

 

obrazek

obrazek

 

Niekompletne drzewo binarne

Drzewo odwzorowujemy podobnie jak listę. Każdy element jest strukturą, która oprócz danych zawiera dwa lub trzy wskaźniki:

 

  Code::Blocks
Wersja uproszczona
struct BTNode
{
  BTNode * left;
  BTNode * right;
  typ_danych data;
};
Wersja pełna
struct BTNode
{
  BTNode * up;
  BTNode * left;
  BTNode * right;
  typ_danych data;
};

 

Gdzie:

up  – wskazuje ojca danego węzła. Dla korzenia pole to zawiera wskazanie puste
left  – wskazuje lewego syna
right  – wskazuje prawego syna
data  – dane dowolnego typu przechowywane przez węzeł

 

Wskaźniki pozwalają na przemieszczanie się po węzłach w strukturze drzewa. Wskaźniki left  i right  umożliwiają przechodzenie w dół drzewa. Wskaźnik up  prowadzi w górę do ojca danego węzła. Jeśli ten kierunek nie jest istotny, to wskaźnik może zostać pominięty (wersja uproszczona).

Przechodzenie drzew binarnych – DFS

Drzewa odzwierciedlają różnego rodzaju struktury. W węzłach są przechowywane różne informacje. Często będziemy spotykać się z zadaniem, które wymaga odwiedzenia każdego węzła drzewa i przetworzenia informacji przechowywanych w węźle. Zadanie to realizują algorytmy przechodzenia drzewa (ang. tree traversal algorithm). Polegają one na poruszaniu się po drzewie od węzła do węzła wzdłuż krawędzi w pewnym porządku i przetwarzaniu danych przechowywanych w węzłach. Istnieje kilka takich algorytmów o różnych własnościach. Omówimy je w tym rozdziale

Algorytm DFS

Odwiedzenie węzła (ang. node visit) polega na dojściu do danego węzła po strukturze drzewa oraz przetworzenie danych zawartych w węźle. Przeszukiwanie w głąb (ang. Depth First Search - DFS) jest bardzo popularnym algorytmem przechodzenia przez wszystkie węzły poddrzewa, którego korzeniem jest węzeł startowy (jeśli węzłem startowym będzie korzeń drzewa, to DFS przejdzie przez wszystkie węzły zawarte w drzewie). Zasada działania tego algorytmu opiera się na rekurencji lub stosie, którym zastępujemy wywołania rekurencyjne. Ze względu na kolejność odwiedzin węzłów wyróżniamy trzy odmiany DFS (istnieją jeszcze trzy dalsze będące "lustrzanymi odbiciami"):

 

DFS: pre-order – przejście wzdłużne

W przejściu wzdłużnym (ang. pre-order traversal) najpierw odwiedzamy korzeń poddrzewa, a następnie przechodzimy kolejno lewe i prawe poddrzewo. Prześledź poniższy przykład:

 

Stan przejścia Przetworzone węzły Opis
obrazek A Odwiedzamy korzeń A i przechodzimy do lewego syna B, który jest korzeniem lewego poddrzewa dla węzła A.
obrazek A B Odwiedzamy korzeń B poddrzewa i przechodzimy do lewego syna D, który jest korzeniem poddrzewa dla węzła B.
obrazek A B D Odwiedzamy D i przechodzimy do H.
obrazek A B D H Odwiedzamy H. Węzeł nie ma dzieci, zatem lewe poddrzewo dla węzła D (ojca H) zostało przebyte. Wracamy do węzła D i przechodzimy do I, który jest korzeniem prawego poddrzewa dla węzła D.
obrazek A B D H I Odwiedzamy I. Węzeł jest liściem, zatem prawe drzewo węzła D zostało przebyte. Jednocześnie zostało przebyte całe lewe poddrzewo węzła B. Wracamy do B i przechodzimy do E, które jest korzeniem prawego poddrzewa węzła B.
obrazek A B D H I E Odwiedzamy węzeł E i przechodzimy do lewego poddrzewa, czyli do węzła J.
obrazek A B D H I E J Wracamy do korzenia A, ponieważ całe lewe poddrzewo zostało przebyte. Teraz w analogiczny sposób odwiedzamy prawe poddrzewo, rozpoczynając od jego korzenia C.
obrazek A B D H I E J C Odwiedzamy C i przechodzimy do lewego poddrzewa.
obrazek A B D H I E J C F Odwiedzamy F i przechodzimy do lewego poddrzewa.
obrazek A B D H I E J C F K Odwiedzamy K i wracamy do C (lewe poddrzewo węzła C jest przebyte), a następnie przechodzimy do prawego poddrzewa.
obrazek A B D H I E J C F K G Odwiedzamy G. Drzewo zostało przebyte.

Na poniższym rysunku zaznaczyliśmy linię przejścia przez kolejne węzły drzewa.

obrazek → pre-order → obrazek

 

Algorytm rekurencyjny DFS:preorder dla drzewa binarnego

Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Lista kroków:
K01: Jeśli v  = nil, to zakończ ; koniec rekurencji
K02: Odwiedź węzeł wskazany przez v  
K03: preorder(vleft) ; przejdź rekurencyjnie przez lewe poddrzewo
K04: preorder(vright) ; przejdź rekurencyjnie przez prawe poddrzewo
K05: Zakończ  

 

Algorytm stosowy DFS:preorder dla drzewa binarnego

Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Elementy pomocnicze:
S  –  stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.
Lista kroków:
K01: Utwórz pusty stos S  
K02: S.push(v) ; zapamiętujemy wskazanie węzła startowego na stosie
K03: Dopóki S.empty() = false, wykonuj K04...K08 ; w pętli przetwarzamy kolejne węzły
K04:     v  ← S.top() ; pobieramy ze stosu wskazanie węzła
K05:     S.pop() ; pobrane wskazanie usuwamy ze stosu
K06:     Odwiedź węzeł wskazany przez v ; przetwarzamy węzeł
K07:     Jeśli (vright) ≠ nil, to S.push(vright) ; umieszczamy na stosie wskazanie prawego syna, jeśli istnieje
K08:     Jeśli (vleft) ≠ nil, to S.push(vleft) ; umieszczamy na stosie lewego syna, jeśli istnieje i kontynuujemy pętlę aż do wyczerpania stosu
K09: Zakończ  

 

DFS: in-order – przejście poprzeczne

W przejściu poprzecznym (ang. in-order traversal) najpierw przechodzimy lewe poddrzewo danego węzła, następnie odwiedzamy węzeł i na koniec przechodzimy prawe poddrzewo.

 

Stan przejścia Przetworzone węzły Opis
obrazek H Rozpoczynamy w korzeniu A. Jednakże węzła A nie przetwarzamy, lecz przechodzimy do lewego syna B. Tutaj dalej przechodzimy do D i H. Węzeł H nie ma dzieci, więc przechodzenie do lewego poddrzewa się kończy i węzeł H zostaje przetworzony jako pierwszy.
obrazek H D Lewe poddrzewo węzła D zostało przebyte, zatem przetwarzamy węzeł D i przechodzimy do prawego poddrzewa, którego korzeniem jest węzeł I.
obrazek H D I Węzeł I jest liściem, zatem nie posiada lewego poddrzewa. Przetwarzamy węzeł I. 
obrazek H D I B Lewe poddrzewo węzła B zostało przebyte. Przetwarzamy węzeł B i przechodzimy do jego prawego poddrzewa rozpoczynającego się w węźle E.
obrazek H D I B J Będąc w węźle E najpierw przechodzimy jego lewe poddrzewo, czyli idziemy do węzła J. Węzeł J jest liściem i nie posiada dalszych poddrzew. Przetwarzamy J i wracamy do E.
obrazek H D I B J E Lewe poddrzewo węzła E zostało przebyte. Przetwarzamy węzeł E. Ponieważ nie posiada on prawego poddrzewa, wracamy do A.
obrazek H D I B J E A Lewe poddrzewo węzła A zostało przebyte. Przetwarzamy A i przechodzimy do prawego poddrzewa rozpoczynającego się od węzła C.
obrazek H D I B J E A K Będąc w węźle C przechodzimy do lewego poddrzewa rozpoczynającego się od węzła F, a tam dalej przechodzimy do następnego lewego poddrzewa, czyli do węzła K. Ten węzeł jest liściem i nie posiada dalszych poddrzew. Przetwarzamy K i wracamy do F.
obrazek H D I B J E A K F Lewe poddrzewo węzła F zostało przebyte. Przetwarzamy F. Ponieważ brak prawego poddrzewa, wracamy do C.
obrazek H D I B J E A K F C Lewe poddrzewo węzła C zostało przebyte, przetwarzamy C i przechodzimy do prawego poddrzewa, czyli do węzła G.
obrazek H D I B J E A K F C G G jest liściem, przetwarzamy G i kończymy.

 

obrazek → in-order → obrazek

 

Algorytm rekurencyjny DFS:inorder dla drzewa binarnego

Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Lista kroków:
K01: Jeśli v  = nil, to zakończ ; koniec rekurencji
K02: inorder(vleft) ; przejdź rekurencyjnie przez lewe poddrzewo
K03: Odwiedź węzeł wskazany przez v  
K04: inorder(vright) ; przejdź rekurencyjnie przez prawe poddrzewo
K05: Zakończ  

 

Algorytm stosowy DFS:inorder dla drzewa binarnego

Algorytm wykorzystuje stos oraz dodatkowy wskaźnik cp, którym przemieszczamy się po drzewie.
Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Elementy pomocnicze:
S  –  stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.
cp  – wskaźnik bieżącego węzła
Lista kroków:
K01: Utwórz pusty stos S  
K02: cp  ← v ; bieżącym węzłem jest korzeń drzewa
K03: Dopóki (S.empty() = false) obrazek (cp  ≠ nil) wykonuj K04...K11 ; pętla jest wykonywana, jeśli jest coś na stosie lub cp wskazuje węzeł drzewa
K04:     Jeśli cp  = nil, to idź do K07 ; sprawdzamy, czy wyszliśmy poza liść drzewa
K05:     S.push(cp) ; jeśli nie, to umieszczamy wskazanie bieżącego węzła na stosie
K06:     cp  ← (cpleft) ; bieżącym węzłem staje się lewy syn
K07:     Następny obieg pętli K02 ; wracamy na początek pętli
K08:     cp  ← S.top() ; wyszliśmy poza liść, wracamy do węzła, pobierające jego wskazanie ze stosu
K09:     S.pop() ; wskazanie usuwamy ze stosu
K10:     Odwiedź węzeł wskazany przez cp ; przetwarzamy dane w węźle
K11:     cp  ← (cpright) ; bieżącym węzłem staje się prawy syn
K12: Zakończ  

 

DFS: post-order – przejście wsteczne

W przejściu wstecznym (ang. post-order traversal) najpierw przechodzimy lewe poddrzewo, następnie prawe, a dopiero na końcu przetwarzamy węzeł.

 

Stan przejścia Przetworzone węzły Opis
obrazek H Rozpoczynamy w korzeniu A. Najpierw przechodzimy lewe poddrzewo. Idziemy do B. Tutaj również przechodzimy lewe poddrzewo i idziemy do D, a następnie do H. Węzeł H jest liściem i nie posiada poddrzew. Przetwarzamy H i wracamy do D.
obrazek H I Lewe poddrzewo węzła D jest przebyte, przechodzimy poddrzewo prawe. Idziemy do węzła I. Ponieważ jest on liściem, to nie posiada poddrzew. Przetwarzamy I. Wracamy do D.
obrazek H I D Oba poddrzewa węzła D zostały przebyte, przetwarzamy D i wracamy do B.
obrazek H I D J Dla węzła B przebyte zostało poddrzewo lewe. Teraz przechodzimy przez jego prawe poddrzewo. Idziemy do E i do J (lewe poddrzewo E). J jest liściem i nie posiada dalszych poddrzew, zatem przetwarzamy J i wracamy do E.
obrazek H I D J E Lewe poddrzewo węzła E zostało przebyte. Nie ma prawego poddrzewa dla E, zatem przetwarzamy E i wracamy do B.
obrazek H I D J E B Lewe i prawe poddrzewo węzła B jest przebyte. Przetwarzamy węzeł B i wracamy do A.
obrazek H I D J E B K Lewe poddrzewo węzła A zostało przebyte. Przechodzimy do prawego poddrzewa, czyli do węzła C, następnie do F (lewe poddrzewo C) i do K (lewe poddrzewo F). K jest liściem i nie posiada poddrzew. Przetwarzamy K i wracamy do F.
obrazek H I D J E B K F Lewe poddrzewo węzła F jest przebyte, a prawego poddrzewa brak. Przetwarzamy F i wracamy do C.
obrazek H I D J E B K F G Lewe poddrzewo węzła C jest przebyte, przechodzimy do poddrzewa prawego, czyli do węzła G. Węzeł G jest liściem i nie posiada poddrzew. Przetwarzamy G i wracamy do C.
obrazek H I D J E B K F G C Oba poddrzewa węzła C zostały przebyte. Przetwarzamy C i wracamy do A.
obrazek H I D J E B K F G C A Oba poddrzewa węzła A zostały przebyte. Przetwarzamy A i kończymy

 

obrazek → post-order → obrazek

 

 

Algorytm rekurencyjny DFS:postorder dla drzewa binarnego

Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Lista kroków:
K01: Jeśli v  = nil, to zakończ ; koniec rekurencji
K02: postorder(vleft) ; przejdź rekurencyjnie przez lewe poddrzewo
K03: postorder(vright) ; przejdź rekurencyjnie przez prawe poddrzewo
K04: Odwiedź węzeł wskazany przez v  
K05: Zakończ  

 

Algorytm stosowy DFS:postorder dla drzewa binarnego

Algorytm wykorzystuje stos oraz dwa wskaźniki: pp  – wskazanie poprzedniego węzła i cp  – wskazanie bieżącego węzła. Są one używane do określenia, czy oba poddrzewa danego węzła zostały przebyte.

 

Wejście
v    wskazanie węzła startowego drzewa binarnego
Wyjście:
przetworzenie wszystkich węzłów drzewa.
Elementy pomocnicze:
S  –  stos wskazań węzłów, rozmiar stosu nie przekracza podwójnej wysokości drzewa.
pp  – wskaźnik węzła poprzedniego
cp  – wskaźnik węzła bieżącego.
Lista kroków:
K01: Utwórz pusty stos S  
K02: S.push(v) ; węzeł startowy umieszczamy na stosie
K03: pp  ← nil ; zerujemy wskaźnik węzła poprzedniego
K04: Dopóki S.empty() = false: wykonuj K05...K14  
K05:     cp  ← S.top() ; ustawiamy cp na węzeł przechowywany na stosie
K06:     Jeśli (pp  = nil) obrazek ((ppleft) = cp) obrazek ((ppright) = cp), to idź do K11 ; sprawdzamy, czy idziemy w głąb drzewa
K07:     Jeśli (cpleft) = pp, to idź do K13 ; sprawdzamy, czy wróciliśmy z lewego poddrzewa
K08:     Odwiedź węzeł wskazany przez cp ; oba poddrzewa przebyte, przetwarzamy węzeł
K09:     S.pop() ; i usuwamy jego wskazanie ze stosu
K10:     Idź do K14  
K11:     Jeśli (cpleft) ≠ nil, to S.push(cpleft)
    inaczej jeśli (cpright) ≠ nil, to S.push(cpright)
; jeśli istnieje lewy syn cp, umieszczamy go na stosie
; inaczej umieszczamy na stosie prawego syna, jeśli istnieje
K12:     Idź do K14  
K13:     Jeśli (cpright) ≠ nil, to S.push(cpright) ; jeśli istnieje prawy syn, to umieszczamy go na stosie
K14:     pp  ← cp ; zapamiętujemy cp w pp i wykonujemy kolejny obieg pętli
K15: Zakończ  

 

Podsumowanie

Drzewo binarne przejście pre-order przejście in-order przejście post-order
obrazek obrazek obrazek obrazek

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe