Tree Dalam Struktur Data

Tree

Kumpulan node yang saling terhubung satu sama lain dalam suatu  kesatuan yang

membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu  cara

merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip

sebuah pohon, walaupun pohon tersebut  hanya tampak sebagai kumpulan node-node  dari atas ke bawah. Suatu struktur data yang tidak linier yang

menggambarkan  hubungan yang hirarkis (one-to-many) dan tidak linier antara

elemen-elemennya.

Deklarasi Pohon

Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun  struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam  setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang  kanan, dan informasi yang akan disimpan dalamsimpul tersebut.

typedef char TypeInfo;

typedef struct Simpul *Tree;

struct Simpul {

TypeInfo Info;

tree Kiri, /* cabang kiri */

Kanan; /* cabang kanan */

};

 ISTILAH DALAM TREE

1.       JENIS-JENIS TREE

BINARY TREE

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub

pohon dan kedua subpohon harus terpisah.

Kelebihan struktur Binary Tree :

§  Mudah dalam penyusunan algoritma sorting

§  Searching data relatif cepat

§  Fleksibel dalam penambahan dan penghapusan data

1.       KUNJUNGAN PADA POHON BINER

Sebuah pohon biner memiliki operasi  traversal  yaitu suatu kunjungan pada

suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan

memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.

Terdapat tiga jenis kunjungan pada pohon biner, yaitu :

1.       PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

Prosedur untuk melakukan traversal secara PREORDER adalah sebagai berikut:

1.       INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kanan.

Prosedur untuk melakukan traversal secara INORDER adalah sebagai berikut:

1.       POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

–  Cetak isi simpul yang dikunjungi

BERIKUT MERUPAKN CONTOH PROGRAMNYA

#include<stdio.h>//header file

#include<conio.h>

/* Deklarasi struct */

typedef struct Node{

      int data;    //data pada tree

      Node *kiri;  //penunjuk node anak kiri

      Node *kanan; //penunjuk node anak kanan

};

/* Fungsi untuk memasukkan data ke dalam tree */

void tambah(Node **root, int databaru){

      if((*root) == NULL){       //jika pohon/subpohon masih kosong

            Node *baru;//node “baru” dibentuk…

            baru = new Node;//berdasarkan struct “Node”

            baru->data = databaru; //data node baru diisi oleh variabel databaru

            baru->kiri = NULL;//penunjuk kiri node baru masih kosong

            baru->kanan = NULL;//penunjuk kanan node baru masih kosong

            (*root) = baru; //node pohon (root) diletakkan pada node baru

            (*root)->kiri = NULL;//penunjuk kiri node root masih kosong

            (*root)->kanan = NULL; //penunjuk kanan node root masih kosong

            printf(“Data bertambah!”);

      }

      else if(databaru < (*root)->data)//jika databaru kurang dari data node root…

            tambah(&(*root)->kiri, databaru);//tambahkan databaru pada subpohon kiri

      else if(databaru > (*root)->data)//jika databaru lebih dari data node root…

            tambah(&(*root)->kanan, databaru); //tambahkan databaru pada subpohon kanan

      else if(databaru == (*root)->data)//jika databaru sama dengan data node root

            printf(“Data sudah ada!”);//databaru tidak dapat ditambahkan pada tree

}

/* Fungsi untuk menampilkan data secara pre-order

   (data ditampilkan dari node induk, node anak kiri, lalu node anak kanan)

*/

void preOrder(Node *root){

      if(root != NULL){//jika pohon/subpohon tidak kosong

            printf(“%d “, root->data);//menampilkan data node yang dikunjungi

      preOrder(root->kiri);//mengunjungi node anak kiri

      preOrder(root->kanan); //mengunjungi node anak kanan

      }

}

/* Fungsi untuk menampilkan data secara in-order

   (data ditampilkan dari node anak kiri, node induk, lalu node anak kanan)

*/

void inOrder(Node *root){

      if(root != NULL){//jika pohon/subpohon tidak kosong…

      inOrder(root->kiri);//mengunjungi node anak kiri

      printf(“%d “, root->data);//menampilkan data node yang dikunjungi

      inOrder(root->kanan);//mengunjungi node anak kanan

      }

}

              

/* Fungsi untuk menampilkan data secara post-order

   (data ditampilkan dari node anak kiri, node anak kanan, lalu node induk)

*/

