STRUKTUR DATA
♣ KUNJUNGAN PADA POHON BINER ♣
Nama Kelompok :
1.Leonard P. Malau 12120774
2.Nurul Suhartatik 12122167
3.Bohaerudin 12120327
4.Dwi Sudarwati 12120498
5.Herman Pirwaniadi 12120937
6.Dedy Kurniawan 12120453
Kelompok 3 (Leafe)
Manajemen Informatika
122D03
BINA SARANA INFORMATIKA
KATA PENGANTAR
Puji Syukur
kami panjatkan kehadirat Allah SWT karena berkat limpahan rahmat dariNya kami
selaku Kelompok 3 dapat
menyelesaikan makalah ini tepat pada waktunya, walaupun dalam keadaan
yang sangat sederhana. Makalah ini berisikan tidak lanjut dari materi
pembelajaran kita di Pertemuan 10 yang membahas tentang Kunjungan Pada Pohon
Biner. Dengan segala keterbatasan yang kami miliki kami sajikan makalah ini
dalam bentuk yang sangat sederhana maka dari itu kami selaku panyaji meminta
maaf yang sebesar-besarnya jika makalah ini masih begitu banyak kekurangan,
baik itu yang kami sengaja ataupun tidak
sengaja karena ini semua masih dalam
proses pembelajaran kami yang tentunya tak
lepas dari kodrad kami sebagai manusia biasa yang tak akan pernah luput dari kesalahan dan
tentunya makalah ini masih sangat jauh dari sempurna. Semoga makalah ini dapat
bermanfaat untuk memberikan wawasan kepada kalian semua bagi para pembaca.
Untuk itu kepada dosen kami untuk meminta masukan, kritikan atau saran yang
membangun untuk melengkapi kekurangan yang ada di makalah ini. Atas
perhatiannya kami selaku Kelompok 3 mengucapkan terima kasih.
Tangerang, 15 Desember 2012
DAFTAR ISI
BAB I
PENDAHULUAN……………………………............................................................................................................1
1.1. Latar Belakang………………………………………………………………………………………………………………………..………1
1.2. Batasan
Masalah……………………………………………………………………………………………………………………………3
1.3. Tujuan……………………………………………………………………………………………………………………………………………3
BAB II
PEMBAHASAN…………………………….............................................................................................................4
II.1. Pengertian Kunjungan Pohon
Biner……………………………………………………………………………………….………4
II.2. Aplikasi Pohon
Biner………………………………………………………………………………………………………………………4
II.3. contoh
program…………………………………………………………………………………………………………………………….5
II.4. tampilan
program………………………………………………………………………………………………………………………….9
BAB III
PENUTUP…………………………………............................................................................................................10
III.1. Kesimpulan……………………………………………………………………………………………………………………………….10
III.2.
Saran…………………………………………………………………………………………………………………………………………10
BAB IV
DAFTAR PUSTAKA
…………………………………..............................................................................................11
BAB V
FORM PENILAIAN PRESENTASI………………………………………………………………………………………………………….12
BAB I
PENDAHULUAN
Sebuah pohon biner adalah grafik asiklis yang
terhubung dimana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat
ditunjukan 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 yg tak terkoneksi, membolehkan bermacam koneksi dalam
komponen di gafik, kita memanggil struktur sebuah hutan (forest).
1.1. Latar
Belakang
Dalam
pemograman Pada garis besarnya, Data dapat dikategorikan menjadi :
A. Type Data Sederhana / Data Sederhana
Terdiri
dari :
1.
Data Sederhana Tunggal
Misalnya
: Integer, Real/Float, Boolean dan
Character
2.
Data Sederhana Majemuk
Misalnya
: String
B. Struktur Data
Terdiri
dari :
1.
Struktur Data Sederhana
Misalnya
Array dan Record
2.
Struktur Data Majemuk
Terdiri
dari :
a.
Linier
Misalnya
: Stack, Queue dan Linear Linked List.
b.
Non Linier
Misalnya
: Pohon (Tree), Pohon Biner (Binary
Tree),
Pohon Cari Biner (Binary Search Tree), General Tree serta Graph. Dan dalam
kesempatan kali ini kelompok kami akan mempersentasikan tentang kunjungan pohon
biner (binary tree).
Kunjungaan pada pohon biner merupakan salah satu operasi yg
sering dilakukan pada suatu pohon binar tepat satu kali (binary tree traversal)
operasi ini terbagi menjadi 3 bentuk :
1.
Kunjungan secara
preorder(depth firs order) yg mempunyai urutan
a.
Cetak simpul yg
dikunjungi / simpil akar
b. Kunjungin cabang kiri
c.
Kunjungi cabang
kanan
2.
Kunjungan secara
inorder(symmetric order) yang mempunyai urutan
a.
Kunjungi cabang
kiri
b. Cetek simpul yg dikunjungi /simpul akar
c.
Kunjungi cabang
kanan
Kunjungan secara
postorder yg mempunyai urutan
|
a.
Kunjungi cabang
kiri
b. Kunjungi cabang kanan
c.
Cetak simpul yg
dikunjungi /simpul aka
r
1.2. Batasan
Masalah
Pada makalah ini hanya akan dibahas seluk beluk dari struktur
pohon (tree) berkaitan dengan :
1. Pengertian dari kunjungan pada pohon biner.
2. Jenis-jenis dari kunjungan pohon biner.
1.3. Tujuan
Adapun tujuan dari pembuatan makalah ini yaitu :
1. untuk mengtahui definisi dari kunjungan pada poho biner.
2. untuk mengetahui bagaimana pembagian jenis-jenis kunjungan pada
pohon biner.
BAB II
PEMBAHASAN
II.1.Pengertian Kunjungan Pada Pohon Biner
Ada tiga macam kunjungan pada pohon biner, yaitu kunjungan
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 PreOrder :
Kunjungan PreOrder LRO atau sering disebut dengan depth first
order menggunakan urutan sebagai berikut : 1. Cetak isi simpul yang dikunjungi
(simpul akar) 2. Kunjungi cabang kiri 3. Kunjungi cabang kanan.
2. Kunjungan InOrder :
Kunjungan InOrder LRO atau sering disebut dengan symmetric order
menggunakan urutan sebagai berikut : 1. Kunjungi cabang kiri 2. Cetak isi
simpul yang dikunjungi 3. Kunjungi cabang kanan.
3. Kunjungan PostOrder
Kunjungan PostOrder LRO menggunakan urutan sebagai berikut : 1. Kunjungi
cabang kiri 2. Kunjungi cabang kanan 3. Cetak isi simpul yang dikunjungi.
II.2.Aplikasi Pohon Biner
Pada
bagian ini akan di bahas tenang bagaimana menusun sebuah pohon Biner yang
apabila di kunjungi secara :
1.
PreOrder menghasilkan notasi Prefix.
2.
InOrder mengasilkan notasi Infix.
3.
PostOrder mnghasilkan notasi Postfix.
II.3.Contoh Program :
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h> //
dibutuhkan untuk system("cls");
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
bool isEmpty()
{return root==NULL;}
void insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
if(isEmpty())root = t;
else
{
tree_node* curr;
curr = root;
while(curr!=NULL)
{
parent = curr;
if(t->data > curr->data) curr
= curr->right;
else curr = curr->left;
}
5
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void inorder(tree_node* p)
{
if(p!=NULL)
{
if(p->left)
inorder(p->left);
cout<<"
"<<p->data<<" ";
if(p->right)
inorder(p->right);
}
else
return;
}
void print_inorder()
{
inorder(root);
}
int count(tree_node* p)
{
if(p==NULL)return 0;
return count(p->left) +
count(p->right) + 1;
}
int height(tree_node* p)
{
if(p==NULL)return 0;
int u = height(p->left),v =
height(p->right);
if(u > v)
return u+1;
else
return v+1;
}
void cari_terbesar(tree_node* p)
6
{
if(p==NULL)
return;
else
if(p->right==NULL)
{
cout<<"
"<<p->data<<" ";
return;
}
else
{
cari_terbesar(p->right);
return;
}
}
int main()
{
root=NULL;
int ch,tmp;
while(1)
{
system("cls"); // Saya
mengganti scrclr() karena dicompiler sy tidak ada fungsi tersebut
cout<<endl;
cout<<"Menu Utama Operasi
Pohon Biner"<<endl;
cout<<"--------------------"<<endl;
cout<<"1. Insert/Tambah
Data"<<endl;
cout<<"2. Kunjungan
In-Order"<<endl;
cout<<"3. Kunjungan
Pre-Order"<<endl;
cout<<"4. Kunjungan
Post-Order"<<endl;
cout<<"5. Hapus
Data"<<endl;
cout<<"6. Menghitung Jumlah
Node"<<endl;
cout<<"7. Menghitung Tinggi
Pohon"<<endl;
cout<<"8. Mencari Data
Terkecil"<<endl;
cout<<"9. Mencari Data
Terbesar"<<endl;
cout<<"10.
Exit"<<endl;
cout<<"Pilihan Anda :
";
cin>>ch;
cout<<endl;
switch(ch)
{
case 1 : cout<<"Masukan
Data : ";
cin>>tmp;
insert(tmp);
break;
case 2 : cout<<endl;
cout<<"Kunjungan
In-Order"<<endl;
cout<<"---------------"<<endl;
print_inorder();getch();
break;
case 6 : cout<<"Menghitung
Jumlah Node"<<endl;
cout<<"------------------"<<endl;
cout<<"Jumlah Node =
"<<count(root);
getch();
break;
case 7 : cout<<"Menghitung
Tinggi Pohon"<<endl;
cout<<"------------------"<<endl;
cout<<"Tinggi Pohon =
"<<height(root);
getch();
break;
case 9 : cout<<"Mecari Data
Terbesar"<<endl;
cout<<"------------------"<<endl;
cout<<"Data Terbesar Adalah
= "<<endl;
cari_terbesar(root);
getch();
break;
case 10 : return 0;
break;
default: cout<<"Pilihan
yang Anda Masukkan salah!"<<endl;
getch();
break;
}
}
}
BAB III
PENUTUP
1.1. Kesimpulan
Dari uraian pada pembahasan yang
disajikan, maka dapat ditarik
sebuah kesimpulan bahwa : Pada dasarnya Sebuah pohon biner
memiliki operasi traversal yaitu suatu kunjungan pada
suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap
kita akan
memperoleh urutan informasi secara linier yang tersimpan di dalam
pohon biner.
1.2.Saran
Adapun syaran yang dapat kami sampaikanyaitu :
1.Semoga makalah ini dapat dimanfaatkan sesuai pada tempatnya.
2. Kami mohon maaf jika terdapat banyak sekali kesalahan dalam
pembuatan
makalah ini.
3. Kami mengharapkan kritik dan saran yang membangun dari pembaca
guna untuk perbaikan makalah selanjutnya.
4.Semoga makalah ini dapat digunakan sesuai dengan metode
pembelajaranyang sedang di anut oleh Mahasiswa Mahasiswi sekarang
ini.
BAB IV
DAFTAR PUSTAKA
1 comments:
ini inorder doang ya ? post sama pre nya ga jalan
Post a Comment