Penjelasan Binary Tree

    

      Gambar diatas merupakan sebuah Tree dari sekumpulan node. Untuk mencari rute dari tree, digunakan 3 cara, yaitu preorder, inorder, dan postorder. Berikut ini adalah penjelasan untuk mencari rute dari 3 cara tersebut :

Preorder (Root – Left – Right)

     Untuk mencari rute dengan cara preorder, kita harus pahami rumusnya, yaitu Root -  Left – Right. Root adalah node yang memiliki cabang dibawah nya, Left adalah cabang yang ada di sebelah kiri root dan Right adalah cabang yang ada di sebelah kanan root. Untuk menentukan rute kita ambil node paling teratas.

1.     pada gambar diatas node teratas adalah 7. Karena 7 merupakan root kita tulis di dalam rute.

2.     setelah itu ambil angka 3 yang merupakan cabang node 7 yang berada disebelah kiri. Karena 3 merupakan root kita tulis ke dalam rute.

3.     Lalu, ambil left dari node 3, yaitu node 1. Node 1 merupakan root, kita tulis di dalam rute.

4.     Ambil left dari node 1, yaitu node 0. Node 0 bukan root jadi kita tulis di dalam rute.

5.     Kembali lagi ke node 1, karena node 1 dan left nya sudah di tulis di dalam rute, kita ambil right dari node 1, yaitu node 2. Karena node 2 bukan root jadi kita tullis di dalam rute.

6.     Kembali lagi ke node 3, karena node 3 dan leftnya telah di tulis di dalam rute, kita ambil right dari node 3, yaitu node 6. Karena node 6 merupakan root jadi kita tulis di dalam rute.

7.     Node 6 masih memiliki left lalu kita ambil node 4. Karena node 4 merupakan root jadi kita tulis di dalam rute.

8.     Node 4 tidak memiliki left, tetapi memiliki right, yaitu node 5 lalu, kita ambil 5. Karena node 5 bukan root jadi kita tulis di dalam rute.

9.     Kembali lagi ke node 7, karena node 7 tidak memiliki left lagi jadi kita ambil right nya, yaitu node 12.

10.  Karena node 12 merupakan root, jadi kita tulis di dalam rute. Node 12 masih memiliki left, jadi kita ambil node 9. Node 9 merupakan root jadi kita tulis di dalam rute.

11.  Karena node 9 memiliki left jadi kita ambil node 8. Karena node 8 bukan root jadi kita tulis di dalam rute.

12.  Kembali lagi ke node 9, karena node 9 tidak memiliki node kita ambil right nya yaitu node 11. Node 11 merupakan root jadi kita tulis di dalam rute.

13.  Karena node 11 memiliki left, jadi kita ambil node 10 dan node 10 bukan root jadi kita tulis di dalam rute.

14.  Kembali lagi ke node 12, karena node 12 tidak memiliki left jadi kita ambil right nya yaitu node 13. Karena node 13 merupakan root jadi kita tulis di dalam rute.

15.  Node 13 tidak memiliki left jadi kita ambil right nya yaitu node 15. Karena node 15 merupakan root jadi kita tulis  di dalam rute.

16.  Node 15 masih memiliki left jadi kita ambil node 14 dan node 14 bukan root jadi kita tulis di dalam rute.

Sehingga hasil rute seperti berikut ini :  7-3-1-0-2-6-4-5-12-9-8-11-10-13-15-14

Inorder (Left – Root – Right)

     Untuk mencari rute dengan cara inorder, kita harus pahami rumusnya, yaitu Left -  Root – Right. Left adalah cabang yang ada di sebelah kiri root, Root adalah node yang memiliki cabang dibawah nya dan Right adalah cabang yang ada di sebelah kanan root. Untuk menentukan rute kita ambil node paling teratas.

1.     Node 7 memiliki left yaitu node 3, node 3 memiliki left yaitu node 1, node 1 memiliki left yaitu node 0, node 0 bukan root jadi kita tulis di dalam rute.

2.     Kembali lagi ke node 1, node 1sudah tidak memiliki left, tetapi dia merupakan root jadi kita tulis di dalam rute.

3.     Node 1 masih memiliki right yaitu node 2 jadi kita tulis di dalam rute.

4.     Kembali lagi ke node 3, node 3 tidak memiliki left lagi, tetapi dia merupakan root jadi kita tulis di dalam rute.

5.     Node 3 masih memiliki right yaitu node 6. Node 6 memiliki left yaitu node 4, node 4 tidak memilki left, tetapi node 4 merupakan root jadi kita tulis di dalam rute.

