Question

Binary Tree

Himpunan key berikut ini disisipkan ke dalam suatu binary tree:
{5, 3, 2, 7, 4, 6, 8}

Gambarkanlah struktur binary tree tersebut, dan jabarkan penelusuran node (traversal) secara preorder, inorder, dan postorder.
​

Answer 1

Gambar struktur binary tree:

Traversal:

• Preorder: 5 3 2 4 7 6 8
• Inorder: 2 3 4 5 6 7 8
• Postorder: 2 4 3 6 8 7 5

 

Pembahasan

Proses pembentukan binary tree

Pada jawaban ini, saya kembali menggunakan skema binary sorted tree, di mana node yang lebih kecil nilainya ditempatkan pada subtree kiri, dan node yang lebih besar nilainya ditempatkan pada subtree kanan.

Himpunan key: {5, 3, 2, 7, 4, 6, 8}
Kondisi inisial: Tree masih kosong.

1. Key 5 disisipkan. Node 5 menjadi root dari keseluruhan tree.
2. Key 3 disisipkan. Karena 3 < 5, maka 3 ditempatkan pada subtree kiri dari node 5.
   
3. Key 2 disisipkan. Karena 2 < 3 < 5, maka 2 ditempatkan pada subtree kiri dari node 3.
   
4. Key 7 disisipkan. Karena 7 > 5, maka 7 ditempatkan pada subtree kanan dari node 5.
   
5. Key 4 disisipkan. Karena 4 < 5 dan 4 > 3, maka 4 ditempatkan pada subtree kanan dari node 3.
   
6. Key 6 disisipkan. Karena 6 < 7 dan 6 > 5, maka 6 ditempatkan pada subtree kiri dari node 7.
   
7. Key 8 disisipkan. Karena 8 > 7, maka 8 ditempatkan sebagai subtree kanan dari node 7.
   

Selesai.

Traversal

• Traversal Preorder (Node, Left, Right)
  ⇒ 5 3 2 4 7 6 8
• Traversal Inorder (Left, Node, Right)
  ⇒ 2 3 4 5 6 7 8
• Traversal Postorder (Left, Right, Node)
  ⇒ 2 4 3 6 8 7 5