Binary Tree Traversal


Pengertian

  • Binary Tree

sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai sub pohon kiri (left subtree) dan sub pohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

  • Traversal

Traversal adalah proses kunjungan dalam pohon, dengan setiap node hanya dikunjungi tepat satu kali.

Jadi, binary tree traversal adalah proses mengunjungi node tepat satu kali dan tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai sub pohon kiri (left subtree) dan sub pohon kanan (right subtree).

Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree.

Algoritma Binary Tree Traversal secara umum

Tiga teknik rekursif untuk binary tree traversals ,yaitu:

  1. Mengunjungi simpul akar (root),
  2. Melakukan traversal subpohon kiri (left subtree), dan
  3. Melakukan traversal subpohon kanan (right subtree).

Yang membedakan antara teknik satu dengan yang lain adalah proses pengurutan tugas mereka.

Macam – macam Binary Tree Traversal

Terdapat tiga macam binary tree traversal, yaitu:

  • Preorder Traversal
  1. Mengunjungi simpul akar (root),
  2. Melakukan traversal subpohon kiri (left subtree),
  3. Melakukan traversal subpohon kanan (right subtree).
  • Inorder Traversal
  1. Melakukan traversal subpohon kiri (left subtree),
  2. Mengunjungi simpul akar (root),
  3. Melakukan traversal subpohon kanan (right subtree).
  • Postorder Traversal
  1. Melakukan traversal subpohon kiri (left subtree),
  2. Melakukan traversal subpohon kanan (right subtree),
  3. Mengunjungi simpul akar (root).
Iklan

tulis comment nya...

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s