Pertemuan 4 - Tree Structure - 2101711122 - Bela Kristianti

Dalam ilmu komputer, Tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon dan merupakan satu bentuk implementasi banyak linked list yang biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarki antara elemen-elemen yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

Node yang berada di pangkal tree disebut node root (akar), sedangkan node yang berada paling ujung pada piramida tree disebut node leaf (daun).

 

Terminologi dalam tree :

·     Node : Sebuah elemen dalam sebuah tree dan berisi sebuah informasi

·     Parent : Node yang berada di atas node lain secara langsung

·     Child : Cabang langsung dari sebuah node

·     Root : Node teratas yang tidak punya parent

·     Sibling : Sebuah node lain yang memiliki parent yang sama

·     Leaf : Sebuah node yang tidak memiliki children. Leaf biasa disebut sebagai external node, sedangkan node selainnya disebut sebagai internal node.

·     Level : Semua node yang memiliki jarak yang sama dari root.

·     Depth :  Jumlah level yang ada dalam tree

·     Complete : Semua parent memiliki children yang penuh

·     Balanced : Semua subtree memiliki depth yang sama

Binary Tree (Pohon Biner) adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak. Tidak boleh lebih. Pada pohon biner, umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan.

Beberapa istilah pada pohon biner:

·     Size (ukuran) : jumlah total node yang terdapat pada pohon biner tersebut.

·     Depth (kedalaman) : panjang jalur yang menghubungkan sebuah node sampai ke node anaknya yang paling ujung (leaf). Depth biasa juga disebut height.

Sebuah binary tree adalah tree kosong atau terdiri dari sebuah node dengan dua buah sub tree (kiri dan kanan) yang masing-masing adalah tree juga. Algoritma untuk Binary Tree akan lebih mudah dinyatakan secara rekursif. Binary tree memiliki dua kasus rekursif :

·     Base case : empty –leaf –external node.

·     Recursive case : Sebuah internal node(root) dan dua binary trees(sub tree kiri dan sub tree kanan)

·     Traversing Tree : “Menjalani/mengunjungi” tree.

Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti memiliki 0 atau 2 node anak.

Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node memiliki 0 atau 2 node anak dengan leafnya berada pada kedalaman yang sama dari node root.

Complete Binary Tree adalah binary tree dengan tinggi k adalah binary tree yang miliki jumlah maximum nodes dilevel 0 sampai k –1, dan pada level k seluruh node mampat ke kiri. Jadi suatu perfect binary tree adalah juga complete binary tree.

Implementasi

1.   Deklarasi Tree

Karena tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah komponen node itu sendiri. Implementasi node, diperlukan sebuah struktur yang memiliki susunan variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan kiri dan kanan, bertipe pointer, masing-masing mewakili vektor yang akan menunjuk ke node anak kiri dan kanan.

2.   Inisialisasi Tree

Untuk pertama kali, kita perlu tambahkan kode pada baris awal fungsi Main:

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama *pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer *pohon ditunjukkan ke NULL.

3.   Menambahkan Node Pada Tree

Untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner :

1.   Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.

2.   Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

·     Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

·     Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

Variabel **root menunjukkan node mana yang sedang dicek saat ini, untuk itu saat pemanggilan fungsi ini, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.

4.   Membaca dan Menampilkan Node Pada Tree

Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif.

·     Kunjungan Pre-Order

Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1.   Cetak isi (data) node yang sedang dikunjungi

2.   Kunjungi kiri node tersebut

·     Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri 4 tersebut.

·     Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3.   Kunjungi kanan node tersebut

·     Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

·     Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

·     Kunjungan In-Order.

1.   Kunjungi kiri node tersebut

·     Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

·     Jika kiri kosong (NULL), lanjut ke langkah kedua.

2.   Cetak isi (data) node yang sedang dikunjungi

3.   Kunjungi kanan node tersebut

·     Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

·     Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

·     Kunjungan Post-Order

1.   Kunjungi kiri node tersebut

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut. Jika kiri kosong (NULL), lanjut ke langkah kedua.

2.   Kunjungi kanan node tersebut

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut. Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3.   Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Variabel **root pada setiap fungsi diatas menunjukkan node mana yang sedang dikunjungi saat ini, untuk itu saat pemanggilan, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.