Czy przejście do zamówienia w przedsprzedaży jest takie samo, jak Głębokie pierwsze wyszukiwanie?

13

Wydaje mi się, że przechodzenie w przedsprzedaży i DFS są takie same, jak w obu przypadkach przechodzimy od korzenia do lewej gałęzi i z powrotem do korzenia, a następnie rekurencyjnie do prawej gałęzi. Czy ktoś mógłby mnie poprawić, jeśli się mylę?

Z góry dziękuję!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
źródło

Odpowiedzi:

10

Traversal w przedsprzedaży to przejście, odwiedza każdy węzeł drzewa binarnego

Głębokie pierwsze wyszukiwanie jest wyszukiwaniem, omija dowolny wykres, szukając określonego węzła (że działa najlepiej na grafie niecyklicznym (inaczej drzewo) nie ma znaczenia)

sama ta różnica jest wystarczająco duża, aby nazwać je nazwami różnic

maniak zapadkowy
źródło
1
+1, ale chciałbym dodać, że przechodzenie przed i po zamówieniu to tylko szczególne przypadki bardziej ogólnej strategii DFS.
Frank
1
Czy podróż w przedsprzedaży nie oznacza po prostu przetwarzania węzłów przed dziećmi? Gdzie mówi się, że węzły tworzą drzewo binarne, a nawet drzewo?
Kilian Foth
@KilianFoth Spodziewałbym się, że implikacja węzła mającego dzieci (w przeciwieństwie do sąsiadów) implikuje strukturę drzewa, ponieważ sugeruje hierarchię węzłów. Szczyt hierarchii jest korzeniem drzewa. Ale mogę sobie wyobrazić przechodzenie przed zamówieniem i przechodzenie po zamówieniu, które ma sens na każdym drzewie, nawet tym, które nie są binarne.
YoungJohn
1

Tak, ale powinien być odwrotnie: DFSjest podobny do PreOrder.
Termin PreOrderjest bardziej odpowiedni dla drzew binarnych i parserów.
Stosuje się go porównać z innymi zleceń traversal binarnego drzewa: InOrder, PostOrderi PreOrder.
Sortowanie topologiczne jest podobne do przechodzenia po zamówieniu (wepchnij węzeł do stosu po wizycie na wszystkich sąsiednich węzłach).

użytkownik640554
źródło
Moje myśli są podobne do tej odpowiedzi. Mówiąc dokładniej, zamówienie w przedsprzedaży jest specyficzną implementacją nadrzędnej kategorii DFS. Przechodzenie dziecka w przedsprzedaży jest sztywno w lewo, a potem w prawo; podczas gdy w przypadku ogólnego (macierzystego) DFS kolejność przechodzenia dzieci nie jest zdefiniowana i może być dowolną kolejnością.
Jerred S.
-1

Aby przejść przez drzewo binarne w przedsprzedaży, wykonywane są następujące operacje

  1. Odwiedź root
  2. Przejdź przez lewe poddrzewo
  3. Przejdź przez prawe poddrzewo

To jest na poniższym obrazie, że przejście w przedsprzedaży byłoby 1,2,3,6,4,5,7,8,9,10,11,12

Na tym samym obrazie 1,2,3,4,5,6,7,8,9,10,11,12 byłoby dla DFS

Źródło DFS: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Przedsprzedaż Źródło: Wiki

DFS

Zedaiq
źródło
9
To nie jest drzewo binarne. To drzewo, ale nie binarne.
Manoj R
Co się stanie, gdy „6” ma podwęzły?
Marjan Venema
Pytasz o DFS lub zamówienie w przedsprzedaży?
Zedaiq
@ManojR Mam go ze źródła wspomnianego powyżej.
Zedaiq
przedsprzedaż na tym wykresie daje tę samą odpowiedź
Charles Chow