Kegunaan traversal pre dan post order pohon biner

13

Ini mungkin sangat naif, tapi saya bertanya-tanya, itu konteks pohon biner (polos, disortir dan seimbang), dari semua jenis traversal:

  • pre-order mendalam-pertama
  • mendalam-urutan pertama
  • kedalaman-urutan pertama pasca
  • luasnya dulu

apa kegunaan sebenarnya dari yang pre dan post-order? Maksud saya, apakah ada beberapa jenis dan / atau konfigurasi pohon biner di mana pre dan / atau post-order traversal akan memberikan (beberapa) keunggulan dibandingkan dua lainnya?

AFAICS, ada beberapa jenis dan konfigurasi pohon biner tertentu yang urutan-pertama dan lebarnya mungkin memberikan keuntungan tertentu:

  • untuk pohon biner seimbang setiap traversal first-first akan menggunakan lebih sedikit ruang penyimpanan memori dibandingkan dengan lebar pertama (mis. untuk pohon biner seimbang dari 6 atau 7 node, tingginya 2 sehingga traversal kedalaman-pertama mana pun perlu menyimpan maksimal 2 node pada waktu tertentu, sedangkan level terakhir memiliki 3 atau 4 node sehingga traversal-first perlu menyimpan hingga 3 atau 4 node di beberapa titik). Dalam hal ini menggunakan in-order traversal menggunakan jumlah memori paling sedikit dan mengunjungi node dalam urutan alami mereka.

  • untuk pohon biner yang tidak seimbang, jika dekat dengan skenario penyisipan kasus terburuk, melewatinya dengan lebar-pertama akan menggunakan lebih sedikit memori dibandingkan dengan lintas kedalaman-pertama. Jadi dalam hal ini luasnya menawarkan keuntungan. Inversal traversal memiliki lagi keuntungan dari nilai-nilai kunjungan dalam tatanan alami mereka.

Namun saya tidak bisa memikirkan situasi di mana pra dan pasca-traversal akan memberikan keuntungan daripada dua lainnya.

binary-tree graph-traversal Shivan Dragon
sumber

Jawaban:

13

Anda perlu melakukan berbagai hal dengan pohon, seperti menerjemahkan antara struktur data dan beberapa representasi serial, seperti pada file atau dalam bahasa.

Jadi, misalnya, misalkan Anda memiliki pohon parse seperti ini:

    *
   / \
  +   \
 / \   \
A   B   C

Anda bisa membuat serial sebagai * + A B Cdengan berjalan dalam urutan awalan, atau A B + C *dengan berjalan dalam urutan postfix. Jika Anda bekerja sama sekali dengan pengolah bahasa, hal-hal seperti itu harus bersifat alami.

Mike Dunlavey
sumber
Contoh yang sangat bagus! Dan perhatikan bagaimana in-order-traversal akan menghasilkan A + B * C, yang jauh lebih mudah dipahami untuk pengguna normal daripada awalan urutan postfix.
Kilian Foth
3
@KilianFoth kecuali bukan itu yang dikatakan pohon - katanya (A + B) * C, setidaknya di mata saya. Meskipun jari-jari HP-28 saya suka versi AB + C * baik-baik saja. :-)
sdg
@Kilian: sdg benar. Dengan inorder, Anda harus mementingkan prioritas, kecuali Anda menempatkan tanda kurung di sekitar segalanya.
Mike Dunlavey
13

The Artikel wikipedia memiliki deskripsi singkat baik ketika Anda ingin menggunakan berbagai jenis pencarian mendalam-pertama:

  • Pre-order traversal saat menduplikasi node dan nilai dapat membuat duplikat lengkap dari pohon biner. Itu juga dapat digunakan untuk membuat ekspresi awalan (notasi Polandia) dari pohon ekspresi: melintasi pohon ekspresi pre-orderly.
  • In-order traversal sangat umum digunakan pada pohon pencarian biner karena ia mengembalikan nilai dari set yang mendasarinya secara berurutan, menurut komparator yang mengatur pohon pencarian biner (karenanya namanya).
  • Travers post-order sambil menghapus atau membebaskan node dan nilai dapat menghapus atau membebaskan seluruh pohon biner. Itu juga dapat menghasilkan representasi postfix dari pohon biner.

Itu bermuara pada kebutuhan logistik suatu algoritma. Misalnya, jika Anda tidak menggunakan traversal post-order selama penghapusan, maka Anda kehilangan referensi yang Anda butuhkan untuk menghapus pohon anak.

Karl Bielefeldt
sumber
Wikipedia pada 10 November 2019 berubah dan deskripsi pertama juga menjadi milik Post-Order, yang membingungkan. Itulah alasan saya berakhir di sini, mencari sumber informasi lain.
whoan
5

Inti dari memiliki algoritma yang berbeda untuk menangani pohon biner bukanlah untuk melakukan sesuatu dengan pohon. Pada tingkat abstrak ini, sebagian besar urutan sama baiknya dengan yang lain, karena Anda hanya mendapatkan simbol abstrak dari prosedur.

Tetapi pohon biasanya digunakan untuk mewakili hal-hal yang menarik, dan itu dapat membuat perbedaan besar dalam hasilnya. Misalnya, jika node mewakili status pencarian dalam pencarian lengkap melalui domain besar (bahkan mungkin domain tak terbatas), menurun terlebih dahulu vs memproses terlebih dahulu tidak hanya menentukan urutan urutan hasil ditemukan, bahkan dapat menentukan apakah Anda akan pernah temukan solusi sama sekali . Poinnya paling mudah untuk dilihat dengan domain tak terbatas: jika Anda turun secara tidak hati-hati, Anda mungkin mengabaikan solusi yang terletak cukup tinggi di pohon, hanya karena Anda mengambil jalan yang salah. Tetapi dalam praktiknya, karena memori dan disk juga terbatas, ini bahkan berlaku untuk domain yang sangat besar daripada benar-benar tak terbatas.

Kilian Foth
sumber