POHON (TREE)

DEFINISI POHON

Pohon (Tree) bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul).

Tingkat yang tertinggi disebut juga sebagai root.

Gambar Contoh pohon (tree) dengan 15 simpul

DEFINISI POHON

Simpul (node atau vertex) adalah elemen pohon yang berisi informasi / data dan petunjuk percabangan.

Tingkat (level) suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1.

Derajat (degree) dari suatu simpul dinyatakan sebagai banyaknya anak atau turunan dari simpul tersebut.

Simpul-simpul F, H, I, J, K, L, N, O yang semuanya berderajat nol, disebut dengan daun (leaf).

Tinggi (Height) atau Kedalaman (Depth) dari suatu pohon adalah tingkat maksimum dari suatu pohon dikurangi dengan satu

Hutan (Forest) adalah kumpulan sejumlah pohon yang tidak saling berhubungan

POHON BINER (BINARY TREE)

Pohon biner bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah

Subpohon disebut juga sebagai cabang Pengertian daun, akar, level, tinggi dan

derajat yang berlaku pada pohon juga berlaku pada binary tree.

Penyajian binary tree pada komputer digunakan double linked list.

DEKLARASI POHON BINER

DEKLARASI POHON BINER

Gambar Penyajian Pohon Biner dengan Double Linked List

MEMBUAT POHON BINER

Untuk membuat pohon biner, terdapat aturan dalam penempatan simpulnya.

Berikut ini algoritma penempatan sebuah simpul dalam pohon biner :“Simpul yang berisi informasi yang nilainya lebih besar dari simpul diatasnya akan ditempatkan sebagai cabang kanan dan jika lebih kecil akan ditempatkan di cabang kiri.”

MEMBUAT POHON BINER

Gambar Pohon biner Untai

MEMBUAT POHON BINER

Karakter pertama ‘H’ ditempatkan sebagai Akar. Karakter ‘K’ karena lebih besar dari ‘H’ diletakkan dicabang kanan. Karakter ‘A’ karena lebih kecil dari ‘H’ akan menempati cabang kiri dari ‘H’. kemudian, karena karakter ‘C’ lebih kecil dari ‘H’ dan lebih besar dari ‘A’ maka ia di letakkan sebagai cabang kanan dari ‘A’. Demikian seterusnya sampai semua masukkan di proses.

KUNJUNGAN PADA POHON BINER

Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali.

Terdapat tiga jenis kunjungan pada pohon biner, yaitu : PreOrder InOrder PostOrder

KUNJUNGAN PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut : Cetak isi simpul yang dikunjungi. Kunjungi cabang kiri. Kunjungi cabang kanan.

Dari gambar pohon biner untai, jika melakukan traversal secara PreOrder, maka akan menghasilkan untai : ‘HACBKJL’.

KUNJUNGAN INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut : Kunjungi cabang kiri. Cetak isi simpul yang dikunjungi. Kunjungi cabang kanan.

Dari gambar pohon biner untai, jika melakukan traversal secara InOrder, maka akan menghasilkan untai : ‘ABCHJKL’.

KUNJUNGAN POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut : Kunjungi cabang kiri. Kunjungi cabang kanan. Cetak isi simpul yang dikunjungi.

Dari gambar pohon biner untai, jika melakukan travarsal secara PostOrder, maka akan menghasilkan untai : ‘BCAJLKH’.

KUNJUNGAN PADA POHON BINER

Dalam pengembangan nantinya, tiga jenis kunjungan ini dapat digunakan sebagai pencarian notasi infix, postfix dan prefix. Kunjungan Preorder untuk mencari prefix Kunjungan Inorder untuk mencari infix Kunjungan Postorder untuk mencari

postfix.