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 hasil 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.
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.
1. Ada satu buah node yang tidak memiliki node induk.
2. Setiap node lain dalam pohon memiliki satu induk.
3. Sebuah node yang tidak memiliki anak disebut daun atau leaf.
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 input
{
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 SORTn”;
cout<<“1. Tambahn”;
cout<<“2. Pre-ordern”;
cout<<“3. In-ordern”;
cout<<“4. Post-ordern”;
cout<<“5. Keluarn”;
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”;
}
