Apakah traversal Pre-Order sama dengan Depth First Search?

13

Bagi saya sepertinya pre-order traversal dan DFS sama seperti pada kedua kasus yang kami lintasi dari root sampai cabang kiri dan kembali ke root dan kemudian ke cabang kanan secara rekursif. Bisakah ada yang memperbaiki saya jika saya salah?

Terima kasih sebelumnya!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
sumber

Jawaban:

10

pre order traversal adalah traversal, ia mengunjungi setiap node dalam pohon biner

Depth First Search adalah pencarian, ini berjalan di sekitar grafik sembarang mencari simpul tertentu (yang berfungsi terbaik dalam grafik non-siklik (alias pohon) tidak relevan)

ini saja perbedaan yang cukup besar untuk memanggil mereka nama perbedaan

aneh ratchet
sumber
1
+1, tetapi saya ingin menambahkan bahwa traversal pre-and post-order hanyalah kasus khusus dari strategi DFS yang lebih umum.
Frank
1
Bukankah traversal pre-order hanya berarti memproses node sebelum anak-anak mereka? Di mana dikatakan bahwa node membentuk pohon biner, atau bahkan pohon?
Kilian Foth
@KilianFoth Saya akan mengharapkan implikasi dari simpul yang memiliki anak (bukan tetangga) untuk menyiratkan struktur pohon karena itu menunjukkan hierarki node. Bagian atas hierarki menjadi akar pohon. Tapi saya bisa membayangkan traversal pre-order dan traversal post-order masuk akal pada pohon apa pun, bahkan pohon yang bukan biner.
YoungJohn
1

Ya, tetapi harus sebaliknya: DFSmirip dengan PreOrder.
Istilah PreOrderini lebih relevan untuk pohon biner dan parser.
Hal ini digunakan untuk membandingkan dengan perintah traversal lain dari pohon biner: InOrder, PostOrderdan PreOrder.
Sortasi Topologis mirip dengan traversal Post Order (dorong node ke stack setelah mengunjungi semua node yang berdekatan).

pengguna640554
sumber
Pikiranku mirip dengan jawaban ini. Lebih khusus, pre-order adalah implementasi spesifik dari kategori induk DFS. Pre-order child traversal adalah kiri kiri kemudian kanan; sedangkan untuk DFS generik (orang tua), urutan traversal anak-anak tidak ditentukan dan dapat berupa urutan apa pun.
Jerred S.
-1

Untuk melintasi pohon biner di Preorder, operasi berikut dilakukan

  1. Kunjungi root
  2. Lintasi subtree kiri
  3. Lintasi subtree kanan

Yaitu pada gambar di bawah ini traversal pre order akan menjadi, 1,2,3,6,4,5,7,8,9,10,11,12

Dalam gambar yang sama 1,2,3,4,5,6,7,8,9,10,11,12 akan untuk DFS

Sumber DFS: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Sumber Pre Order: Wiki

DFS

Zedaiq
sumber
9
Ini bukan pohon biner. Itu pohon, tapi bukan biner.
Manoj R
Apa yang terjadi ketika "6" memiliki sub node?
Marjan Venema
Anda meminta DFS atau pre order?
Zedaiq
@ ManojR Mengerti dari sumber yang disebutkan di atas.
Zedaiq
pre order dalam grafik ini memberikan jawaban yang sama
Charles Chow