Rabu, 26 Maret 2014
Selasa, 25 Maret 2014
STRUKTUR DATA
KUNJUNGAN PADA POHON BINER
BAB I
PENDAHULUAN
PENDAHULUAN
Struktur
data
adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media
penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.Sedangkan Data adalah
representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan
yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.
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
·
http://belajarstrukturdata.blogspot.com
http://hermanabdee.blogspot.com/2013/04/contoh-makalah-kunjungan-binary-tree.html
www.Google.comhttp://hermanabdee.blogspot.com/2013/04/contoh-makalah-kunjungan-binary-tree.html
Langganan:
Komentar (Atom)