Tree Sort c++ / Pengurutan (Sorting)

Tree Sort c++

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 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.

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 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 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";

}