Penelusuran Pohon Biner Algoritma DFS(Stack) dan Algoritma BFS(Queue) dalam BahasaChttps://saungkode.wordpress.com/2014/04/16/penelusuran-pohon-biner-berdasarkan-kedalaman-dengan-algoritma-dfs-stack-dan-secara-melebar-level-order-dengan-algoritma-bfs-queue-dan-implementasinya-dalam-bahasa-c/

Penelusuran Pohon Biner Berdasarkan Kedalaman dengan Algoritma DFS + Stack dan Secara Melebar (Level Order) dengan Algoritma BFS + Queue serta Implementasinya dalam Bahasa C.Judulnya udah kaya judul jurnal -_-Yaudahlah ya, nah sekarang sesuai dengan judul postingan ini kita akan membahas bagaimana cara kerja dan implementasi algoritma DFS dan BFS dalam bahasa C. Dalam postingan kali ini saya melibatkan 3 buah stuktur data yang sudah di jelaskan sebelumnya, yaitustack,queuedan pohon biner.Depth First SearchDFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri darirootkemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : A B D H E I C F G J K LDalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita akan membahas dengan cara yang menggunakan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ? Berikut ini adalah urutan algoritmanya :1. Masukkan simpulrootke dalam tumpukan dengan push2. Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas3. Hapus isi stack teratas dengan prosedur pop4. Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul5. Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack6. Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah duaJadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan A B D H E I C F G J K L. Oiya, pada iterasi ke 13 itu kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.Jika dituliskan dalam bahasa C, prosedur pencetakan dengan DFS-nya kurang lebih bisa ditulis seperti ini :123456789101112131415161718192021void DFS_printPreOrder(simpul *root){if(root!=NULL){stack S;createEmptyStack(&S);push(root, &S);while(isStackEmpty(S) != 1){printf("%c ", S.top->elemen->huruf);simpul *node = peek(S);pop(&S);if(node->right != NULL){push(node->right, &S);}if(node->left != NULL){push(node->left, &S);}}printf("\n");}}

Breadth First SearchBFS (Breadth First Search) juga merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul ditelusuri darirootkemudian menelusuri semua simpul pada setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak anak tetangganya yang selevel.Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : A B C D E F G H I J K LSalah satu cara implementasi BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree. Berikut ini adalah urutan algoritmanya :1. Masukkan simpulrootke dalam antrian2. Periksa antrian terdepan apakah memiliki anak simpul3. Jika ya, masukan semua anak simpul ke dalam antrian4. Hapus antrian terdepan5. Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah duaUntuk gambar pohon biner di atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai berikut :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki urutan A B C D E F G H I J K L. Sama seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.Berikut adalah potongan prosedurnya dalam bahasa C :1234567891011121314151617181920void BFS_printLevelOrder(simpul *root){if(root!=NULL){queue Q;createEmptyQueue(&Q);addQueue(root, &Q);while(isQueueEmpty(Q) != 1){printf("%c ", Q.first->elemen->huruf);if(Q.first->elemen->left != NULL){addQueue(Q.first->elemen->left, &Q);}if(Q.first->elemen->right != NULL){addQueue(Q.first->elemen->right, &Q);}delQueue(&Q);}printf("\n");}}

Kodingan lengkapnya untuk DFS dan BFS karena menggunakan gabungan 3 struktur data dan dalam satu file, jadi cukup panjang. Bisa dilihat disini :123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219

