Ocena brak

Według jakich zasad można systematycznie przeglądać strukturę drzewiastą?

Autor /Barnim7777 Dodano /29.12.2011

Przegląd struktury = budowanie ciągu zawierającego wszystkie elementy tej struktury.

Strukturę drzewiastą można przeglądać na trzy sposoby:

- wędruj i sprawdzaj (metoda rekurencyjna)

Jest to prosta metoda polegająca na przejrzeniu wszystkich elementów struktury i wypisaniu kolejno wszystkich jej elementów.

- przegląd w głąb (metoda iteracyjna)

Schemat działania algorytmu:

  1. Wypisany zostaje korzeń (jako pierwszy element ciągu)

  2. Algorytm wybiera ostatni element ciągu nie posiadający etykiety „zamknięty” i postępuje zgodnie z zasadą: jeśli wierzchołek nie ma potomstwa – nadaj mu etykietę „zamknięty”, jeśli ma, wypisz potomków sprawdzając od lewej

Wszystko powtarzane jest dopóki wszystkie elementy ciągu nie mają etykiety „zamknięty”.

- przegląd w szerz (metoda iteracyjna)

Schemat działania algorytmu:

  1. Nadanie wszystkim elementom drzewa etykiety „nowy”

  2. Wypisanie korzenia jako pierwszego elementu ciągu

  3. Algorytm wybiera z ciągu pierwszy element z etykietą „nowy” , dopisuje do ciągu wszystkich jego potomków (nadając im etykietę „nowy”) i zdejmuje etykietę „nowy” z danego elementu.

Wszystko powtarzane jest dopóki w ciągu znajdują się elementy z etykietą „nowy”.

Po utworzeniu odpowiedniego ciągu, do jego przeszukiwania wykorzystujemy metodę: „wędruj i sprawdzaj”. Metoda ta polega na przechodzeniu kolejnych elementów ciągu i porównywaniu ich ze wzorcem elementu poszukiwanego. Po natrafieniu na odpowiedni element zostaje on wypisany.

Do góry