Kiedy używać strategii przechodzenia po drzewie wyszukiwania binarnego przed zamówieniem, zamówieniem pocztowym i wyszukiwania binarnego

Niedawno zdałem sobie sprawę, że chociaż w moim życiu dużo korzystałem z BST, nigdy nawet nie rozważałem używania czegoś innego niż przechodzenie Inorder (chociaż jestem świadomy i wiem, jak łatwo jest dostosować program do przechodzenia przed / po zamówieniu).

Uświadomiwszy sobie to, wyciągnąłem niektóre z moich starych podręczników do struktur danych i szukałem uzasadnienia przydatności przechodzenia przed zamówieniem i po jego zamówieniu - nie mówili jednak zbyt wiele.

Jakie są przykłady, kiedy praktycznie korzystać z przedsprzedaży / zamówienia pocztowego? Kiedy ma to większy sens niż w porządku?

Kiedy używać strategii przemierzania zamówień przedpremierowych, na zamówienie i po zamówieniu

Zanim zrozumiesz, w jakich okolicznościach użyć zamówienia przedprzedażowego, na zamówienie i po zamówieniu dla drzewa binarnego, musisz dokładnie zrozumieć, jak działa każda strategia przechodzenia. Użyj poniższego drzewa jako przykładu.

Korzeń drzewa to 7 , skrajny lewy węzeł to 0 , skrajny prawy węzeł to 10 .

Przechodzenie w przedsprzedaży :

Podsumowanie: Zaczyna się od korzenia ( 7 ), kończy się w prawym węźle ( 10 )

Sekwencja przejścia: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Przechodzenie w kolejności :

Podsumowanie: zaczyna się w węźle położonym najbardziej po lewej stronie ( 0 ), kończy się w węźle najbardziej po prawej ( 10 )

Sekwencja przejścia: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Przechodzenie po zamówieniu :

Podsumowanie: Zaczyna się od węzła znajdującego się najbardziej po lewej stronie ( 0 ), kończy się na korzeniu ( 7 )

Sekwencja przejścia: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Kiedy korzystać z opcji zamówienia przedpremierowego, na zamówienie lub po zamówieniu?

Strategia przejścia wybrana przez programistę zależy od specyficznych potrzeb projektowanego algorytmu. Celem jest szybkość, więc wybierz strategię, która najszybciej dostarczy Ci węzły, których potrzebujesz.

1. Jeśli wiesz, że musisz zbadać korzenie przed sprawdzeniem jakichkolwiek liści, wybierasz zamówienie w przedsprzedaży, ponieważ napotkasz wszystkie korzenie przed wszystkimi liśćmi.

2. Jeśli wiesz, że musisz zbadać wszystkie liście przed jakimikolwiek węzłami, wybierasz zamówienie końcowe , ponieważ nie marnujesz czasu na sprawdzanie korzeni w poszukiwaniu liści.

3. Jeśli wiesz, że drzewo ma nieodłączną sekwencję w węzłach i chcesz spłaszczyć drzewo z powrotem do jego pierwotnej sekwencji, należy użyć przechodzenia w kolejności . Drzewo zostanie spłaszczone w ten sam sposób, w jaki zostało utworzone. Przechodzenie przed lub po zamówieniu może nie spowodować powrotu drzewa do sekwencji, która została użyta do jego utworzenia.

Algorytmy rekurencyjne dla zamówień w przedsprzedaży, na zamówienie i na zamówienie (C ++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

Przedsprzedaż: Służy do tworzenia kopii drzewa. Na przykład, jeśli chcesz utworzyć replikę drzewa, umieść węzły w tablicy z przemierzaniem w przedsprzedaży. Następnie wykonaj operację wstawiania na nowym drzewie dla każdej wartości w tablicy. Otrzymasz kopię swojego oryginalnego drzewa.

W kolejności:: Służy do pobierania wartości węzłów w kolejności nie malejącej w BST.

Post-order:: Używany do usuwania drzewa od liścia do korzenia

Gdybym chciał po prostu wydrukować hierarchiczny format drzewa w formacie liniowym, prawdopodobnie użyłbym przechodzenia przed zamówieniem. Na przykład:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

Zamówienia przed i po kolejności odnoszą się odpowiednio do algorytmów rekurencyjnych odgórnych i oddolnych. Jeśli chcesz napisać dany algorytm rekurencyjny na drzewach binarnych w sposób iteracyjny, to zasadniczo będziesz to robić.

Zauważ ponadto, że sekwencje przed i po zamówieniu razem całkowicie określają dostępne drzewo, dając zwarte kodowanie (przynajmniej dla rzadkich drzew).

Jest mnóstwo miejsc, w których widzisz, że ta różnica odgrywa prawdziwą rolę.

Jedną świetną rzeczą, na którą zwrócę uwagę, jest generowanie kodu dla kompilatora. Rozważ stwierdzenie:

x := y + 32

Sposób generowania kodu do tego polega (oczywiście naiwnie), aby najpierw wygenerować kod w celu załadowania y do rejestru, załadowania 32 do rejestru, a następnie wygenerowania instrukcji dodania dwóch. Ponieważ coś musi znajdować się w rejestrze, zanim nim zaczniesz manipulować (załóżmy, że zawsze możesz zrobić stałe operandy, ale cokolwiek), musisz to zrobić w ten sposób.

Ogólnie rzecz biorąc, odpowiedzi, które można uzyskać na to pytanie, sprowadzają się w zasadzie do tego: różnica naprawdę ma znaczenie, gdy istnieje pewna zależność między przetwarzaniem różnych części struktury danych. Widzisz to podczas drukowania elementów, podczas generowania kodu (stan zewnętrzny robi różnicę, możesz to oczywiście wyświetlać monadycznie, oczywiście) lub podczas wykonywania innych typów obliczeń na strukturze, które obejmują obliczenia w zależności od przetwarzanych elementów potomnych .