Kapan menggunakan strategi Preorder, Postorder, dan Inorder Binary Search Tree Traversal

Baru-baru ini saya menyadari bahwa meskipun telah menggunakan banyak BST dalam hidup saya, saya bahkan tidak pernah berpikir untuk menggunakan apa pun selain Inorder traversal (sementara saya sadar dan tahu betapa mudahnya mengadaptasi program untuk menggunakan pre / post-order traversal).

Setelah menyadari hal ini, saya mengeluarkan beberapa buku teks struktur data lama saya dan mencari alasan di balik kegunaan traversal pre-order dan post-order - mereka tidak banyak bicara.

Apa sajakah contoh kapan harus menggunakan praorder / postorder secara praktis? Kapan lebih masuk akal daripada berurutan?

Kapan menggunakan Strategi Traversal Pre-Order, In-Order, dan Post-Order

Sebelum Anda dapat memahami dalam situasi apa menggunakan pre-order, in-order dan post-order untuk pohon biner, Anda harus memahami dengan tepat bagaimana setiap strategi traversal bekerja. Gunakan pohon berikut sebagai contoh.

Akar pohon adalah 7 , simpul paling kiri 0 , simpul paling kanan 10 .

Traversal praorder :

Ringkasan: Dimulai di root ( 7 ), berakhir di node paling kanan ( 10 )

Urutan traversal: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Traversal berurutan :

Ringkasan: Dimulai di simpul paling kiri ( 0 ), berakhir di simpul paling kanan ( 10 )

Urutan Traversal: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Traversal pasca-pesanan :

Ringkasan: Diawali dengan simpul paling kiri ( 0 ), diakhiri dengan akar ( 7 )

Urutan traversal: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Kapan menggunakan Pre-Order, In-order atau Post-Order?

Strategi traversal yang dipilih programmer bergantung pada kebutuhan spesifik dari algoritma yang sedang dirancang. Tujuannya adalah kecepatan, jadi pilihlah strategi yang memberi Anda node yang paling cepat Anda butuhkan.

1. Jika Anda tahu bahwa Anda perlu menjelajahi akar sebelum memeriksa daun apa pun, Anda memilih pemesanan di muka karena Anda akan menemukan semua akar sebelum semua daun.

2. Jika Anda tahu Anda perlu menjelajahi semua daun sebelum ada node, Anda memilih pasca-pemesanan karena Anda tidak membuang waktu memeriksa akar untuk mencari daun.

3. Jika Anda mengetahui bahwa pohon memiliki urutan yang melekat di node, dan Anda ingin meratakan pohon kembali ke urutan aslinya, sebaiknya gunakan traversal berurutan . Pohon itu akan diratakan dengan cara yang sama seperti saat dibuat. Traversal pre-order atau post-order mungkin tidak melepaskan pohon kembali ke urutan yang digunakan untuk membuatnya.

Algoritma Rekursif untuk Pre-order, In-order dan Post-order (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
}

Pre-order: Digunakan untuk membuat salinan pohon. Misalnya, jika Anda ingin membuat replika pohon, letakkan node dalam array dengan traversal pre-order. Kemudian lakukan operasi Sisipkan pada pohon baru untuk setiap nilai dalam larik. Anda akan mendapatkan salinan dari pohon asli Anda.

In-order:: Digunakan untuk mendapatkan nilai node dalam urutan non-penurunan dalam BST.

Post-order:: Digunakan untuk menghapus pohon dari daun ke akar

Jika saya hanya ingin mencetak format hierarki pohon dalam format linier, saya mungkin akan menggunakan preorder traversal. Sebagai contoh:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

Pre- dan post-order masing-masing berhubungan dengan algoritma rekursif top-down dan bottom-up. Jika Anda ingin menulis algoritme rekursif tertentu pada pohon biner secara berulang, inilah yang pada dasarnya akan Anda lakukan.

Amati lebih lanjut bahwa urutan sebelum dan sesudah pesanan bersama-sama secara lengkap menentukan pohon yang ada, menghasilkan pengkodean yang ringkas (setidaknya untuk pohon yang jarang).

Ada banyak tempat di mana Anda melihat perbedaan ini memainkan peran nyata.

Salah satu yang hebat yang akan saya tunjukkan adalah dalam pembuatan kode untuk kompiler. Pertimbangkan pernyataannya:

x := y + 32

Cara Anda menghasilkan kode untuk itu adalah (secara naif, tentu saja) pertama-tama menghasilkan kode untuk memuat y ke dalam register, memuat 32 ke dalam register, dan kemudian membuat instruksi untuk menambahkan keduanya. Karena sesuatu harus ada dalam register sebelum Anda memanipulasinya (anggap saja, Anda selalu dapat melakukan operan konstan tetapi apa pun) Anda harus melakukannya dengan cara ini.

Secara umum, jawaban yang Anda dapatkan untuk pertanyaan ini pada dasarnya direduksi menjadi ini: perbedaan sangat penting ketika ada beberapa ketergantungan antara pemrosesan bagian yang berbeda dari struktur data. Anda melihat ini saat mencetak elemen, saat membuat kode (keadaan eksternal membuat perbedaan, Anda juga dapat melihatnya secara monadik, tentu saja), atau saat melakukan jenis penghitungan lain di atas struktur yang melibatkan penghitungan bergantung pada turunan yang diproses terlebih dahulu .