Nama : firman atduhri
Ø Pengertian Tree
Tree
merupakan salah satu bentuk struktur data tidak linear yang menggambarkan
hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.
Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus
yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic,
simple, connected yang tidak mengandung loop.
Sebuah
binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan
setiap nodenya harus memiliki identifier/value. Value pada semua node subpohon
sebelah kiiri adalah selalu lebih kecil dari value dari root, sedangkan value
subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root,
masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary
search tree.
Struktur
data bst sangat penting dalam struktur pencarian, misalkan dalam kasus
pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses
pencarian akan semakin cepat, jika kita menggunakan list contigue dan melakukan pencarian
biner,akan tetapi jika kita ingin
melakukan perubahan isi list (insert atau delete), menggunakan list contigue
akan sangat lambat, karena prose insert dan delete dalam list contigue butuh
memindahkan linked-list, yang untuk operasi insert atau delete tinggal
mengatur- atur pointer,akan tetapi pada n-linked list, kita tidak bisa
melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata
lain hanya secara squential.
·
Pengertian
Binary Tree
Binary
Tree merupakan salah satu bentuk struktur data tidak linear yang
menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara
elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu
elemen khusus yang disebut Root dan node lainnya ( disebut subtree).
Dalam
tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah
binary tree.
Binary
tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh
memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap
node dalam binary treee boleh memiliki paling banyak dua child (anak simpul),
secara khusus anaknya dinamakan kiri dan
kanan.
Binary
Tree merupakan himpunan vertex-vertex
yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree
kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.
Sebuah pohon biner adalah grafik asiklis
yang terhubung dimana setiap
tingkatan dari susut tidak lebih dari 3.
Ini dapat ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau
lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga,
tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah
pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya
dengan tingkat tidak lebih dari dua sebagai akar.
Dengan
akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak bagaimanapun juga, sejauh
ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau
kanan. Jika kita membuang keperluan yang
tak terkoneksi, membolehkan bermacam
koneksi dalam komponen di grafik, kita memanggil struktur sebuah hutan.
Sebuah
jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada
grafik langsung. Sebuah pohon biner dapat berarti :
-
Sebuah sudut tunggal.
-
Sebuah graf yang dibentuk dengan
mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah
panah langsung dari sudut yang baru ke akar dai setiap pohon biner.
Pohon biner dapat
dikontruksi dari bahasa pemrogaraman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records
dan referensi. Pohon biner secara khas dikontruksi dengan mengambil sebuah
struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan
anak kanan.
Kadang-kadang itu juga
memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai
kurang dari dua anak, beberapa penunjuk anak diaatur kedalam nilai nol khusus
atau kesebuah simpul sentinel.
Pohon biner dapat juga
disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut
merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam
penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat
ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan
pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode
ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi
lokal yang lebih baik, teristimewa selama sebuah preordeer traversal.
·
Istilah-istilah
dalam pohon
1.
Predesesor
Node yang berada diatas
node tertentu.
(contoh : B predesesor dari E dan F)
2.
Succesor
Node yang berada
dibawah node tertentu.
(contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang
terletak sebelum node tertentu dan
terletak pada jalur
yang sama.
(contoh : A dan B merupakan ancestor dari F)
Istilah – istilah Dalam
Pohon
4. Descendant
Seluruh node yang
terletak sesudah node tertentu
dan
terletak pada jalur yang sama.
(contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level
diatas satu node
(contoh : B merupakan
parent dari F)
6. Child
Succesor satu level
dibawah satu node
(contoh : F merupakan
child dari B)
7. Sibling
Node yang memiliki
parent yang sama dengan satu
node (contoh : E dan F
adalah sibling)
8.
Subtree
Bagian dari tree yang
berupa suatu node beserta
descendant-nya (contoh
: Subtree B, E, F dan
Subtree D, G, H)
9. Size
Banyaknya node dalam
suatu tree (contoh : gambar
tree diatas memiliki
size = 8)
10. Height
Banyaknya tingkat/level
dalam suatu tree (contoh :
gambar tree diatas
memiliki height = 3)
11. Root
(Akar)
Node khusus dalam tree
yang tidak memiliki
predesesor (Contoh : A)
12. Leaf
(Daun)
Node-node dalam tree
yang tidak memiliki daun
(contoh : Node E,F,C,G,H)
13.
Degree (Derajat)
Banyaknya
child yang dimiliki oleh suatu node
(contoh
: Node A memiliki derajat 3, node B memiliki derajat 2)
·
Istilah
pada pohon Binar
a.
Pohon
Biner Penuh (Full Binary Tree)
Semua
simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas
yang sama.
b.
Pohon
Biner Lengkap (Complete Binary Tree)
Hampir sama dengan Pohon BinerPenuh, semua
simpul (kecualidaun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas
berbeda.
c.
Pohon
Biner Similer
Dua pohon yang memiliki struktur yang sama
tetapi informasinya berbeda.
d.
Pohon
Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi
yangsama.
e.
Pohon
Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu
anak / turunan kecuali daun.
·
Sifat utama Pohon Berakar
1.
Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas
atau edge adalah (n-1).
2.
Mempunyai Simpul Khusus yang disebut Root, jika Simpul
tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
3.
Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika
Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4.
Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari
Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah.
Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau
Stribling.
5. Pohon
mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi
6. Pohon
mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7. Banyaknya
Simpul Maksimum sampai Level N adalah :
2
(N) - 1
|
8. Banyaknya
Simpul untuk setiap Level I adalah :
N
∑ 2 ( I – 1)
I
= 1
|
·
Kunjungan
pada pohon Biner
Kunjungan
pohon biner terbagi menjadi 3 bentuk
binary tree :
1. Kunjungan
secara preorder ( Depth First Order), mempunyai urutan :
a. Cetak
isi simpul yang dikunjungi ( simpul akar ),
b. Kunjungi
cabang kiri,
c. Kunjungi
cabang kanan .
2.
Kunjungan secara inorder ( symetric
order), mempunyai urutan :
a. Kunjungi cabang kiri,
a. Kunjungi cabang kiri,
b. Cetak isi simpul yang dikunjungi (simpul
akar),
c. Kunjungi
cabang kanan .
3. Kunjungan
secara postorder, mempunyai urutan :
a. Kunjungi cabang kiri,
a. Kunjungi cabang kiri,
b.
Kunjungi cabang kanan,
c.
Cetak isi simpul yang dikunjungi ( simpul akar ).
·
Aplikasi
pohon Biner
Notasi
Prefix, Infix dan Postfix
Pada bagian ini akan
dibahas tentang bagaimana menyusun sebuah Pohon Binar yang apabila
dikunjungisecara PreOrder akan menghasilkan Notasi Prefix,kunjungan secara
InOrder menghasilkan Notasi Infix, dankunjungan PostOrder menghasilkan Notasi
Postfix.
2.1.
Contoh kasus dan Program
·
Contoh
Program Tree dalam C++
#include
<iostream.h>
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
struct Node{
int data;
Node *kiri;
Node *kanan;
};
int count;
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 telah
Dimasukkan");
}
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 search(Node
**root, int cari)
{
if((*root) == NULL){
printf("Maaf,Data
tidak ditemukan!");
}
else if(cari <
(*root)->data)
search(&(*root)->kiri,cari);
else if(cari >
(*root)->data)
search(&(*root)->kanan,cari);
else if(cari ==
(*root)->data)
printf("Data
ditemukan!!!");
}
void hapus(Node **root,
int del)
{
if((*root) == NULL){
printf("Data tidak
ada!!");
}
else if(del <
(*root)->data)
hapus(&(*root)->kiri,del);
else if(del >
(*root)->data)
hapus(&(*root)->kanan,del);
else if(del ==
(*root)->data)
{
(*root)=NULL;
printf("Data telah
Terhapus");
}
}
int main(){
int pil,cari,del;
Node *pohon;
pohon = NULL;
do{
int data;
system("cls");
printf(" PROGRAM TREE LANJUTAN \n");
printf("================================\n");
printf(" 1. Masukkan Data \n");
printf(" 2. Transverse \n");
printf(" 3. Cari \n");
printf(" 4. Hapus \n");
printf(" 5. Clear Data \n");
printf(" 6. Keluar \n");
printf("================================\n");
printf("Masukkan
Pilihan Anda : ");
scanf("%d",&pil);
switch(pil){
case 1:
printf("Masukkan
data baru : ");
scanf("%d",
&data);
tambah(&pohon,data);
break;
case 2:
printf("\nPreOrder
: ");
if(pohon!=NULL) preOrder(pohon);
else printf("Data
masih kosong");
printf("\ninOrder
: ");
if(pohon!=NULL)
inOrder(pohon);
else printf("Data
masih kosong");
printf("\npostOrder
: ");
if(pohon!=NULL)
postOrder(pohon);
else printf("Data
masih kosong");
break;
case 3:
printf("Cari data
: ");
scanf("%d",
&cari);
search(&pohon,cari);
break;
case 4:
printf("Hapus data
: ");
scanf("%d",
&del);
hapus(&pohon,del);
break;
case 5:
pohon = NULL;
printf("Semua data
telah terhapus");
break;
case 6:
return 0;
default:
printf("Maaf,
pilihan Anda Salah");
}
getch();
}while(pil!=7);
}
Tampilan program saat dijalankan :
PERBEDAAN
TENTANG VARIABEL LOKAL DAN VARIABEL GLOBAL
1. Variabel Lokal (Variabel
Otomatis)
Variabel yang didefinisikan didalam suatu
fungsi dan berlaku sebagai variabel lokal bagi fungsi Variabel hanya dikenal di
dalam fungsi dimana variabel itu didefinsikan dan tidak dikenal oleh fungsi
lain
Sifat
variabel otomatis:
· Hanya
diciptakan saat fungsi dipanggil
· Saat
fungsi berakhir, variabel otomatis akan dihapus
· Hanya
dapat diakses didalam fungsi yang mendefinisikannya
Selang waktu
antara penciptaan dan penghapusan variabel disebut sebagai lifetime atau waktu
hidup.
Contoh
penggunaan variabel otomatis / local:
#include
using namespace std;
int main()
void contoh();
void main()
{
clrscr();
int x = 10;
cout << "x pada main() :
" << x << endl;
contoh();
getch();
}
void contoh()
{ int x = 15;
cout << "x pada contoh()
: " << x; }
2. Variabel Ekternal (Variabel Global)
· Variabel
yang didefinisikan di luar fungsi manapun sehingga dikenal oleh semua fungsi
· Variabel
eksternal mempunyai lifetime selama program dieksekusi
· Variabel
eksternal sebaiknya digunakan sesedikit mungkin atau bahkan tidak digunakan
sama sekali.
Contoh
penggunaan variabel eksternal / global:
int x = 10;
#include
using namespace std;
int main()
void contoh();
void main()
{
clrscr();
contoh();
cout << x;
getch();
}
void contoh()
{
x++;
}
Assalamualaikum,saya mau bertanya ,bagaimana cara kerja tree,terimakasih,,
BalasHapus