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.
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 =newNode; //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
// 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";
}
2.InOrder
3.PreOrder
Hasil output:
1.PostOrder
2.InOrder
3.PreOrder
Update Contact :
No Wa/Telepon (puat) : 085267792168
No Wa/Telepon (fajar) : 085369237896
Email : Fajarudinsidik@gmail.com
No Wa/Telepon (puat) : 085267792168
No Wa/Telepon (fajar) : 085369237896
Email: Fajarudinsidik@gmail.com
atau Kirimkan Private messanger melalui email dengan klik tombol order dibawah ini :
