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.
Aplikasi Pohon Biner
Pada bagian ini akan membahas tentang bagaimana menyusun sebuah pohon Biner yang apabila di kunjungi secara :
1. PreOrder menghasilkan notasi Prefix.
2. InOrder mengasilkan notasi Infix.
3. PostOrder mnghasilkan notasi Postfix.
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;
}
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)
{
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;
}
}
}
SEMOGA BERMANFAAT
0 Response to "Materi Kuliah : Pengertian Pohon Biner dan Contoh Program"
Posting Komentar
Dari Abu Hurairah bahwa Rasulullah shallallahu ‘alaihi wa sallam bersabda,
مَنْ كَانَ يُؤْمِنُ بِاللَّهِ وَالْيَوْمِ اْلآخِرِ فَليَقُلْ خَيْرًا أَوْ لِيَصْمُت
“Barang siapa yang beriman kepada Allah dan Hari Akhir maka hendaklah ia berkata baik atau hendaklah ia diam.” (Muttafaq ‘alaih: Al-Bukhari, no. 6018; Muslim, no.47)