void postOrder(Node *root){

     if(root != NULL){//jika pohon/subpohon tidak kosong

     postOrder(root->kiri); //mengunjungi node anak kiri

     postOrder(root->kanan);//mengunjungi node anak kanan

     printf(“%d “, root->data); //menampilkan data node yang dikunjungi

     }

}

main(){

     int pil, c;

     Node *pohon, *t;

     pohon = NULL;

     do{

           int data;

           printf(“MENU\n”);

           printf(“1. Tambah\n”);

           printf(“2. Lihat Pre-Order\n”);

           printf(“3. Lihat In-Order\n”);

           printf(“4. Lihat Post-Order\n”);

           printf(“5. Exit\n”);

           printf(“Pilihan : “); scanf(“%d”, &pil);

           switch(pil){

           case 1 :

                printf(“Data baru : “);

                scanf(“%d”, &data);

                tambah(&pohon, data);

                break;

           case 2 :

                if(pohon != NULL)

                     preOrder(pohon);

                else

                     printf(“Masih kosong!”);

                break;

           case 3 :

                if(pohon != NULL)

                     inOrder(pohon);

                else

                      printf(“Masih kosong!”);

                break;

           case 4 :

                if(pohon != NULL)

                     postOrder(pohon);

                else

                     printf(“Masih kosong!”);

                break;

           }

           getch();

           printf(“\n”);

     }

     while(pil != 5);

}

Searching dalam struktur data

Searching

Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori(pencarian internal), bisa juga pada file pada external storage(pencarian external).

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search). Pada Kesempatan ini kita hanya akan membahas tentang pencarian internal menggunakan Array dinamis (pointer).
Berikut adalah metode-metode yang digunakan dalam Searching 

1. Sequential Search (Pencarian berurutan)
Adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan. 

Contoh Program :
#include <iostream>
using namespace std;
main() {
int data[8] = {8,10,6,-2,11,7,1,100};
int cari;
int tanda=0;
cout<<"masukkan data yang ingin dicari = "; cin>>cari;
for(int i=0;i<8;i++){
if(data[i] == cari) tanda=1;
}
if(tanda==1) cout<<"Data ada!\n"; 
else cout<<"Data tidak ada!\n";
}

2. Binary Search
Salah satu syarat agar binary search dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, binary search tidak dapat dilakukan. 
Prinsip dari binary search dapat dijelaskan sebagai berikut : 
a.Mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah. 
b.Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
c.Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1. Jika data sama, berarti ketemu.

Contoh Program:
#include <iostream>
using namespace std;
main() {
int data[7] = {10,13,17,34,58,67,99};
int N = 7
int kiri=0,kanan=N-1,tengah,cari;
int tanda=0;

cout<<”Masukan data yang di cari?”;cin>>cari;
while((kiri<=kanan)&&(tanda==0)) {
tengah=(kiri+kanan)/2; 
cout<<”data tengah = ”<<tengah<<endl; 
if(data[tengah]==cari) tanda=1; 
else if(cari < data[tengah]) { 
cout<<”cari di kiri\n”; 
kanan=tengah-1; 
} 
else {
kiri=tengah+1; 
cout<<”cari di kanan\n”; 
}
if(tanda==1) cout<<”Data ada\n”;
else cout<<”Data tidak ada\n”; 
} 
}

3. Interpolation Search
Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data. Contoh ilustrasi: jika kita hendak mencari suatu kata di dalam kamus telepon, misal yang berawalan dengan huruf J, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 1/3 atau 1/4 dari tebal kamus.
Rumus posisi relatif kunci pencarian dihitung dengan rumus:

- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, low = pos + 1 Contoh program:
#include <iostream>
#include <math.h>
using namespace std;
main() {
int data[7] = {10,13,17,34,58,67,99};
int low,high,cari,posisi;
float posisi1;
int N = 7,tanda=0;
low=0,high=N-1;
cout<<”Masukan data yang di cari?”;cin>>cari;
do {
posisi1 = (cari-data[low])/(data[high]-data[low])*(high-low)+low;
posisi = floor(posisi1); //pembulatan ke bawah
if(data[posisi]==cari) {
tanda =1;
break;
}
if(data[posisi]>cari) high=posisi-1;
else if (data[posisi]<cari) low=posisi+1
}
while (cari>=data[low]&&cari<=data[high]);
if(tanda==1) cout<<”Data ditemukan\n”;
else cout<<”Data tidak ada\n”;
}