Materi Kunjungan Pohon Biner

Kunjungan pada pohon biner merupakan salah satu operasi yang sering dilakukan pada suatu pohon biner tepat satu kali ( Binary Tree Traversal ).

Ada tida macam operasi kunjungan pada pohon biner, yaitu Kunjungan secara PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.

1. Kunjungan secara Preorder ( Depth First Order ).

Urutan :
a.Cetak isi simpul yang dikunjungi ( simpul akar )
b.Kunjungi Cabang kiri
c.Kunjungi Cabang kanan

Prosedur kunjungan secara PreOrder dapat dilakukan dengan cara rekursif atau non
rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini :
Procedure PreOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
Write (Root^.Info);
PreOrder (Root^.kiri);
PreOrder (Root^.kanan);
End;
End;

2. Kunjungan secara Inorder ( Symetric Order )

Urutan :
a.Kunjungi Cabang kiri
b.Cetak isi simpul yang di kunjungi ( simpul akar )
c.Kunjungi Cabang kanan

Seperti pada kunjungan secara PreOrder, prosedur kunjungan secara InOrder dapat dilakukan
dengan cara rekursif atau non rekursif. Prosedur kunjungan secara InOrder LRO dengan
rekursif disajikan berikut ini :
Procedure InOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
InOrder (Root^.kiri);
Write (Root^.Info);
InOrder (Root^.kanan);
End;
End;

3. Kunjungan secara Postorder

Urutan :
a.Kunjungi Cabang kiri
b.Kunjungi Cabang kanan
c.Cetak isi simpul yang dikunjungi ( simpul akar )

Seperti halnya PreOrde dan InOrder, prosedur kunjungan secara PostOrder juga dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini :
Procedure PostOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
PostOrder (Root^.kiri);
PostOrder (Root^.kanan);
Write (Root^.Info);
End;
End;

* Pada ketiga cara kunjungan diatas, kunjungan ke

Cabang Kiri dilakukan terlebih dahulu, baru kemudian

kunjungan ke Cabang Kanan. Dengan orientasi

semacam ini, Ketiga kunjungan diatas disebut dengan

Left To Right Oriented (LRO). 

Jika kunjungan ke Cabang Kanan dilakukan lebih

dahulu baru kemudian kunjungan ke Cabang Kiri, maka

Orientasi semacam ini disebut Right To Left Oriented

(RLO).

Contoh:

1.)  12 , 22 , 8 , 19 , 10 , 9 , 20 , 4 , 2 , 6

2.)  2 , 3 , 4 , 5 , 50 , 10 , 15 , 13 , 20 , 12 , 10 , 7

3.)  7 , 13 , 4 , 6 , 5 , 9 , 15 , 20 , 60 , 14 , 40 , 70

4.)  50 , 45 , 55 , 41 , 49 , 13 , 60 , 70 , 40 , 35 , 30 , 20 , 80 , 75 , 85

5.)  12 , 19 , 11 , 17 , 29 , 21 , 20 , 22 , 13 , 14 , 18 , 16 , 15