TREE
Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, 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).
Ilustrasi Tree:
Binary Tree (Pohon Biner)
Dalam mata
kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner. 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.
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 leafnya berada
pada kedalaman yang sama dari node root. Juga disebut sebagai Complete Binary
Tree (Pohon Biner Lengkap)
Almost Complete
Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang setiap nodenya
dapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus
memiliki kiri. Tidak boleh memiliki kanan saja.
Ilustrasi Binary Tree:
Implementasi
Implementasi
dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner
saja. Asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe
data integer.
1. Deklarasi Tree
Karena tree tersusun oleh node-node, maka yang perlu kita
deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita
namai Node.
Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node
ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan
berikut ini:
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, saat kita akan membuat sebuah pohon biner,
asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali,
sehingga masih kosong. Oleh karena itu perlu kita tambahkan kode berikut 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
Karena pohon yang kita buat merupakan sebuah pohon biner, maka 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:
a. 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.
b. 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.
tambah(&pohon,data);
Untuk selengkapnya dapat dilihat pada bagian 5, kode program
lengkap.
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.
a.
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 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.
void preOrder(Node *root){
if(root != NULL){
printf("%d
",root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
b.
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.
void inOrder(Node *root){
if(root != NULL){
inOrder(root->kiri);
printf("%d
",root->data);
inOrder(root->kanan);
}
}
c. 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.
void postOrder(Node *root){
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d
",root->data);
}
}
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.
preOrder(pohon);
inOrder(pohon);
postOrder(pohon);
Untuk selengkapnya dapat dilihat pada bagian 5, kode program
lengkap.
5. Kode Program Lengkap
Berikut ini kode program keseluruhan, termasuk menu
tampilan, di mana di dalamnya terdapat Deklarasi Tree, Inisialisasi Tree,
Penambahan Node, dan Pembacaaan serta Menampilkan Node dengan 3 macam
kunjungan. Kode ditulis dengan C++ 3.00.
#include
<stdio.h>
#include
<conio.h>
typedef
struct Node{
int data;
Node *kiri;
Node *kanan;
};
void
tambah(Node **root,int databaru){
if((*root) == NULL){
Node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf("Data bertambah!");
}
else
if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else if(databaru == (*root)->data)
printf("Data sudah ada!");
}
void
preOrder(Node *root){
if(root != NULL){
printf("%d
",root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void
inOrder(Node *root){
if(root != NULL){
inOrder(root->kiri);
printf("%d
",root->data);
inOrder(root->kanan);
}
}
void
postOrder(Node *root){
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d
",root->data);
}
}
void
main(){
int pil,c;
Node *pohon,*t;
pohon = NULL;
do{
clrscr();
int data;
printf("MENU\n");
printf("1. Tambah\n");
printf("2. Lihat
pre-order\n");
printf("3. Lihat
in-order\n");
printf("4. Lihat post-order\n");
printf("5. Exit\n");
printf("Pilihan : ");
scanf("%d",&pil);
switch(pil){
case 1: printf("Data baru :
");scanf("%d",
&data);
tambah(&pohon,data);
break;
case 2: if(pohon!=NULL) preOrder(pohon);
else printf("Masih
kosong!");
break;
case 3: if(pohon!=NULL) inOrder(pohon);
else printf("Masih
kosong!");
break;
case 4: if(pohon!=NULL) postOrder(pohon);
else printf("Masih
kosong!");
break;
}
getch();
}while(pil!=5);
}
0 komentar:
Posting Komentar