/*Saungkode - saungkode.wordpress.com*//*Library*/#include #include #include #define LEFT "left"#define RIGHT "right"/*-------Pohon Biner*/typedef struct smp *alamatsimpul;typedef struct smp{char huruf; //Elemen pohonalamatsimpul right;//Ranting kananalamatsimpul left;//Ranting kiri}simpul;typedef struct{simpul* root;//Root = Akar pohon paling atas}tree;/*-------Stack*/typedef struct elmStack *alamatelmtStack;typedef struct elmStack{simpul* elemen;//alamat simpul pohonalamatelmtStack next;}containerStack;typedef struct {containerStack *top;//Paling atas}stack;/*-------Queue*/typedef struct elmQueue *alamatelmtQueue;typedef struct elmQueue{simpul* elemen;//alamat simpul pohonalamatelmtQueue next;}containerQueue;typedef struct{containerQueue *first;//Pointer depancontainerQueue *last;//Pointer belakang}queue;/*Saungkode - saungkode.wordpress.com*//*Mesin*//*-------Pohon Biner*///Buat pohon baruvoid makeTree(char huruf, tree *T){simpul *node;//Pointer barunode = (simpul *) malloc (sizeof (simpul));node->huruf = huruf;node->right = NULL;node->left = NULL;(*T).root = node;//Pindah akar}//Tambah elemen di ranting kananvoid addTree(char tempat[], char huruf, simpul **root){/*Jika ranting kanan masih kosong*/if((*root)->right == NULL){simpul *node;//Pointer barunode = (simpul *) malloc (sizeof (simpul));node->huruf = huruf;node->right = NULL;node->left = NULL;if(strcmp(tempat, RIGHT) == 0) (*root)->right = node;//Pindah ranting kananelse if(strcmp(tempat, LEFT) == 0) (*root)->left = node;//Pindah ranting kiri}}/*Saungkode - saungkode.wordpress.com*//*-------Stack*///buat stack kosongvoid createEmptyStack(stack *S){(*S).top = NULL;}//fungsi memeriksa stack kosong atau tidakint isStackEmpty(stack S){int hasil = 0;if(S.top == NULL){ //jika kosonghasil = 1;}return hasil;}//operator peeksimpul* peek(stack S){if(S.top != NULL){ //jika tidak kosongreturn S.top->elemen;}}//operator pushvoid push(simpul *node, stack *S ){containerStack *tunjuk;tunjuk = (containerStack *) malloc (sizeof (containerStack));tunjuk->elemen = node;tunjuk->next = (*S).top;(*S).top = tunjuk;tunjuk = NULL;}//operator popvoid pop(stack *S){if((*S).top != NULL){ //jika tidak kosongcontainerStack *tunjuk = (*S).top;(*S).top = (*S).top->next;tunjuk->next = NULL;free(tunjuk);}}/*Saungkode - saungkode.wordpress.com*//*-------Queue*///prosedur membuat queue kosongvoid createEmptyQueue(queue *Q){(*Q).first = NULL;(*Q).last = NULL;}//prosedur memeriksa apakah queue kosongint isQueueEmpty(queue Q){int hasil = 0;if(Q.first == NULL){hasil = 1;}return hasil;}//prosedur menambah elemen pada queue(addLast)void addQueue(simpul *node, queue *Q ){containerQueue *tunjuk;tunjuk = (containerQueue *) malloc (sizeof (containerQueue));tunjuk->elemen = node;tunjuk->next = NULL;//jika queue masih kosong (addFirst)if((*Q).first == NULL) (*Q).first = tunjuk;else (*Q).last->next = tunjuk;(*Q).last = tunjuk;tunjuk = NULL;}//prosedur delete queue (delFirst);void delQueue(queue *Q){//jika queue tidak kosongif((*Q).first != NULL){containerQueue *tunjuk = (*Q).first;(*Q).first = (*Q).first->next;tunjuk->next = NULL;free(tunjuk);}}/*Saungkode - saungkode.wordpress.com*//*-------Prosedur Cetak Pohon Biner*/// print pohon menurut keadalaman dengan algoritma DFSvoid DFS_printPreOrder(simpul *root){if(root!=NULL){stack S;createEmptyStack(&S);push(root, &S);while(isStackEmpty(S) != 1){printf("%c ", S.top->elemen->huruf);simpul *node = peek(S);pop(&S);if(node->right != NULL){push(node->right, &S);}if(node->left != NULL){push(node->left, &S);}}printf("\n");}}//print pohon per level dengan algoritma BFSvoid BFS_printLevelOrder(simpul *root){if(root!=NULL){queue Q;createEmptyQueue(&Q);addQueue(root, &Q);while(isQueueEmpty(Q) != 1){printf("%c ", Q.first->elemen->huruf);if(Q.first->elemen->left != NULL){addQueue(Q.first->elemen->left, &Q);}if(Q.first->elemen->right != NULL){addQueue(Q.first->elemen->right, &Q);}delQueue(&Q);}printf("\n");}}/*Saungkode - saungkode.wordpress.com*/int main(){tree T;makeTree('A', &T);addTree(LEFT , 'B', &T.root);addTree(RIGHT, 'C', &T.root);addTree(LEFT , 'D', &T.root->left);addTree(RIGHT, 'E', &T.root->left);addTree(LEFT , 'F', &T.root->right);addTree(RIGHT, 'G', &T.root->right);addTree(LEFT , 'H', &T.root->left->left);addTree(RIGHT, 'I', &T.root->left->right);addTree(LEFT , 'J', &T.root->right->right);addTree(RIGHT, 'K', &T.root->right->right);addTree(RIGHT, 'L', &T.root->right->right->right);DFS_printPreOrder(T.root);BFS_printLevelOrder(T.root);return 0;}