• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Przechodzenie drzewa



    Podstrony: [1] [2] 3
    Przeczytaj także...
    Drzewo składniowe, drzewo AST (ang. syntax tree) czyli drzewo składni abstrakcyjnej (ang. abstract syntax tree) - drzewo etykietowane, wynik przeprowadzenia analizy składniowej zdania (słowa) zgodnie z pewną gramatyką. Każdy węzeł wewnętrzny tego drzewa reprezentują pewną konstrukcję języka, a jego synowie znaczące składowe tej konstrukcji.Drzewo – w informatyce to struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych.
    Przykład przejścia binarnego drzewa AST opisującego wyrażenie arytmetyczne[ | edytuj kod]

    (1*(2-3))+(4+5)

    in-order - notacja wrostkowa[ | edytuj kod]

    (1*(2-3))+(4+5)
    

    Notacja wrostkowa wymaga nawiasów do zdefiniowania kolejności wykonywania operacji.

    Część nawiasów z powyższego zapisu może zostać opuszczona bez uszczerbku dla wyniku wyrażenia arytmetycznego. Jednak po usunięciu nadmiarowych (z punktu widzenia poprawności wyniku) nawiasów zapis przestanie być wzajemnie jednoznaczny z przytoczonym drzewem.

    Konkretniej: z przytoczonego drzewa wynika, że operacja +(4,5) powinna zostać wykonana przed + z korzenia. Po opuszczeniu nawiasów powstałaby dowolność w kolejności wykonywania + i z zapisu bez 'nadmiarowych' nawiasów byłoby możliwe wyprowadznie więcej niż jednego drzewa. Inaczej: z łączności dodawania wynika, że na drzewie składniowym dopuszczalne są obroty operacji + względem siebie.

    Łą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.

    pre-order - notacja polska[ | edytuj kod]

    + * 1 - 2 3 + 4 5
    

    lub nawiązując do języków programowania:

    plus(razy(1,minus(2,3)),plus(4,5))
    

    post-order - odwrotna notacja polska (RPN)[ | edytuj kod]

    1 2 3 - * 4 5 + +
    

    W latach 70. kalkulatory RPN były popularne w kręgach finansowych. Obliczenia z wykorzystaniem RPN używają stosu. Współcześnie powyższe wyrażenie może zostać wykonane przy pomocy kalkulatora dc.

    $ dc
    1 2 3 - * 4 5 + +
    p
    8
    

    Komenda p zwraca wartość na wierzchołku stosu, czyli w tym przypadku ostateczny wynik wyrażenia.

    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).

    Levelorder[ | edytuj kod]

    Level-order: F, B, G, A, D, I, C, E, H.

    Istnieje również metoda przechodzenia levelorder, która polega na odwiedzaniu wierzchołków kolejno według wzrastającego poziomu zagłębienia. Jest ona implementowana przy użyciu algorytmu przeszukiwania wszerz (BFS), np. z wykorzystaniem kolejki. W przykładowym drzewie powyżej metoda ta odwiedza węzły w kolejności:

    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.
  • level-order: F, B, G, A, D, I, C, E, H.
  • LEVEL-ORDER(wierzchołek_v)
     {
        utwórz kolejkę wierzchołków k
        wstaw wierzchołek_v do kolejki
    
        dopóki kolejka nie jest pusta:
    
            pobierz z kolejki wierzchołek w
            wypisz wierzchołek_w.wartość
    
            dla każdego wierzchołka u będącego potomkiem wierzchołka w:
                wstaw wierzchołek u do kolejki
     }
    
    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ń.


    Podstrony: [1] [2] 3



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    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".
    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.

    Reklama

    Czas generowania strony: 0.013 sek.