Przechodzenie drzewa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa.

Łączność – jedna z własności działań dwuargumentowych, czyli np. operatorów arytmetycznych. Pojęcie to występuje w dwóch znaczeniach.Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.

Sposoby przechodzenia drzewa binarnego[ | edytuj kod]

Wyróżnia się 3 sposoby rekursywnego przejścia drzewa binarnego:

Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.Kolejka (ang. queue) – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).
  • VLR – pre-order, przejście wzdłużne,
  • LVR – in-order, przejście poprzeczne,
  • LRV – post-order, przejście wsteczne,
  • gdzie: Visit – „odwiedź” węzeł, Left – przejdź lewe poddrzewo, Right – przejdź prawe poddrzewo.

    W przypadku gdy dane drzewo jest binarnym drzewem AST przejścia określa się również:

  • pre-order – prefiksowym, gdyż wynik odwiedzania poszczególnych węzłów jest trawestacją wyrażenia zawartego w strukturze AST do postaci przedrostkowej (notacji Łukasiewicza),
  • in-order – infiksowym, gdyż trawestuje wyrażenie do postaci wrostkowej,
  • post-order – postfiksowym, gdyż trawestuje wyrażenie do postaci przyrostkowej (odwrotnej notacji polskiej).
  • Niniejsze algorytmy rekurencyjne działają na drzewie binarnym:

    Rotacja drzewa – w informatyce operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.Binarne drzewo poszukiwań (ang. Binary Search Tree (BST)) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi O(log n). Złożoność obliczeniowa jest tak niska, ponieważ operacje wykonywane są wzdłuż drzewa. Z tego samego powodu w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do O(n). W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa h - wynosi on O(h). Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.
  • Pre-order
  • Pre-order: F, B, A, D, C, E, G, I, H.
    PRE-ORDER(wierzchołek_v)
     {
        wypisz wierzchołek_v.wartość
        jeżeli wierzchołek_v.lewy_syn != null to PRE-ORDER(wierzchołek_v.lewy_syn)
        jeżeli wierzchołek_v.prawy_syn != null to PRE-ORDER(wierzchołek_v.prawy_syn)
     }
    

    Działanie jest wykonywane najpierw na rodzicu, następnie na synach.

    dc to uniksowe narzędzie służące do wykonywania prostych obliczeń według poleceń podanych przy użyciu odwrotnej notacji polskiej. Jest to jedno ze starszych narzędzi napisanych dla tego systemu, obecnie nie jest już szerzej używane.Odwrotna notacja polska (ONP, ang. Reverse Polish Notation, RPN) – jest sposobem zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy) lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.
  • In-order
  • In-order: A, B, C, D, E, F, G, H, I.
    IN-ORDER(wierzchołek_v)
     {
        jeżeli wierzchołek_v.lewy_syn != null to IN-ORDER(wierzchołek_v.lewy_syn)
        wypisz wierzchołek_v.wartość
        jeżeli wierzchołek_v.prawy_syn != null to IN-ORDER(wierzchołek_v.prawy_syn)
     }
    

    Najpierw wykonywane jest działanie na jednym z synów, następnie na rodzicu i na końcu na drugim synu. Przechodząc w ten sposób drzewo poszukiwań binarnych, otrzymuje się posortowane wartości wszystkich węzłów. Dzieje się tak dlatego, że w drzewie poszukiwań binarnych wartości lewego syna węzła n oraz wszystkich jego potomków są mniejsze od wartości n, a wartości prawego syna i jego potomków większe od wartości n.

    Zapis infiksowy – inaczej zapis wrostkowy. Klasyczny sposób zapisywania wyrażeń z binarnymi (dwuargumentowymi) operacjami arytmetycznymi (dodawanie, mnożenie, potęgowanie, itd.).Notacja polska, zapis przedrostkowy, notacja Łukasiewicza – sposób zapisu wyrażeń logicznych (a później arytmetycznych), podający najpierw operator, a potem operandy (argumenty). Został przedstawiony w 1920 roku przez polskiego filozofa i logika Jana Łukasiewicza. Różniła się ona od zapisów nawiasowych używanych, m.in., przez klasyczne dzieło formalizmu logicznego Principia Mathematica Bertranda Russella i A. N. Whiteheada. Według Jana Woleńskiego, notacja ta pozwala na łatwiejsze przeprowadzanie operacji na formułach o znacznej długości; formuły krótsze wydają się bardziej "intuitywne".
  • Post-order
  • Post-order: A, C, E, D, B, H, I, G, F.
    POST-ORDER(wierzchołek_v)
     {
        jeżeli wierzchołek_v.lewy_syn != null to POST-ORDER(wierzchołek_v.lewy_syn)
        jeżeli wierzchołek_v.prawy_syn != null to POST-ORDER(wierzchołek_v.prawy_syn)
        wypisz wierzchołek_v.wartość
     }
    

    Działanie jest wykonywane najpierw na wszystkich synach, na końcu na rodzicu.

    Przeszukiwanie wszerz (ang. Breadth-first search, w skrócie BFS) – jeden z najprostszych algorytmów przeszukiwania grafu. Przechodzenie grafu rozpoczyna się od zadanego wierzchołka s i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków. Wykorzystywany jest do odnajdywania najkrótszej drogi w grafie. Wynikiem działania algorytmu jest także drzewo przeszukiwania wszerz o korzeniu w s, zawierające wszystkie wierzchołki do których prowadzi droga z s. Algorytm działa prawidłowo zarówno dla grafów skierowanych jak i nieskierowanych.


    Podstrony: 1 [2] [3]




    Reklama