Struktur Data - Tree Traversal

Ada berbagai strategi yang dapat digunakan untuk melintasi(traverse) items pada pohon struktur data; pilihan strategi tergantung pada urutan kunjungan node yang Anda butuhkan. Pada bagian ini kita akan menyentuh pada traversal yang diberikan Struktur Data Algoritma pada semua struktur data yang berasal dari Pohon Pencarian Biner

Ketika kita melihat list struktur data, traversal cukup mudah. Kita hanya perlu melalui list untuk memastikan melihat setiap elemen. Pohon tidak linear, jadi tidak ada jalan yang jelas untuk melintasi semuanya. Misalkan kita mulai di root, apakah kita pergi ke kiri dulu atau ke kanan dulu?

box1

Haruskah kita benar-benar melintasi satu subtree atau satu bagian dari pohon termasuk ‘parent’ dan semua turunannya atau melintasi semuanya pada tingkat yang sama terlebih dahulu? Traversal dalam pohon sedikit lebih rumit tetapi sama pentingnya. Kita tidak dapat mencari atau mengurutkan elemen kecuali memiliki cara untuk memastikan kita dapat mengunjungi semua elemen terlebih dahulu. Ada dua pendekatan luas yang berbeda untuk mengobati traversal. Salah satunya disebut pencarian kedalaman-pertama atau depth-first search (DFS) for short.

Di DFS, filosofinya adalah jika ada node children untuk dijelajahi, menjelajahi mereka pasti merupakan prioritas Alternatifnya disebut breadth-first search atau BFS. Di BFS, prioritasnya adalah mengunjungi setiap node pada tingkat yang sama dengan yang kita temui sebelum mengunjungi node children.

Begitupun dengan konvensi, kita mulai di sisi paling kiri dari level dan bergerak ke kanan. Traversal ini jelas merupakan BFS. Kita mengunjungi semua node pada tingkat yang sama sebelum pindah ke node children.

box2

Ada beberapa pendekatan berbeda untuk DFS dan pohon. Pertama, kita akan berbicara tentang traversal pre-order. Pra maksudnya, periksa simpul seperti yang Anda lihat sebelum Anda menjelajahi lebih jauh di pohon. Ada metode lain dari traversal di mana Anda memeriksa node setelah Anda melihat children. mereka.

Jadi aturan ini sangat penting untuk diingat. Kita mulai di rute dan segera periksa bahwa kita telah melihatnya. Selanjutnya, kita memilih salah satu dari children itu. Biasanya yang kiri dengan konvensi, dan periksa juga. Kita akan terus melintas di node paling kiri sampai kita memiliki ‘leaf’. Kita memeriksa ‘leaf’ dan dari sana kembali ke ‘parent’.

Sekarang kita bisa melintasi ke children yang tepat dan memeriksanya juga. Kita selesai dengan subtree ini, sehingga kita dapat kembali ke root dan melihat right children. Kita melakukan langkah yang sama sampai kita melihat semuanya.

Baik anda melihat gambar diatas. Ketika menggunakan algoritma preorder, Anda mengunjungi root (D) terlebih dahulu, kemudian melintasi subpohon kiri (B) kemudian turunannya subpohon kiri (A) dan akhirnya melintasi subpohon kanan ©. → D, B, A, C

Triknya di sini adalah kita bergerak melalui node dalam urutan yang sama, karena ini masih merupakan DFS dan kita perlu mengeksplorasi semua children terlebih dahulu. Sekali lagi, kita mulai di root, dari D → B → A. Kita harus terus menurun sampai kita menabrak leaf. Setelah memeriksa leaf dan naik ke parent (B). Kita beralih ke node kanan ini ©, yang tidak memiliki children, jadi kami dapat memeriksanya juga. Kemudain kembali ke root (D) dan mengulangi semua ini di sisi kanan sampai selesai. Mode ini pun juga disebut ‘in-order’, artinya menelusuri node sampai terakhir.

  • 1) algorithm Preorder(root)
  • 2) Pre: root adalah node root dari BST
  • 3) Post: node di BST telah dikunjungi di preorder
  • 4) if root = θ
  • 5) yield root.Value
  • 6) Preorder(root.Left)
  • 7) Preorder(root.Right)
  • 8) end if
  • 9) end Preorder

Kemudian kita memiliki post-order traversal. Kali ini kita tidak akan dapat memeriksa node sampai melihat semua keturunannya atau mengunjungi kedua children dan kembali. Langkah serupa, kita mulai di root, jangan dicentang, tetapi terus ke leaf.

Kita memeriksa leaf dan pindah ke parent. Kali ini kita tidak memeriksa parent, hanya melanjutkan ke node yang tepat. Setelah memeriksa children yang tepat, kita dapat kembali ke parent dan akhirnya memeriksanya juga.

Sekali lagi, kita akan melewati node root dan hanya memindahkan semua jalan ke bawah ke kanan. Begitu semuanya ada yang baik kita bisa pindah kembali ke root dan dapatkan.

box3

Algoritma ini sangat mirip dengan yang dijelaskan pada pre - order, namun nilainya dari node dihasilkan setelah melintasi kedua subpohon.

  • 1) algorithm Postorder(root)
  • 2) Pre: root adalah node root dari BST
  • 3) Post: node di BST telah dikunjungi di postorder
  • 4) if root = θ
  • 5) Postorder(root.Left)
  • 6) Postorder(root.Right)
  • 7) yield root.Value
  • 8) end if
  • 9) end Postorder