TREE SORT
Pengurutan (Sorting) adalah suatu proses pengurutan data yang
sebelumnya disusun secara
acak atau tidak teratur menjadi urut dan teratur menurut suatu
aturan tertentu.
Dalam
melakukan sorting ada banyak metode yang digunakan. tetapi yang akan kami bahas
adalah metode sorting dengan tree sort.
a. Definisi Tree Sort
Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasik output:
PreOrder,InOrder,PostOrder.
b. Konsep dan Algoritma
Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar,
batang, ranting, daun, dsb. Dalam tree sort ada istilah akar atau root dan daun
atau leaf.
Perhatikan gambar di bawah ini.
ketentuan dari gambar diatas adalah :
1 menjadi akar ,
2 menjadi subtree kiri,
3 menjadi subtree kanan,
4 & 5 menjadi daun dari subtree kiri ,
6 menjadi daun dari subtree kanan.
Setiap objek
dalam pohon biner berisi dua pointer, biasanya disebut kiri dan kanan. Selain
pointer ini tentu saja node dapat berisi tipe data lainnya. Misalnya, pohon biner integer bisa
terdiri dari objek dari jenis berikut:
struct Node {
int item; / / Data dalam node
ini.
Node *kiri; / / Pointer
ke subtree kiri.
Node * kanan; / / Pointer ke subtree kanan.
}
· Pointer kiri dan Kanan
dalam Node dapat NULL atau dapat menunjuk ke objek
lain dari jenis Node. Sebuah
simpul yang menunjuk ke node lain dikatakan induk dari simpul tersebut, dan
simpul itu menunjuk disebut anak.
Sebuah binary tree harus memiliki sifat-sifat sebagai berikut:
1. Ada satu buah node yang tidak memiliki node induk. Node ini
disebut root atau akar pohon.
2. Setiap node lain dalam pohon memiliki satu induk. Tidak ada loop
dalam sebuah binary tree. Artinya tidak mungkin untuk mengikuti rantai pointer
yang dimulai di node tertentu dan kembali di node yang sama.
3. Sebuah node yang tidak memiliki anak disebut daun atau leaf. Node
daun dapat dikenali dengan cara mengetahui bahwa pointer kiri dan kanan dari
sebuah node adalah NULL.
langsung saja bisa memahami algoritmanya lewat coding di bawah ini :
#include
"iostream"
#include
"conio.h"
using namespace std;
struct Node {
int item; //variabel item
Node *kiri; //pointer ke subtree kiri
Node *kanan; //pointer ke subtree kanan
};
void tambah(Node **akar,int itembaru) //berisi
pointer yang menunjuk ke pointer akar itu sendiri
{
if((*akar) == NULL) //jika akar kosong maka membuat item baru
{
Node *baru; //pointer baru
baru
=
new
Node; //new node = alamat baru
baru->item = itembaru; //baru di tunjuk oleh pointer item & di isi dengan item baru
baru->kiri = NULL; //baru ditunjuk dengan pointer kiri ,dan jika masihh kosong
baru->kanan = NULL; //baru ditunjuk dengan pointer kanan & jika kosong
(*akar) = baru; //pointer akar = variabel baru dengan alamat baru
(*akar)->kiri = NULL;
(*akar)->kanan = NULL;
cout<<"Item bertambah!";
}
else if(itembaru < (*akar)->item) tambah(&(*akar)->kiri,itembaru);
//
jika item yang ditambah di kiri
else if(itembaru > (*akar)->item) tambah(&(*akar)->kanan,itembaru); //jika
item yang ditambah item ke kanan
else if(itembaru == (*akar)->item) //jika
item yang di input sama dengan item yang ditambah sebelumnya
cout<<"Item sudah ada!";
}
void tampil(Node *akar) //fungsi menampilkan seluruh item yang telah di imput
{
if(akar != NULL){
cout<<akar->item<<" ";
tampil(akar->kiri), //rekursif dengan fungsi tampil dengan mengarah ke kanan
tampil(akar->kanan); //rekursif dengan fungsi tampil dengan mengarah ke kanan
}}
void preOrder(Node *akar) //fungsi cetak preOrder
{
if(akar != NULL){
cout<< akar->item<<" "; //cetak
item akar
preOrder(akar->kiri), //cetak
di subtree kiri
preOrder(akar->kanan); //cetak
di subtree kanan
}}
void inOrder(Node *akar) //fungsi cetak inOrder
{
if(akar != NULL){
inOrder(akar->kiri), //cetak
di subtree kiri
cout<< akar->item<<" "; //cetak
item akar
inOrder(akar->kanan); //cetak
di subtree kanan
}}
void postOrder(Node *akar) //fungsi cetak postOrder
{
if(akar != NULL){
postOrder(akar->kiri), //cetak
di subtree kiri
postOrder(akar->kanan); //cetak
di subtree kanan
cout<< akar->item<<" "; //cetak
item akar
}}
main()
{
int item;
Node *phn; //pointer phn untuk menghubungkan dengan link Node
phn = NULL; //alamat
pointer phn pada NULL
char pil;
do {
system("cls");
cout<<"\tTREE SORT\n";
cout<<"1. Tambah\n";
cout<<"2. Pre-order\n";
cout<<"3. In-order\n";
cout<<"4. Post-order\n";
cout<<"5. Keluar\n";
cout<<"Silahkan masukkan pilihan anda (1-5)... ";
pil=getche();
if(pil=='1')
{
cout<<"\n";
cout<<"\nItem baru :
";cin>>item;
tambah(&phn,item); //fungsi
tambah dengan menggunakan alamat pointer phn dengan variabel
}
if(pil=='2')
{
if(phn!=NULL) { //jika phn tidak kosong
cout<< "\n-->Item yang masuk : ";tampil (phn); //cetak
item yang masuk
cout<<"\n-->preOrde : ";preOrder(phn); //cetak preOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
if(pil=='3')
{
if(phn!=NULL) {
cout<< "\n-->Item yang masuk : ";tampil(phn); //cetak
item yang masuk
cout<<"\n-->inOrder : ";inOrder (phn); //cetak item inOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
if(pil=='4')
{
if(phn!=NULL) {
cout<< "\n-->Item yang masuk : ";tampil (phn); //cetak
item yang masuk
cout<<"\n-->postOrder : ";postOrder(phn); //cetak
item postOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
}
while(pil!='5');
cout<<"\n";
}
Hasil output:
1.PostOrder
2.InOrder
3.PreOrder