6.     Node 4 masih memiliki right, yaitu node 5 jadi kita tulis di dalam rute.

7.     Kembali lagi ke node 6, node 6 tidak memiliki left tetapi node 6 merupakan root jadi kita tulis di dalam rute.

8.     Kembali lagi ke node 7, node 7 tidak memiliki left tetapi node 7 merupakan root jadi kita tulis di dalam rute.

9.     Node 7 memiliki right yaitu node 12, node 12 memiliki left yaitu node 9, node 9 memiliki left yaitu node 8, node 8 bukan root jadi kita tulis di dalam rute.

10.  Kembali lagi ke node 9, node 9 merupakan root jadi kita tulis di dalam rute.

11.  Node 9 masih memiiki right yaitu node 11, node 11 memiliki left yaitu node 10, node 10 bukan root jadi kita tulis di dalam rute.

12.  Kembali lagi ke node 11, node 11 merupakan root jadi kita tulis di dalam rute.

13.  Kembali lagi ke node 12, node 12 merupakan root jadi kita tulis di dalam rute.

14.  Node 12 memiliki right, yaitu node 13. Node 13 merupakan root jadi kita tulis di dalam rute.

15.  Node 13 memiliki right yaitu node 15, node 15 memiliki left yaitu node 14. Node 14 bukan root jadi kita tulis di dalam rute.

16.  Kembali lagi ke node 15, node 15 merupakan root jadi kita tulis di dalam rute.

Sehingga hasil rute seperti berikut ini :  0-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15

Postorder (Left – Right – Root)

     Untuk mencari rute dengan cara postorder, kita harus pahami rumusnya, yaitu Left -  Right – Root. Left adalah cabang yang ada di sebelah kiri root, Right adalah cabang yang ada di sebelah kanan root dan Root adalah node yang memiliki cabang dibawah nya. Untuk menentukan rute kita ambil node paling teratas.

1.     Node 7 memiliki left yaitu node 3, node 3 memiliki left yaitu node 1 dan node 1 memiliki left yaitu node 0. Node 0 bukan root jadi kita tuliskan di dalam rute.

2.     Kembali lagi ke node 1, node 1 memiliki right yaitu node 2 jadi kita tuliskan di dalam rute.

3.     kembali lagi node 1, node 1 tidak memiliki left dan right, tetapi node 1 merupakan root jadi kita tuliskan di dalam rute

4.     kembali lagi ke node 3, node 3 tidak memiliki left tetapi masih memiliki right yaitu node 6. Node 6 memiliki left yaitu node 4, node 4 memiliki right yaitu node 5. Node 5 bukan root jadi kita tuliskan di dalam rute

5.     kembali lagi ke node 4, node 4 tidak memiliki left dan right tetapi node 4 merupakan root jadi kita tuliskan di dalam rute.

6.     Kembali ke node 6, node 6 tidak memiliki left dan right tetapi node 6 merupakan root jadi kita tuliskan di dalam rute.

7.     kembali lagi ke node 3, node 3 tidak memiliki left dan right tetapi node 3 merupakan root jadi kita tuliskan di dalam rute.

8.     Kembali lagi ke node 7, node 7 masih memiliki right yaitu node 12. Node 12 memiliki left yaitu node 9. Node 9 memiliki left yaitu node 8, node 8 bukan root jadi kita tuliskan di dalam rute.

9.     Kembali lagi ke node 9, node 9 memiliki right node 11. Node 11 memiliki left yaitu node 10, node 10 bukan root jadi kita tuliskan di dalam rute.

10.  Kembali lagi ke node 11, node 11 tidak memiliki left dan right tetapi node 11 merupakan root jadi kita tuliskan di dalam rute.

11.  Kembali lagi ke node 9, node 9 tidak memiliki left dan right tetapi node 9 merupakan root jadi kita tuliskan di dalam rute.

12.  Kembali lagi ke node 12, node 12 memiliki right yaitu node13. Node 13 memiliki right yaitu node 15. Node 15 memiliki left yaitu node 14, karena node 14 bukan root jadi kita tuliskan di dalam rute.

13.  Kembali lagi ke node 15, node 15 merupakan root jadi kita tuliskan di dalam rute.

14.  Kembali lagi ke node 13, node 13 merupakan root jadi kita tuliskan di dalam rute.

15.  Kembali lagi ke node 12, node 12 merupakan root jadi kita tuliskan di dalam rute.

16.  Kembali lagi ke node 7, node 7 merupakan root jadi kita tuliskan di dalam rute.

Sehingga hasil rute seperti berikut ini :  0-2-1-5-4-6-3-8-10-11-9-14-15-13-12-7