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


100

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?

Odpowiedzi:


137

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 .

wprowadź opis obrazu tutaj

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
}

3
A co z nierekurencyjnymi przemierzaniami? Wydaje mi się, że przeglądanie drzewa nierekurencyjnie w kolejności pre-order jest znacznie łatwiejsze w porównaniu do in-order / post-order, ponieważ nie wymaga powrotu do poprzednich węzłów.
bluenote10

@ bluenote10 Czy możesz wyjaśnić, co masz na myśli? W przedsprzedaży nadal „powracasz” do węzła, aby przetworzyć jego prawe dziecko po przetworzeniu jego lewego dziecka. Jasne, możesz użyć kolejki „węzłów jeszcze nie odwiedzonych”, ale tak naprawdę jest to po prostu zamiana niejawnego (stosu) magazynu na jawną kolejkę. We wszystkich metodach przechodzenia muszą zostać przetworzone zarówno lewe, jak i prawe dzieci, co oznacza, że ​​po wykonaniu jednej z nich należy „powrócić” do rodzica.
Joshua Taylor

@JoshuaTaylor: Tak, wszystkie są tej samej klasy złożoności, ale jeśli spojrzysz na typowe implementacje, post-order jest prawdopodobnie nieco trudniejszy.
bluenote10

2
Trawers zamówiony w przedsprzedaży podaje wartości węzłów w kolejności wstawiania. Jeśli chcesz utworzyć kopię drzewa, musisz w ten sposób przejść przez drzewo źródłowe. Ciąg poligonowy w kolejności podaje posortowane wartości węzłów. Jeśli chodzi o trawers po zamówieniu, możesz użyć tej metody do usunięcia całego drzewa, ponieważ najpierw odwiedza węzły liści.
albin

Myślę, że to prawda, nawet jeśli drzewo nie jest prawidłowo uporządkowane, to znaczy w kolejności nie dałoby posortowanej kolejności, jeśli sekwencja nie została posortowana na początku.
CodeYogi

31

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


2
to świetna, zwięzła odpowiedź, która pomogła mi zrozumieć przypadki użycia przed i po zamówieniu. chociaż może być oczywiste, biorąc pod uwagę, że w pytaniu wspomniano o tym bezpośrednio, ale należy zauważyć, że dotyczy to binarnych drzew SEARCH i niekoniecznie sprawdza się w przypadku ogólnych drzew binarnych. na przykład nie można koniecznie używać funkcji przechodzenia w przedsprzedaży do kopiowania ogólnego drzewa binarnego, ponieważ logika wstawiania podczas procesu kopiowania nie zadziała.
markckim

7
W kolejności:: Aby uzyskać wartości węzła w kolejności „nie malejącej” - nie „nie rosnącej”
rahil008

26

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

4
Lub w TreeViewkomponencie aplikacji GUI.
svick

4

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


1
Myślę, że próbujesz powiedzieć coś ważnego, czy możesz wyjaśnić pierwszą połowę?
CodeYogi,

@CodeYogi Czego konkretnie potrzebujesz wyjaśnienia?
Raphael

1
„Zlecenie przed i po kolejności odnoszą się do algorytmów rekurencyjnych odgórnych i oddolnych”. Myślę, że chcesz powiedzieć, że w pierwszym przypadku węzeł jest przetwarzany przed wywołaniem którejkolwiek z metod rekurencyjnych i odwrotnie w drugim, prawda ?
CodeYogi

@CodeYogi Tak, w zasadzie.
Raphael

2

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 .

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.