Post ini ditujukan untuk tugas struktur data : Binary Tree. . . .
Nama : Ardiant Yosa Hastaka
NIM : A11.2012.07102
Kelas : A11.4311
Progdi : TI - S1
Dosen Pembimbing : Fahri Firdausillah
Kali ini saya "yosasensei akan membicarakan tentang Binary tree, yang mungkin bagi mahasiswa yang pernah diampu oleh Bu Sari saat Algoritma Pemrograman sudah pernah mendengar kata-kata tersebut.
nah pada saat ini, saya ingin menjelaskan menurut yang saya sudah pahami walaupun juga banyak resensi yang saya kumpulkan untuk dapat memahami Algoritma Binary Tree ini. dan tentunya dari saduran berbagai sumber yang mungkin saja akan disadur oleh para pembaca post ini :)
Post ini mungkin akan menjelaskan tentang pengertian, manfaat, dan implementasinya dalam bahasa C.
BINARY TREE
Oleh Ardiant Yosa Hastaka
Seperti silsilah keluarga atau MLM (multilevel marketing). Itulah binary tree, dari satu terpecah menjadi dua dan seperti itu seterusnya element-elementnya. Itulah mengapa namanya Biner, yang asalnya bilangan biner terdiri dari dua (2) macam karakter, 1 dan 0. diterapkan dalam algoritma ini sehingga setiap element memecah sudutnya menjadi dua sehingga terlihat bercabang, seperti keluarga ayah dan ibu yang mempunyai satu anak.
- Kemudahan dalam pengurutan dan penyusunan data.
- Pencarian data yang relatif cepat.
- Fleksibelitas dalam penyisipan dan penghapusan data. (user lebih leluasa dalam edit data dalam implementasiannya)
dan Secara Umum Binary Trees adalah Kumpulan node yang dibentuk dengan aturan tertentu (syarat derajat masuk dan keluar ). Binary Tree bisa dibagi-bagi menjadi bagian yang paling kecil.
misalkan gambar ini:
Gambar X Binary Trees
Node " R " disebut dengan root atau akar dari pohon X. X tersebut bisa dibagi menjadi lebih kecil lagi mulai dari cabang-cabangnya. berikut langkah-langkahnya :
Bagian-bagian dari pohon X
Binary Tree X terdiri dari root atau akar, left substree (bagian kiri pohon), dan right substree (bagian kanan pohon)
dan bila bagian yang kiri kita bagi lagi akan menjadi seperti demikian.
dan jika bagian kiri kita pilah lagi nejadi sub sub left substree akan menjadi demikian:
node N dan T tidak memiliki jaringan ke bawahna lagi. element atau nodes semacam ini disebut dengan terminal nodes (element terakhir) atau leaf (daun).
pengulangan prosedur atau proses semacam ini dilakukan dengan rekursif, sama halnya dengan yang pernah dibahas salam kelas stack.
pada penjelasan diatas adalah penjelasan tentang definisi Binary Tree dan struktur data dari Binary Tree tersebut.
dan berikutnya akan saya sampaikan tentang "Transversing Binary Trees" atau pengunjungan Pohon Biner.
TRANVERSING BINARY TREES
oleh. Ardiant Yosa Hastaka
Transversing Binary Trees adalah kunjungan terhadap nodes yang ada pada struktur data Binary Tree untuk keperluan pengolahan data selanjutnya, dapat dilakukan dengan tiga cara, yaitu:
dengan gambar berikut:
- Preorder, dengan tahapan:
- Proses root R
- Kunjungi left substree dari R secara preorder ; rekursif
- Kunjungi right substree dari R secara preorder; rekursif
- Inorder, dengan tahapan:
- Kunjungi left substree dari R secara inorder; rekursif
- Proses root R
- Kunjungi right substree dari R secara inorder; rekursif
- Postorder, dengan tahapan:
- Kunjungi left substree dari R secara preorder; rekursif
- Kunjungi right substree dari R secara preorder; rekursif
- Proses root R.
Atau secara singkat dapat dikatakan bahwa:
- Preorder mengikuti pola : rekursif (root - left - right).
- Inorder mengikuti pola : rekursif (left - root - right).
- Postorder mengikuti pola : rekursif (left - right - root).
- Preorder adalah : R , A , H , N , T , C , M , I
- Inorder adalah : A , N , H , T , R , C , M , I
- Postorder adalah : N , T , H , A , M , I , C , R
Source : Wahyudi, Bambang, Pengantar Struktur Data dan Algoritma, Penerbit Andi, Yogyakarta, 2004.#include#include#includetypedef char typeinfo;typedef struct node tree;struct node {int info;tree *kanan;//cabang kiritree *kiri;//cabang kanan};tree *p,*q,*baru, *root,*baca;int x,n=0;float total=0.0f,jum=0.0f;float rata=0.0f;void alokasi(){printf("masukan DATA: ");fflush(stdin);scanf("%i",&x);baru=(tree *)malloc(sizeof(tree));if(baru==NULL){puts("Alokasi memori gagal");}else{baru->info=x;baru->kanan=NULL;baru->kiri=NULL;}}void bentuk(){alokasi();n++;//banyak dataif(root==NULL){root=baru;}else{p=root;q=root;while((q!=NULL)&&(baru->info!=p->info)){p=q;if(baru->infoinfo){ q=p->kiri;}else{q=p->kanan;}}if(baru->info==p->info){puts("data duplikasi");}else{if(baru->infoinfo){ p->kiri=baru;}else{p->kanan=baru;}}}}void preorder(tree *root){if(root!=NULL){jum=root->info;printf("%d ",root->info);total=total+jum;preorder(root->kiri);preorder(root->kanan);}//return;}void inorder(tree *root){if(root!=NULL){inorder(root->kiri);printf("%d ",root->info);inorder(root->kanan);}//return;}void postorder(tree *root){if(root!=NULL){postorder(root->kiri);postorder(root->kanan);printf("%d ",root->info);}//return;}main(){char jawab;do{bentuk();printf("ada data lagi (Y/N): ");fflush(stdin);jawab=getchar();}while(jawab=='y'||jawab=='Y');printf("hasil pre order : ");preorder(root);printf("\nhasil in order : ");inorder(root);printf("\n hasil post order : ");postorder(root);printf("\ntotal data=%d",total);printf("\nbanyak data=%d ",n);printf("\n\nrata-rata= %g\n",rata=total/n);}
Tidak ada komentar:
Posting Komentar